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$?
-
1What 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 – 2011-12-06
-
0@alvoutila - Yep, that's prettymuch it. – 2011-12-06
-
0This 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? – 2011-12-06
-
0Well, $gcd(3,4)=1$ and we know that both 4 and 3 divide $p+1$, so therefore 12 divides $p+1$ (why?). – 2011-12-06
-
0I 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$ – 2011-12-06
-
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}$.