OFFSET
1,1
COMMENTS
Write psi = A002322, b = A118106. These are numbers k that are not prime powers such that b(k) < psi(k).
If k = Product_{i=1..t} p_i^e_i (t > 1), where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, then k is here, as b(k) | psi(k)/2.
If k = 2 * Product_{i=1..t} p_i^e_i, where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, and p_i == 1, 7 (mod 8), then k is here. For example, k = 2p, where p == 1, 7 (mod 8).
If k = 2^e * Product_{i=1..t} p_i^e_i (e > 1), where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, and p_i == 1 (mod 8), then k is here. For example, k = 2^e*p, where p == 1 (mod 8).
If k = p_1^e_1 * p_2^e_2, where p_1 is not a primitive root modulo p_2^e_2, p_2 is not a primitive root modulo p_1^e_1, then k is not necessarily here: for k = 3^2 * 67 = 603, 3 is not a primitive root modulo 67, 67 is not a primitive root modulo 3^2, but b(603) = psi(603) = 66. Conversely, if p_1 is a primitive root modulo p_2^e_2, then k can still be here: for k = 3^2 * 17 = 153, 3 is a primitive root modulo 17, but b(153) = 16 while psi(153) = 48.
If k is an odd number, then 4k is here if and only if 8k is also here. Write k = Product_{i=1..t} p_i^e_i, then b(4k) = lcm(lcm_{i=1..t} ord(p_i,4),lcm_{i=1..t} ord(2,p_i^e_i),b(k)), b(8k) = lcm(lcm_{i=1..t} ord(p_i,8),lcm_{i=1..t} ord(2,p_i^e_i),b(k)). It is easy to see that lcm(ord(p_i,4),ord(2,p_i^e_i)) = lcm(ord(p_i,8),ord(2,p_i^e_i)), so b(4k) = b(8k). Note that psi(4k) = psi(8k).
If k is an odd number such that 4k is here, then 16k is also here (but the converse is not true). Write k = Product_{i=1..t} p_i^e_i, N = lcm(lcm_{i=1..t} ord(2,p_i^e_i),b(k)), then b(4k) = lcm(lcm_{i=1..t} ord(p_i,4),N), b(16k) = lcm(lcm_{i=1..t} ord(p_i,16),N) = b(4k) or b(4k)*2 or b(4k)*4. Note that psi(16k) = lcm(psi(4k),4). If we have b(4k) < psi(4k) and b(16k) = psi(16k), let M = psi(k), then:
Case (a): M == 2 (mod 4), then b(16k) = psi(16k) = 2*psi(4k) = 2M, and b(4k) = b(16k)/4 = M/2 which is an odd number, so ord(2,p_i^e_i) is odd for all i, so p_i == 1, 7 (mod 8), which gives ord(p_i,16) <= 2*ord(p_i,4). As a result, b(16k) <= 2*b(4k), a contradiction!
Case (b): M == 0 (mod 4), then b(16k) = psi(16k) = psi(4k) = M. If N is divisible by 4, then b(4k) = b(16k) = N, a contradiction. So 4 does not divide N, we have v(M,2) = v(lcm(lcm_{i=1..t} ord(p_i,16),N),2) <= 2, but 4 | M, so v(M,2) = 2, where v(,2) is the 2-adic valuation. As a result, there must exist p_i congruent to 5 mod 8 to make v(M,2) = 2, then 4 | ord(2,p_i^e_i), so 4 | N, a contradiction!
EXAMPLE
Let ord(a,r) be the multiplicative order of a modulo r.
For k = 175 = 5^2 * 7, b(175) = lcm(ord(7,5^2),ord(5,7)) = lcm(4,6) = 12, while psi(175) = lcm(20,6) = 60, so 175 is a term.
For k = 410 = 2 * 5 * 41, b(410) = lcm(ord(5,2),ord(41,2),ord(2,5),ord(41,5),ord(2,41),ord(5,41)) = 20, while psi(410) = lcm(1,4,40) = 40, so 410 is a term.
PROG
CROSSREFS
KEYWORD
nonn
AUTHOR
Jianing Song, Nov 02 2019
STATUS
approved