Take the 2-minute tour ×

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$)
share|improve this question

1 Answer 1

up vote 1 down vote accepted

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) \}. $$

Hope that helps,

share|improve this answer
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

Your Answer


