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?

  • 0
    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$.2012-08-27
  • 0
    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.2012-08-27
  • 1
    Then everything is OK, except you should say for every **positive** (or non-negative) $m$.2012-08-27

2 Answers 2