# Prove Base case $P(0)$ with three variables.

I'm studying for a mathematical induction test tomorrow, and I have a practice question:

Use mathematical induction to prove that if $a$ and $b$ are integers with $a \equiv b \pmod m$ then $a^k \equiv b^k \pmod m$ for all $k \ge 0$

So I've tried tackling the base case $P(0)$, since $k$ can equal $0$.

$i=k$

Assume $P(i)$ is true.

Prove $P(i+1)$

$a^{i+1}\equiv b^{i+1} \pmod m$

Base Case: $P(0)$

$a^{i+0}\equiv b^{i+0} \pmod m$

$a^i\equiv b^i \pmod m$ is equal to our original equation.

So $P(0)$ is true.

How can this possibly make sense? I don't understand how we can come to a logical conclusion with an assumption of proof. I do not see how this proves the base case.

Could someone show me how to tackle the inductive step? I'm not even sure where to start once I change $k$ to $i+1$

-

It’s an assumption throughout that $a\equiv b\pmod m$, so the statement $P(k)$ is simply $$P(k):\qquad a^k\equiv b^k\pmod m\;.$$ Thus, the base case, $P(0)$, is just $a^0\equiv b^0\pmod m$, which is certainly true, since $a^0=b^0=1$.

For the induction step you want to assume that $P(i)$ is true for some $i\ge 0$ and show that $P(i+1)$ must then be true. Thus, you’re going to assume that $a^i\equiv b^i\pmod m$, and you’re going to show somehow that $a^{i+1}\equiv b^{i+1}\pmod m$.

Do you already know that if $a\equiv b\pmod m$ and $c\equiv d\pmod m$, then $ac\equiv bd\pmod m$? That’s the fact that you need to carry out the induction step. If you know it, just figure out how to apply it; if not, you’ll need to prove it first.

-
I understand how $ac==bd \pmod m$ makes sense, how would I go about proving it? –  Unknown Oct 31 '12 at 18:45
@Bernie: $ac-bd=ac-ad+ad-bd=a(c-d)+d(a-b)$; since $a\equiv b\pmod m$ and $c\equiv d\pmod m$, you know that $m\mid a-b$ and $m\mid c-d$, so ... ? –  Brian M. Scott Oct 31 '12 at 18:46

I've approached the question wrong.

I'm not supposed to have $i+1$ until after the base case of $0$.

Base case $P(0)$

$a^0==b^0 \pmod m$

$1-1/m$

$0/m$ is possible as long as m is not a zero.

-
In the penultimate line you should write $m\mid 1-1$, and it’s safe to assume that $m\ne 0$: $0$ simply can’t be a modulus. But yes, you’ve found the problem with your original approach. (If you right-click on the expressions in my answer or my edit of your question and select Show Math As > TeX Commands, you’ll see how to get congruences to display properly.) –  Brian M. Scott Oct 31 '12 at 18:45
Okay thanks, I will! –  Unknown Oct 31 '12 at 18:47

As I understand it you have defined $a \equiv b \pmod m$ iff $m | a-b$.

So what we really want to prove is that $m|a-b$ then $m|a^n-b^n$, but given $m|a-b$ we have $m|(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots+b^{n-1})$ which is just $m|a^n-b^n$.

-
Can you extend on the second part of your answer? –  Unknown Oct 31 '12 at 19:32