0
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$
    – Rushy
    Sep 26, 2021 at 20:53
  • $\begingroup$ Because $\phi(n)<n$ so the value eventually reaches $1$ on iteration. $\endgroup$ Sep 26, 2021 at 20:56
  • $\begingroup$ There's no need to iterate here since they use strong induction. $\endgroup$
    – Rushy
    Sep 26, 2021 at 20:58
  • $\begingroup$ @Rushy Do you mean to say it's just a hypothesis? $\endgroup$ Sep 26, 2021 at 20:59
  • $\begingroup$ 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$. $\endgroup$
    – Rushy
    Sep 26, 2021 at 21:01

1 Answer 1

1
$\begingroup$

The natural numbers are a well order ( meaning there's a least element). This means $\phi(n)<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.

$\endgroup$
1
  • $\begingroup$ More or less helped me out, thanks, I will still accept as an answer. $\endgroup$ Sep 26, 2021 at 21:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .