Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.