|
| |
|
|
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.
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
