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

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.

-
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

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$

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

-
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