|
%I #32 May 26 2019 19:42:48
%S 1,2,4,6,8,12,16,18,20,24,32,36,40,42,48,60,72,80,84,96,120,126,144,
%T 156,160,168,180,240,252,288,312,336,360,420,468,480,504,624,672,720,
%U 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
%N Numbers k such that for any positive integers x,y coprime to k, x^x == y (mod k) iff y^y == x (mod k).
%C There are exactly 78 terms in this sequence.
%C 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.
%C From _Jianing Song_, Nov 17 2018: (Start)
%C 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.
%C The case k = 1, 2 is obvious. Now let k > 2, then k must be even.
%C 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).
%C 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.
%C 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.
%C So psi(k) | 24, k divides 131040.
%C 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.
%C 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.
%C (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).
%C (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]
%e 3 is not a term because 2^2 == 1 (mod 3) but 1^1 !== 2 (mod 3).
%e 10 is not a term because 13^13 == 3 (mod 10) but 3^3 !== 13 (mod 10).
%e 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.
%o (PARI) for(i=1, 144, my(j=divisors(131040)[i]); if(j%lcm(znstar(j)[2])==0, print1(j, ", ")))
%Y Cf. A002322, A124240.
%K nonn,fini,full
%O 1,2
%A _Jianing Song_, Oct 16 2018
|
