|
| |
|
|
A320580
|
|
Numbers k such that for any positive integers x,y coprime to k, x^x == y (mod k) iff y^y == x (mod k).
|
|
0
|
|
|
|
1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 42, 48, 60, 72, 80, 84, 96, 120, 126, 144, 156, 160, 168, 180, 240, 252, 288, 312, 336, 360, 420, 468, 480, 504, 624, 672, 720, 780, 840, 936, 1008, 1092, 1248, 1260, 1440, 1560, 1680, 1872, 2016, 2184, 2340, 2520, 3120, 3276, 3360, 3744, 4368, 4680, 5040, 5460, 6240, 6552, 8736, 9360, 10080, 10920, 13104, 16380, 18720, 21840, 26208, 32760, 43680, 65520, 131040
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
There are exactly 78 terms in this sequence.
k is a term in this sequence iff k is divisible by A002322(k) (k is in A124240) and k is a divisor of 131040.
Proof. Let psi = A002322. For every x coprime to k we must have x^x == (x+k)^(x+k) == x^(x+k) (mod k), that is, x^k == 1 (mod k), so psi(k) must be divisible by k, and the condition is equivalent to x^x^(x+1) == x (mod k) for every x coprime to k.
The case k = 1, 2 is obvious. Now let k > 2, then k must be even.
Let g be a primitive lambda-root modulo k and psi(k), 0 < g < k, then g must be odd. By the condition, we have g^g^(g+1) == g (mod k), so g^(g+1) == 1 (mod psi(k)), g + 1 == 0 (mod psi(psi(k)). Also, (k-g)^(k-g)^(k-g+1) == k - g (mod k). Let d be the multiplicative order of k - g modulo k, then (k-g)^d == 1 (mod k) and (k-g)^(k-g+1) == 1 (mod d).
Case (i). d is even, then we have g^d == 1 (mod k) => d = psi(k). So (k-g)^(k-g+1) == 1 (mod psi(k)). Since k - g + 1 is an even number, we have g^(k-g+1) == 1 (mod psi(k)) => k - g + 1 == 0 (mod psi(psi(k))). psi(k) | k implies that psi(psi(k)) | psi(k) (and also divides k), so -g + 1 == 0 (mod psi(psi(k)) => psi(psi(k)) | 2.
Case (ii). d is odd, then g^d == -1 (mod k) => d = psi(k)/2. So (k-g)^(k-g+1) == 1 (mod psi(k)/2). Since k - g is an odd number, we get (k-g)^(k-g+1) == 1 (mod psi(k)) again. The same as above, psi(psi(k)) | 2.
So psi(k) | 24, k divides 131040.
Note (i). Now we show that there does exist such g being a primitive lambda-root modulo k and psi(k). Let k = 2^(e_0)*Product_{i=1..m} (p_i)^(e_i)*s, psi(k) = 2^(f_0)*Product_{i=1..m} (p_i)^(f_i)*t, where p_i are distinct odd primes, gcd(t, k) = gcd(s, psi(k)) = 1, then let g == 3 (mod 8), g be a primitive root modulo (p_i)^2 and a primitive lambda-root modulo s and t.
Note (ii). We show that k divides 131040 and psi(k) divides k suffice. Suppose k > 1, then gcd(x, k) = 1 implies that x is odd.
(a) k is not divisible by 3, by psi(k) | k we have psi(k) is also not divisible by 3, so k divides 2^5*5 = 160. x^(x+1) == 1 (mod 8) => x^x^(x+1) == x (mod 160).
(b) k is divisible by 3, then gcd(x, 6) = 1 => x^(x+1) == 1 (mod 24) => x^x^(x+1) == x (mod 131040). (End) [Revised by Jianing Song, Feb 04 2019]
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
3 is not a term because 2^2 == 1 (mod 3) but 1^1 !== 2 (mod 3).
10 is not a term because 13^13 == 3 (mod 10) but 3^3 !== 13 (mod 10).
20 is a term because 1^1 == 1 (mod 20), 3^3 == 7 (mod 20), 7^7 == 3 (mod 20), 9^9 == 9 (mod 20), 11^11 == 11 (mod 20), 13^13 == 13 (mod 20), 17^17 == 17 (mod 20), 19^19 == 19 (mod 20), and A002322(20) = 4 divides 20.
|
|
|
PROG
|
(PARI) for(i=1, 144, my(j=divisors(131040)[i]); if(j%lcm(znstar(j)[2])==0, print1(j, ", ")))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,fini,full
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
