OFFSET
1,1
COMMENTS
Conjecture: this sequence contains odd prime numbers A065091, but does not contain Carmichael numbers A002997.
Proof from Jianing Song, Jun 14 2021: (Start)
Conjecture: Let v(n) = A007814(n) be the 2-adic valuation of n. Define
A(n) = A182816(n) as the number of nonnegative m < n such that m^n == m (mod n),
B(n) = A333570(n) as the number of nonnegative m < n such that m^n == -m (mod n),
C(n) as the number of nonnegative m < n such that m^(2^v(n-1)+1) == m (mod n), and
D(n) as the number of nonnegative m < n such that m^(2^v(n-1)+1) == -m (mod n).
Then A(n)/B(n) = n and C(n)/D(n) = 2^v(n-1) + 1 if and only if n is an odd prime.
The conjecture is correct.
"<=": If n is an odd prime, then A(n) = n, B(n) = 1, C(n) = 2^v(n) + 1, D(n) = 1.
"=>": If A(n)/B(n) = n, since A(n) <= n, we must have A(n) = n, so n is either prime or a Carmichael number.
Let n = (p_1)*(p_2)*...*(p_k) be a Carmichael number. Write d = v(n-1), s = (n-1)/2^d be odd.
If m^(2^d+1) == -m (mod n), then m^(2^d) == -1 (mod n/gcd(m,n)). Since m^(s+1) == 1 (mod n), we have (-1)^s == 1 (mod n/gcd(m,n)), so n/gcd(m,n) = 1, m = 0. This shows that D(n) = 1.
For gcd(m,n) = Product_{i in S} p_i, m^(2^v(n-1)+1) == m (mod n) is equivalent to m == 0 (mod Product_{i in S} p_i), m^(2^d) == 1 (mod Product_{i not in S} p_i). The number of solutions modulo n is Product_{i not in S} gcd(2^d, p_i-1). Hence we have C(n) = Sum_{S subset of {1,2,...,k}} Product_{i not in S} gcd(2^d, p_i - 1) = Product_{i=1..k} (1 + gcd(2^d, p_i-1)).
If n is a Carmichael number such that C(n)/D(n) = 2^d + 1, then Product_{i=1..k} (1 + gcd(2^d, p_i-1)) = 2^d + 1. Hence gcd(2^d, p_i-1) < 2^d for 1 <= i <= k. By Zsigmondy's Theorem, unless d = 1 or 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 = 1 or 3 (otherwise p does not divide Product_{i=1..k} (1 + gcd(2^d, p_i-1))), then k = 1 or 2. But a Carmichael number must have at least 3 prime factors, a contradiction! (End)
In the case k = r, this sequence contains odd prime and Carmichael numbers, but does not contain any other numbers.
PROG
(Magma) [r: r in [2..190] | #[m: m in [0..r-1] | m^k mod r eq m] eq #[m: m in [0..r-1] | -m^k mod r eq m]*k where k is 2^Valuation(r-1, 2) + 1];
CROSSREFS
KEYWORD
nonn
AUTHOR
Juri-Stepan Gerasimov, Jul 28 2021
STATUS
approved