3
$\begingroup$

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$)

1 Answers 1

1

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,

  • 1
    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.2012-11-02