Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|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
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|cite|improve this answer
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}$.

share|cite|improve this answer

Your Answer


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.