Welcome to our community

Be a part of something great, join today!

Number Theory Proving operations of congruence modulo m

crypt50

New member
Jun 29, 2013
21
If a, b and m > 0 are integers such that a % b (mod m), then a^n % b^n (mod m) for all positive integers n. I don't know how to go about it, any help would be greatly appreciated.
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,193
By '%', do you mean congruent? That's typically written
$$a \equiv b \;( \text{mod} \; m),\qquad \text{and}
\qquad a^{n} \equiv b^{n} \;( \text{mod} \; m).$$
Use induction on $n$ to prove this. What will you need to show the inductive step?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
Welcome to MHB, crypt50! :)

Assuming you meant what Ackbach suggested, here's an alternative way.

The expression $a \equiv b \pmod m$ means that there is a $k \in \mathbb Z$ such that $a=b+km$.
This implies that $a^n=(b+km)^n$.
Can you expand the right hand side with the binomial theorem?
If so, what can you conclude?