# Why does $(^n a)$ eventually become constant modulo $\phi (n)$.

Sorry, I changed this question from another one I delete a few minutes ago, but I'm slightly confused on this question."

In the following link, the statement in Case $$1$$, "since $$\phi(m) < m$$, by induction hypothesis, $$(^n a) \text{ mod } \phi(m)$$ is eventually constant" doesn't make a lot of sense to me can someone elaborate on that?

To elaborate, the base question is that $$1,a,a^a,...$$ eventually becomes constant modulo $$n.$$

• What doesn't make sense about it? It's just the induction hypothesis, you assume that ${}^na \pmod k$ is eventually constant for all $k \leq m - 1$, and use that to show that it holds for $k = m$. Sep 26, 2021 at 20:53
• Because $\phi(n)<n$ so the value eventually reaches $1$ on iteration. Sep 26, 2021 at 20:56
• There's no need to iterate here since they use strong induction. Sep 26, 2021 at 20:58
• @Rushy Do you mean to say it's just a hypothesis? Sep 26, 2021 at 20:59
• Yes, in the base case you show that it holds for all $n > 0$ and $m = 2$, then you assume that it holds for all modulo up to $m - 1$, and use that to show it holds for $m$. Sep 26, 2021 at 21:01

The natural numbers are a well order ( meaning there's a least element). This means $$\phi(n) which implies $$\phi(\phi(n))<\phi(n)$$ etc. Will eventually hit the lowest element. Since modulo $$1$$ always returns $$0$$ we get everything at or above that level doesn't affect the outcome.