|
| |
|
|
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.
|
|
0
|
|
|
|
3, 5, 7, 11, 13, 15, 17, 19, 23, 27, 29, 31, 35, 37, 39, 41, 43, 47, 51, 53, 55, 57, 59, 61, 67, 71, 73, 75, 79, 83, 85, 87, 89, 91, 95, 97, 101, 103, 107, 109, 111, 113, 115, 119, 123, 125, 127, 131, 135, 137, 139, 143, 149, 151, 155, 157, 159, 163, 167, 173, 175, 179, 181, 183, 187
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Conjecture: this sequence contains odd prime numbers A065091, but does not contain Carmichael numbers A002997.
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.
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
