# How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?

-
HINT It's equivalent to proving $\rm\ 1^{\:n}\equiv 1\$ by modular arithmetic. – Bill Dubuque Dec 6 '11 at 18:39

Well, I'll leave the case of $n=1$ to you.

So, for a fixed $k$, suppose that $k^n\equiv 1 \mod(k-1)$ for some $n\in \mathbb{N}$.

We want to show that $k^{n+1} \equiv 1 \mod(k-1)$. Well, $k^{n+1}=k^n k$, and we know that $k^n\equiv 1 \mod(k-1)$ (since this is the induction hypothesis). So, what is $k^{n+1}$ congruent to mod $k-1$?

-
What you think about following proof? Let us suppose that for some n $k^n \equiv 1 \pmod {k-1}$. One has to show that $k^{n+1} \equiv 1 \pmod {k-1}$. Now because $k^{n+1}=k^n \cdot k \equiv 1 \cdot k \equiv 1 \pmod {k-1}$(because $k \equiv 1 \pmod {k-1}$). Thus $k^{n+1} \equiv 1 \pmod {k-1}$ and claim holds – alvoutila Dec 6 '11 at 18:42
@alvoutila - Yep, that's prettymuch it. – user5137 Dec 6 '11 at 18:45
This question goes outside of the scope of this "chapter", but here it is: How is it that $p \equiv 3 \pmod 4$ and $p \equiv 2 \pmod 3$ is equivalent with condition $p \equiv -1 \equiv 11 \pmod {12}$? Maybe something to do with chinese remainder theorem? – alvoutila Dec 6 '11 at 18:57
Well, $gcd(3,4)=1$ and we know that both 4 and 3 divide $p+1$, so therefore 12 divides $p+1$ (why?). – user5137 Dec 6 '11 at 19:00
I know that if remainders are same then $p \equiv x \pmod {12}$. For example $p \equiv 1 \pmod 4$ and $p \equiv 1 \pmod 3$ then $p \equiv 1 \pmod {12}$ but would you explain in more detail why $p \equiv -1 \equiv 11 \pmod 12$ if $p \equiv 3 \pmod 4$ and $p \equiv 2 \pmod 3$ – alvoutila Dec 6 '11 at 19:21

Hint: $k \equiv 1 \pmod{k-1}$.

-