cp's OEIS Frontend

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.