3
$\begingroup$

This may be a very basic number theory question, but I don't understand:

Why does $a^b \bmod c = (a \bmod c)^b \bmod c$

  • 0
    There is an integer k with $a = (a \mod c) + kc$. If you raise both sides to the $b$th power and use the binomial theorem to expand $((a \mod c) + kc)^b$ you find that every term in the expansion except perhaps the first, $(a \mod c)^b$, is a multiple of $c$. So $a^b = (a \mod c)^b +$ (a multiple of $c$), so the congruence you want holds. It is worth pointing out that some number theory books never give independent to "$b \mod c$" for integers $b,c$; they only define congruences (ie, what $a \equiv b (\mod c)$ means). Understanding the difference can make intro number theory much easier.2011-10-27

5 Answers 5

3

Suppose that x \;\mathrm{mod}\; n = x' \;\mathrm{mod}\; n and y \;\mathrm{mod}\; n = y' \;\mathrm{mod}\; n.

Then it must be the case that x=x'+nk and y=y'+n\ell for some $k,\ell \in \mathbb{Z}$.

Thus xy=(x' +nk)(y'+n\ell) = x'y' + n(y'k+x'\ell+nk\ell). In other words, $xy$ and x'y' differ by a multiple of $n$. Therefore, xy \;\mathrm{mod}\; n = x'y' \;\mathrm{mod}\; n.

This says multiplication (mod $n$) does not depend on the exact choice of integers just the remainders.

Now to apply to your situation. $a \;\mathrm{mod}\; n = (a \;\mathrm{mod}\; n)\;\mathrm{mod}\;n$ so $a^2 \;\mathrm{mod}\; n = a\cdot a \;\mathrm{mod}\; n = (a \;\mathrm{mod}\; n) \cdot (a \;\mathrm{mod}\; n) \;\mathrm{mod}\;n =(a \;\mathrm{mod}\; n)^2 \;\mathrm{mod}\;n$.

To get higher powers just repeat (use induction).

Edit: I should also mention, the same thing is true of addition mod $n$. Adding does not depend on the exact integers, just their remainders. You can prove this much the same way I did for multiplication:

x \;\mathrm{mod}\; n = x' \;\mathrm{mod}\; n and y \;\mathrm{mod}\; n = y' \;\mathrm{mod}\; n then x+y \;\mathrm{mod}\; n = x'+y' \;\mathrm{mod}\; n.

As Leslie mentions in the comments above, it is must easier (better) to deal with modular arithmetic in terms of congruence classes. What I did above says that we can multiply congruence classes by multiplying any two representatives of those classes (the same for addition). In "abstract algebra" language, we are discovering that equivalence classes mod $n$ have a ring structure (in fact, we are just looking at the quotient ring $\mathbb{Z}/n\mathbb{Z}$).

2

By the definition of congruence, you want to show that $c$ divides $(\mbox{some number congruent to a})^b - a^b$. This means you want to show that $c$ divides $(a + ck)^b - a^b$ for some $k$. Expand the expression and you should be able to show this is true.

2

Hint $\rm\ \ c\ |\ (a + n\:c)^b - a^b\:$ is the special case $\rm\ R = \mathbb Z,\ \ f(x) = x^b,\ \ x = a+n\:c\ $ in the

Factor Theorem $\rm\ \ \ \ \ \ x-a\ \ \,|\,\ \ f(x)\,-\,f(a)\ \ in\ \ R[x],\ $ for $\rm\ a\in R,\ \ f(x)\in R[x]$

or, said operationally: $\rm\ x\equiv a \Rightarrow f(x)\equiv\: f(a),\:$ a prototypical ring congruence inference.

See also my many posts on the Congruence Product Rule.

1

Because the canonical map from ${\bf Z}$ to ${\bf Z}/c{\bf Z}$ is a ring homomorphism.

1

If you are comfortable with $x\equiv y\bmod n\Rightarrow xz\equiv yz \;(\bmod n)$, then

$a\equiv (a \bmod c)\; (\bmod c)$

$a^b\equiv (a\bmod c)^b\; (\bmod c)$

$a^b \,\bmod c=(a\bmod c)^b\bmod c$.