How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?
How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?
1
$\begingroup$
elementary-number-theory
induction
-
0**HINT** It's equivalent to proving $\rm\ 1^{\:n}\equiv 1\ $ by modular arithmetic. – 2011-12-06
2 Answers
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$?
-
0If $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}$.