Let $a_n = n^n$. For all $n \in \Bbb N$, show that

Let $a_n = n^n$. For all $n \in \Bbb N$, show that

• There exists some $k \in \Bbb N$ such that for each $n \in \Bbb N$ we have: $a_{n+k} \equiv a_n \pmod m$ where $m \gt 1$ is a square-free integer.
• Find the minimum $k$, as a function of $m$ that satisfies the above congruence. ($a_{n+k} \equiv a_n \pmod m$)
-

By the Chinese Remainder Theorem, we can study the congruence modulo $p$, where $p$ is a prime dividing $m$. Therefore you can assume $k$ satisfies $$(n+k)^{n+k} \equiv n^n \pmod p$$ for every $n \in \mathbb N$. In particular, $$(p+k)^{p+k} \equiv p^p \equiv 0 \pmod p,$$ which leaves the only possibility $k \equiv 0 \pmod p$. Write $k = \ell p$. Then the conditions on $k$ becomes $$(n + \ell p)^{n + \ell p} \equiv n^{n + \ell p} \equiv n^n \pmod p$$ if and only if, by Fermat's theorem, $$n^{\ell} \equiv n^{\ell p} \equiv 1 \pmod p.$$ This implies $\ell \equiv 0 \pmod {p-1}$. Now suppose $k = p(p-1)m$, hence $$(n+p(p-1)m)^{n + p(p-1)m} \equiv n^{n+p(p-1)m} \equiv n^n \pmod p,$$ so that $k$ satisfies the constraints. Therefore the $k$ that satisfy the desired properties are the multiples of $p(p-1)$ and the minimal one is clearly $p(p-1)$.
Going back to $m$, since we must have $m \equiv 0 \pmod {p(p-1)}$ for every prime $p$ dividing $m$, the minimal $k$ you are looking for is $$k = \underset{p | m}{\mathrm{LCM}} \{ p(p-1) \}.$$
Good, may I ask you what does $\underset{p | m}{\mathrm{ppcm}} \{ p(p-1) \}$ mean here? Is it some sort of notation? – fmat Nov 2 '12 at 6:48
It's the least common multiple of the numbers $p(p-1)$ where $p$ divides $m$. Since we must have $p(p-1)$ dividing $m$ for all primes dividing $m$, to get the least number $k$ that satisfies all of these conditions at the same time, you must take the least common multiple of them. I'm sorry, I just noticed the notation ppcm ("Plus Petit Commun Multiple") is french, that's probably why you didn't understand. I'll fix that. – Patrick Da Silva Nov 2 '12 at 19:18