A197658 - OEIS

%I #31 Dec 13 2014 14:14:27

%S 2,3,0,5,3,7,0,0,5,11,0,13,7,5,0,17,0,19,0,7,11,23,0,0,13,0,0,29,5,31,

%T 0,11,17,13,0,37,19,13,0,41,7,43,0,0,23,47,0,0,0,17,0,53,0,21,0,19,29,

%U 59,0,61,31,0,0,13,11,67,0,23,13,71,0,73,37,0,0,31,13,79,0,0,41,83,0,17

%N Smallest k such that i^k = i mod n for each i in [0..n-1], or 0 if no such k exists.

%C a(n) = 0 when n is not squarefree. The reason is obvious when n is a perfect square, cube or higher power. Otherwise, n = (p^r)(q^s), where p is some prime, gcd(p, q) = 1, r > 1, s != r; then when k > floor(log_p(n)), p^k mod n is always a multiple of p^2 and thus p doesn't occur again (e.g., for n = 72, the powers of 2 mod 72 are 1, 2, 4, 8, 16, 32, 64, 56, 40, 8, ... in fact, always multiples of 2^3 past 4).

%C Fermat's little theorem suggests that a(n) = n when n is prime, since then clearly i^(n - 1) = 1 mod n.

%C Often, but not always, a(n) = abs(mu(n))(phi(n) + 1), where mu(n) is the Möbius function and phi(n) is Euler's totient function. This is the case when phi(n) = psi(n), where psi(n) is the reduced totient function (or Carmichael lambda function). Thus when n is squarefree it's not guaranteed that a(n) is a divisor of n.

%H Charles R Greathouse IV, <a href="/A197658/b197658.txt">Table of n, a(n) for n = 2..10000</a>

%F a(n) = abs(mu(n))(psi(n) + 1), where mu(n) is the Moebius function and psi(n) is the reduced totient function.

%F a(n) = A002322(n) + 1 if n squarefree, otherwise a(n) = 0. - _Joerg Arndt_, Jan 22 2013

%e a(6) = 3 because in the powers modulo 6

%e 0 1 2 3 4 5

%e 0 1 4 3 4 1

%e 0 1 2 3 4 5

%e we see that at k = 1 and k = 3 each i^k = i mod 6.

%e a(7) = 7 because in the powers modulo 7

%e 0 1 2 3 4 5 6

%e 0 1 4 2 2 4 1

%e 0 1 1 6 1 6 6

%e 0 1 2 4 4 2 1

%e 0 1 4 5 2 3 6

%e 0 1 1 1 1 1 1

%e 0 1 2 3 4 5 6

%e we see that at k = 1 and k = 7 each i^k = i mod 7.

%e a(8) = 0 because in the powers modulo 8, 4^k zeros out at k = 2, thus preventing the row 0 1 2 3 4 5 6 7 from occurring at any position other than k = 1.

%t Table[Abs[MoebiusMu[n]](CarmichaelLambda[n] + 1), {n, 2, 100}]

%o (PARI) a(n)=if(issquarefree(n),lcm(znstar(n)[2])+1,0) \\ _Charles R Greathouse IV_, Jan 17 2013

%Y Cf. A002322.

%K nonn,easy

%O 2,1

%A _Alonso del Arte_, Jan 07 2013