1
$\begingroup$

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$

3 Answers 3

0

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

  • 0
    Can you extend on the second part of your answer?2012-10-31
1

Answering my own question:

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.

  • 0
    Okay thanks, I will!2012-10-31
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.

  • 1
    @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 ... ?2012-10-31