2
$\begingroup$

If a,b,c,k $\in\mathbb{Z\cap{(N\cup{0}})}$ and a$\equiv$b(mod c) then prove that a$^{k}\equiv$b$^{k}$(mod c). I know how to prove it using induction but I wanted to know if there is a method that only uses number theory.

$\endgroup$
  • 1
    $\begingroup$ Of course, the quotient $\frac{a^k-b^k}{a-b} = a^{k-1} + a^{k-2} b + \cdots + b^{k-1} = \sum_{i=0}^{k-1} a^{k-1-i} b^i$ would have to involve a recursive definition at some point (if you're going for full formalization), and recursion and induction are nearly the same thing, so... $\endgroup$ – Daniel Schepler Aug 27 '18 at 17:40
1
$\begingroup$

If $a \equiv b \pmod{c}$, then these two guys are the same element of the ring of integers modulo $c$. Hence the $k$-th power of one is the same as the $k$-th power of the other.

For this you need to prove that the product in the quotient ring is well defined (no induction) and then you can conclude (with induction, if you really want to be that formal) that multiplying $k$ times one is the same as multiplying $k$ times the other one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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