Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
I understand how $ac==bd \pmod m$ makes sense, how would I go about proving it? –  Unknown Oct 31 '12 at 18:45
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 ... ? –  Brian M. Scott Oct 31 '12 at 18:46

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.

share|improve this answer
    
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$.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.