A345329 Composite numbers such that m^(2^v(k-1)+1) == m (mod k) has exactly 2^v(k-1) + 1 solutions modulo k, where v(k) = A007814(k) is the 2-adic valuation of k.

4, 8, 16, 27, 32, 57, 64, 125, 128, 201, 217, 243, 249, 256, 297, 329, 343, 393, 441, 473, 489, 512, 537, 553, 633, 649, 681, 713, 889, 921, 1024, 1081, 1161, 1177, 1257, 1273, 1331, 1337, 1401, 1497, 1529, 1561, 1577, 1593, 1641, 1673, 1689, 1817, 1897, 1929, 1977, 2048

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

Cf. A007814.

Sequence in context: A180861 A353316 A068936 * A349112 A325127 A054744

Adjacent sequences: A345326 A345327 A345328 * A345330 A345331 A345332

Keyword

nonn

Author

Jianing Song, Jun 14 2021

Status

approved