|
| |
|
|
A197658
|
|
Smallest k such that i^k = i mod n for each i in [0..n-1], or 0 if no such k exists.
|
|
1
|
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,1
|
|
|
COMMENTS
|
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).
Fermat's little theorem suggests that a(n) = n when n is prime, since then clearly i^(n - 1) = 1 mod n.
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = abs(mu(n))(psi(n) + 1), where mu(n) is the Moebius function and psi(n) is the reduced totient function.
|
|
|
EXAMPLE
|
a(6) = 3 because in the powers modulo 6
0 1 2 3 4 5
0 1 4 3 4 1
0 1 2 3 4 5
we see that at k = 1 and k = 3 each i^k = i mod 6.
a(7) = 7 because in the powers modulo 7
0 1 2 3 4 5 6
0 1 4 2 2 4 1
0 1 1 6 1 6 6
0 1 2 4 4 2 1
0 1 4 5 2 3 6
0 1 1 1 1 1 1
0 1 2 3 4 5 6
we see that at k = 1 and k = 7 each i^k = i mod 7.
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.
|
|
|
MATHEMATICA
|
Table[Abs[MoebiusMu[n]](CarmichaelLambda[n] + 1), {n, 2, 100}]
|
|
|
PROG
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
