1
$\begingroup$

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?

  • 1
    Then everything is OK, except you should say for every **positive** (or non-negative) $m$.2012-08-27

2 Answers 2

3

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$

0

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