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).

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

Offset: 1

Author

Jianing Song, Oct 16 2018

Keywords

• nonn
• fini
• full

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.

From Jianing Song, Nov 17 2018: (Start)

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]

Examples

			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.
		

Crossrefs

Cf. A002322, A124240.

Programs

PARI

for(i=1, 144, my(j=divisors(131040)[i]); if(j%lcm(znstar(j)[2])==0, print1(j, ", ")))