1

I have this conjecture: Let a and b be integers and n and m natural numbers.

$$ a \equiv b \bmod n \Rightarrow a^m \equiv b^m \bmod n$$

I think I got the induction proof, but I'm having difficulties on how to proof this with well-ordering principle.

J.-E. Pin
  • 40,163
dendritic
  • 315

2 Answers2

3

Let $k$ be the smallest natural number such that $a^k \not\equiv b^k \mod n$ (such a number exists by the well-ordering principle). We have that $a \equiv b \mod n$ (hence $k \ge 2$). If now $a^{k-1} \equiv b^{k-1} \mod n$, then

$$ a^k \equiv a^{k-1} a \equiv b^{k-1} a \equiv b^{k-1} b \equiv b^k \mod n, $$

which contradicts $a^k \not\equiv b^k \mod n$. Hence, $a^{k-1} \not\equiv b^{k-1} \mod n$, and thus $j:=k-1$ is a smaller number with $a^j \not\equiv b^j \mod n$, and since $k \ge 2$, $j$ is a natural number. This contradicts the fact that $k$ was the smallest number with that property.

EDIT: By 'natural number' i mean positive integer.

Cloudscape
  • 5,124
  • Thanks for your answer. I'm still having a little trouble understanding your answer, especially the middle statement. – dendritic Sep 20 '15 at 15:40
  • The middle statement follows from the following theorem: If $a \equiv a' \mod n$ and $b \equiv b' \mod n$, then $ab \equiv a'b' \mod n$. – Cloudscape Sep 20 '15 at 15:42
  • Ohh, I see. Hm, sorry that wasn't in one of our lists of propositions for modulo. – dendritic Sep 20 '15 at 15:46
  • This is proven as follows: If $a \equiv a' \mod n$, then by definition $n|(a - a')$. Analogously, $n|(b - b')$. Since $ab - a'b' = (a - a')b' + (b - b')a$, $n|(ab - a'b')$, and by definition $ab \equiv a'b' \mod n$. – Cloudscape Sep 20 '15 at 15:46
  • @dendritic: As the above is one of the most fundamental theorems for modulo, it would be rewarding to learn it. (Sometimes the theorem is also called 'well-definedness of products modulo a natural number'.) – Cloudscape Sep 20 '15 at 16:07
  • Our professor accidentally duplicated one of the propositions in our list, so that duplicated one must have supposed to be the one you showed me now. But he never told us what the duplicated was supposed to be. – dendritic Sep 20 '15 at 16:08
  • There is also a theorem which is the exact same version for addition (if $a \equiv a' \mod n$ and $b \equiv b' \mod n$, then $a + b \equiv a' + b' \mod n$). If you have had this theorem, it is possible that you've had the other one too. – Cloudscape Sep 20 '15 at 16:10
  • http://homepages.math.uic.edu/~kwhyte/math215/Worksheet215.pdf – dendritic Sep 20 '15 at 16:11
  • In any case, by knowing these two you are going to impress everybody. Just sayin. – Cloudscape Sep 20 '15 at 16:11
  • Looks like you can use 0.17 instead! – Cloudscape Sep 20 '15 at 16:13
  • OK, for the first $\equiv$ sign and the last you need 0.13 and to know that for every $c \in \mathbb R$, $c c^{k-1} = c^k$. – Cloudscape Sep 20 '15 at 16:16
  • Alrighty, thank you for your help! – dendritic Sep 20 '15 at 16:34
1

Notice that

$a^m-b^m=(a-b)\sum\limits_{k=0}^{m-1}a^{m-k-1}b^{k}=(a-b)(a^{m-1}+a^{m-2}b+\ldots+ab^{m-2}+b^{m-1})$

So

$a-b | a^m-b^m $

Kulisty
  • 1,468