cp's OEIS Frontend

A346669 Numbers r such that the number of nonnegative m < r such that m^k == m (mod r) is equal to k*(the number of nonnegative m < r such that -m^k == m (mod r)), where k = 2^A007814(r-1) + 1.

%I A346669 #22 Dec 10 2023 17:17:28
%S A346669 3,5,7,11,13,15,17,19,23,27,29,31,35,37,39,41,43,47,51,53,55,57,59,61,
%T A346669 67,71,73,75,79,83,85,87,89,91,95,97,101,103,107,109,111,113,115,119,
%U A346669 123,125,127,131,135,137,139,143,149,151,155,157,159,163,167,173,175,179,181,183,187
%N A346669 Numbers r such that the number of nonnegative m < r such that m^k == m (mod r) is equal to k*(the number of nonnegative m < r such that -m^k == m (mod r)), where k = 2^A007814(r-1) + 1.
%C A346669 Conjecture: this sequence contains odd prime numbers A065091, but does not contain Carmichael numbers A002997.
%C A346669 Proof from _Jianing Song_, Jun 14 2021: (Start)
%C A346669 Conjecture: Let v(n) = A007814(n) be the 2-adic valuation of n. Define
%C A346669   A(n) = A182816(n) as the number of nonnegative m < n such that m^n == m (mod n),
%C A346669   B(n) = A333570(n) as the number of nonnegative m < n such that m^n == -m (mod n),
%C A346669   C(n) as the number of nonnegative m < n such that m^(2^v(n-1)+1) == m (mod n), and
%C A346669   D(n) as the number of nonnegative m < n such that m^(2^v(n-1)+1) == -m (mod n).
%C A346669 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.
%C A346669 The conjecture is correct.
%C A346669 "<=": If n is an odd prime, then A(n) = n, B(n) = 1, C(n) = 2^v(n) + 1, D(n) = 1.
%C A346669 "=>": 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.
%C A346669 Let n = (p_1)*(p_2)*...*(p_k) be a Carmichael number. Write d = v(n-1), s = (n-1)/2^d be odd.
%C A346669 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.
%C A346669 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)).
%C A346669 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)
%C A346669 In the case k = r, this sequence contains odd prime and Carmichael numbers, but does not contain any other numbers.
%o A346669 (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];
%Y A346669 Cf. A002997, A007814, A065091, A182816, A333570, A340281.
%K A346669 nonn
%O A346669 1,1
%A A346669 _Juri-Stepan Gerasimov_, Jul 28 2021