# Validity of a proof of a mod identity

So I constructed this proof that for any integers $a, c\text{ and }n$, with $n > 1$, if $a ≡ c \pmod n$ then for any integer $m, a^m ≡ c^m \pmod n$.

Proof:

1. $a ≡ c \pmod n$ implies that $a \bmod n = c \bmod n$

2. $a^m \bmod n = ((a \bmod n)^m) \bmod n.$

3. But $a \bmod n = c \bmod n$ (from step 1), and, thus, by substitution: $$((a \bmod n)^m) \bmod n = ((c \bmod n)^m) \bmod n.$$

4. Finally, $((c \bmod n)^m) \bmod n = c^m \bmod n$, and, thus, $a^m \bmod n = c^m \bmod n$, which implies that $a^m ≡ c^m \pmod n$.

Is this proof valid?

-
Yes and no. Your assertion $(2.)$ is certainly true. If it has been proved in the course already, then it can be used. Otherwise it needs justification. I imagine the result has been proved for a product of two terms. If not, that has to be done. Then a straightforward induction, perhaps an informal one, settles things. I also have a slight worry about the word integer. Do you mean positive integer? By the way, you could give a proof not using the operator mod, the one that produces a number between $0$ and $n-1$. – André Nicolas Aug 27 '12 at 7:31
Thanks for the response Andre. I have proved the second assertion previously, yes. And I should have stated that m > 0. The book I'm reading said to use induction, but I thought this was an alternative. – Kariem Aug 27 '12 at 7:35
Then everything is OK, except you should say for every positive (or non-negative) $m$. – André Nicolas Aug 27 '12 at 7:40

It's hard for me to follow your proof as it is written without LaTeX, but here's a very simple proof:

$$a=c\pmod n\Longleftrightarrow a-c=kn\,\,,\,\,k\in\Bbb Z\Longrightarrow$$ $$\Longrightarrow a^m-c^m=(a-c)\stackrel{\text{call this integer}X}{\overbrace{(a^{m-1}+a^{m-2}c+...+ac^{m-2}+c^{m-1})}}=kXn\Longrightarrow a^m=c^m\pmod n$$

-

It is somewhat ambiguous when you write $a \text{ mod } n$ as an element.

A easy way to see this is to prove that if $a \equiv b \text{ mod } n$ and $x \equiv y \text{ mod } n$, then $ax \equiv by \text{ mod } n$.

To prove this you have

1) $a - b = in$

2) $x - y = jn$

Then $ax - ay - bx + by = (a - b)(x - y) = ijn$

By 2) $x = y + jn$. Substituting in

$ax - ay - b(y + in) + by = ijn$

$ax - by - ay + by - bin = ijn$

$ax - by = ay - by + bin + ijn$

$ax - by = y(a - b) + bin + ijn$

using 1), you get

$ax - by = y(in) + bin + ijn$

$ax - by = n(iy + bi + ij)$

Hence $ax \equiv by \text{ mod } n$.

Now to solve your original question, $a \equiv c \text{ mod } n$. Applying the lemma $m$ times, you get $a^m \equiv c^m \text{ mod } n$.

-