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.

Prove that for every $x \in \mathbb{Z} \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x -2 \equiv 0 \pmod 5$.

I was trying to use induction:

Base case $(x = 3)$: If $3 \equiv 3 \pmod 4$ then $3^3 - 2 \equiv 0 \pmod 5$ holds

Inductive step ($n > 3$): Assume that for every $y$ from $3$ to $x-1$, if $y \equiv 3 \pmod 4$ then $3^y - 2 \equiv 0 \pmod 5$.

But I'm stuck in the inductive step, so not sure if induction is the right way to prove this claim.

share|improve this question
    
Note: when you write "x=y (mod n)", that's incorrect. You mean that x is congruent to y, (mod n). The equal- and congruency-signs look similar, but the difference is important. –  Newb Oct 30 '13 at 1:46
    
Because we are only looking at $x \equiv 3 \pmod{4}$, the induction step goes from $x$ to $x+4$ (or from $x-4$ to $x$, if you prefer). –  hardmath Oct 30 '13 at 2:21

2 Answers 2

up vote 0 down vote accepted

Tom's answer shows how to get the result without induction.

To get it by induction, suppose that $3^{4n+3} \equiv 2 (\mod 5)$.

This is true for $n=0$.

You want to show that $3^{4(n+1)+3} \equiv 2 (\mod 5)$.

$\begin{align} 3^{4(n+1)+3} &=3^{4n+4+3}\\ &=3^{4n+3}3^4\\ &=3^{4n+3}81\\ &\equiv 3^{4n+3} (\mod 5)\\ &\equiv 2(\mod 5)\\ \end{align} $

since $81 \equiv 1 (\mod 5)$.

More generally, since $3^4 = 81 \equiv 1 (\mod 5)$, if $0 \le k < 4$, $3^{4n+k} \equiv 3^k (\mod 5)$ for all $n$ by exactly the same induction proof.

Even more generally, if $a^b \equiv 1 (\mod c)$, if $0 \le k < c$, then $a^{bn+k} \equiv a^k (\mod c)$ for all $n$ by exactly the same induction proof.

Of course this can be directly proved as in Tom's proof by, computing $(\mod c)$, $a^{bn+k} \equiv a^{bn}a^k \equiv (a^b)^na^k \equiv (1)^na^k \equiv a^k $

share|improve this answer
    
But how do you know that $n+1 \equiv 3 \pmod 4$ is true? –  Giovanni Oct 30 '13 at 2:40
    
You don't. Where is this assumed? –  marty cohen Nov 11 '13 at 4:31

If $x \geq 3$ and $x \cong 3$ $\mod 4$ then $x = 4q + 3$ for some integer $q \geq 0$. So, now $3^x = 3^{4q+3} = 27(3^4)^q = 27(81)^q$. Now, what is $27(81)^q$ congruent to $\mod 5$?

share|improve this answer
    
Sorry, it should say $27(81)^q - 2$ congruent to $\mod 5$. But are you suggesting that induction is not the right way to prove this proposition? –  Giovanni Oct 30 '13 at 2:11
    
That's exactly what he's suggesting. –  Dennis Meng Oct 30 '13 at 2:34
    
I'm not saying that induction has no place in this problem. But, I imagine that you have already seen that $(ab)\mod k \cong (a \mod k)(b \mod k)$ and from there used an induction to prove that $(a_1 a_2 \cdots a_n) \mod k \cong (a_1 \mod k)(a_2 \mod k) \cdots (a_n \mod k)$. Once you have shown this general result, then you can do this problem directly (without another induction) by looking at $27(81)^q$ (which if you can show is congruent to $2 \mod 5$ is equivalent to showing $27(81)^q-2$ is congruent to $0 \mod 5$). –  Tom Oct 30 '13 at 11:23

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.