login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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.
1

%I #13 Jun 14 2021 14:21:04

%S 4,8,16,27,32,57,64,125,128,201,217,243,249,256,297,329,343,393,441,

%T 473,489,512,537,553,633,649,681,713,889,921,1024,1081,1161,1177,1257,

%U 1273,1331,1337,1401,1497,1529,1561,1577,1593,1641,1673,1689,1817,1897,1929,1977,2048

%N 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.

%C 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.

%C 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).

%C 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)).

%C 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.

%C 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).

%H Jianing Song, <a href="/A345329/b345329.txt">Table of n, a(n) for n = 1..10000</a>

%H Wikipedia, <a href="https://en.m.wikipedia.org/wiki/Zsigmondy%27s_theorem">Zsigmondy's theorem</a>

%e 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).

%e 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.

%e 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)).

%o (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)

%Y Cf. A007814.

%K nonn

%O 1,1

%A _Jianing Song_, Jun 14 2021