OFFSET
1,1
COMMENTS
For primes p, m^(2^v(p-1)+1) == m (mod p) has exactly 2^v(p-1) + 1 solutions modulo p. This sequence gives that composite numbers that satisfy this condition.
Even terms are powers of 2 that are greater than or equal to 4. For odd k, k is a term if and only if k is of one of the two forms: (i) k = p^e for odd primes p and odd e >= 3; (ii) k = (p_1)^(e_1) * (p_2)^(e_2), p_1 == p_2 == 3 (mod 4), k == 9 (mod 16).
Proof: Let k = (p_1)^(e_1)*(p_2)^(e_2)*...*(p_r)^(e_r) be an odd number. Write d = v(k-1). It is easy to see that the number of solutions to m^(2^d+1) == m (mod (p_i)^(e_i)) is 1 + gcd(2^d, (p_i-1)*(p_i)^(e_i)).
If r = 1, then k = p^e is in this sequence if and only if (p-1)*p^(e-1) is divisible by 2^v2(p^e-1), or equivalently, v2(p-1) >= v2(p^e-1). So k = p^e is in this sequence if and only if e >= 3 is odd.
If r >= 2, then k is in this sequence if and only if Product_{i=1..r} (1 + gcd(2^d, (p_i-1)*(p_i)^(e_i))) = 2^d + 1. Hence gcd(2^d, (p_i-1)*(p_i)^(e_i)) < 2^d for 1 <= i <= k. By Zsigmondy's Theorem, unless d = 3, 2^d + 1 has a primitive prime factor p such that p does not divide 2^e + 1 for all e < d. So we must have d = 3 (otherwise p does not divide Product_{i=1..r} (1 + gcd(2^d, (p_i-1)*(p_i)^(e_i)))), then r = 2 and gcd(2^d, (p_1-1)*(p_1)^(e_1)) = gcd(2^d, (p_1-1)*(p_1)^(e_1)) = 2. In conclustion, k is in this sequence if and only if r = 2, p_1 == p_2 == 3 (mod 4), k == 9 (mod 16).
LINKS
Jianing Song, Table of n, a(n) for n = 1..10000
Wikipedia, Zsigmondy's theorem
EXAMPLE
If k is a power of 2 that is greater than or equal to 4, then 2^v(k-1)+1 = 2, and m^2 == m (mod k) has exactly 2 solutions: m == 0, 1 (mod k).
If k = p^e for odd primes p and odd e >= 3, then 2^v(k-1)+1 = 2^v(p-1)+1 and m^(2^v(p-1)+1) == m (mod k) has exactly 2^v(p-1)+1 solutions: m == 0 (mod k) is a solution, and m^(2^v(p-1)) == 1 (mod k) has 2^v(p-1) solutions.
If k = (p_1)^(e_1) * (p_2)^(e_2), p_1 == p_2 == 3 (mod 4), k == 9 (mod 16), then 2^v(k-1)+1 = 9, and m^9 == m (mod k) has exactly 9 solutions: m == -1, 0, 1 (mod (p_1)^(e_1)) and m == -1, 0, 1 (mod (p_2)^(e_2)).
PROG
(PARI) isA345329(n) = if(n%2, my(f=factor(n), w=omega(n)); if(w==1, my(e=f[1, 2]); e%2 && e>1, if(w==2, n%16==9 && f[1, 1]%4==3 && f[2, 1]%4==3, 0)), isprimepower(n)&&n>2)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jianing Song, Jun 14 2021
STATUS
approved