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

  • 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 holds2011-12-06
  • 0
    @alvoutila - Yep, that's prettymuch it.2011-12-06
  • 0
    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?2011-12-06
  • 0
    Well, $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
  • 0
    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$2011-12-06
  • 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}$.