Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
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 –  laovultai 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? –  laovultai 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$ –  laovultai Dec 6 '11 at 19:21

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.