1
$\begingroup$

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

  • 0
    **HINT** It's equivalent to proving $\rm\ 1^{\:n}\equiv 1\ $ by modular arithmetic.2011-12-06

2 Answers 2

2

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

  • 0
    If $a,b\in \mathbb{Z}$ with $gcd(a,b)=1$ and if we have $a\vert c$ and $b \vert c$ for some $c\in \mathbb{Z}$, then $ab \vert c$ (if you're not convinced that this is true, I'd advise taking a bit of time to write down a proof).2011-12-06
3

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