If $d \equiv 1 \pmod 6$, then how $2^d + 1 \equiv 3 \pmod 9$?

Question

If $d \equiv 1 \pmod 6$, then how $2^d + 1 \equiv 3 \pmod 9$?

and

if $d \equiv 5 \pmod 6$, then how can I derive $2^d + 1 \equiv 6 \pmod 9$ ?

The question is taken from the below solution-

Answer 1

Because $\varphi(9)=6$ and $\gcd(2,9)=1$ we have $2^6\equiv1\pmod{9}$ and hence $$2^d+1\equiv2^1+1\equiv3\pmod{9}\qquad\text{ and } \qquad2^d+1\equiv2^5+6\equiv3\pmod{9},$$ when $d\equiv1\pmod{6}$ and $d\equiv5\pmod{6}$, respectively.

Answer 2

$d \equiv 1 \pmod{6}$, assume that $d$ is written in the form $d=6k+1$ $(k\in\mathbb{Z^+})$. Then we have:

$$2^d+1=2^{6k+1}+1=2^{6k}\times 2+1=64^k\times 2+1$$

Here are the next steps:

\begin{equation}\begin{aligned}64 \equiv 1 \pmod{9} & \Rightarrow 64^k \equiv 1 \pmod{9}\\ &\Rightarrow 64^k\times2 \equiv 2 \pmod{9} \\ &\Rightarrow 64^k\times2+1 \equiv 3 \pmod{9}\\ &\Rightarrow 2^d+1 \equiv 3 \pmod{9}\\ \end{aligned}\end{equation}

Answer 3

Since $d=6k+1$ and $$2^6\equiv_9 8^2 \equiv_9 (-1)^2 \equiv_9 1$$ we have $$2^d+1\equiv_9 2^{6k+1}+1\equiv_9 (2^6)^k\cdot 2+1\equiv_9 (1)^k\cdot 2 +1\equiv_9 3$$

Answer 4

$$ 2^d+1=2^{6k+1}+1=2(2^3)^{2k}+1 = 2(9-1)^{2k}+1 \equiv 3 \mod 9 $$

Answer 5

Note that $2^6=64=9\times7+1\equiv 1 \bmod 9$

From this you obtain $2^{6r}\equiv 1\bmod 9$ by raising both sides to the power $r$.

Now multiply by $2$ and add $1$ to obtain $2^{6r+1}+1\equiv 3 \bmod 9$

If instead you multiply by $2^5= 32\equiv 5 \bmod 9$ and add $1$ you obtain $2^{6r+5}+1\equiv 2^5+1\equiv 5+1\equiv 6\bmod9$

Answer 6

Others are telling you to use Euler's totient, $\varphi(9)=6$. But one should be careful. This is the maximal order of an element, but the order of an element is only required to divide the totient. We should check that the order of $2$ isn't a divisor of $6$. (In the problem you are quoting, this might not matter. If it were (counterfactually) that the order of $2$ was $2$, then $1 \pmod 6$ and $5 \pmod{6}$ would be the same modulo the order. In other problems, this difference could matter.) One way to do this is to check that $2^3 \not \cong 1$, $2^2 \not\cong 1$, and (easy) $2^1 \not\cong 1$, all modulo $6$. Of course, that's half the table of powers of $2$ and mentally doubling is easy, so why not make the full table...

\begin{align*} &d & &2^d \pmod{9} \\ \text{_}&\text{__}&\text{_}&\text{____________}\\ &0 & &1 \\ &1 & &2 \\ &2 & &4 \\ &3 & &8 \\ &4 & &7 \\ &5 & &5 \\ &6 & &1 \end{align*} ... and we've cycled, as expected. So, if you know $d \pmod{6}$, you know $2^d \pmod{9}$. If $d \cong 1 \pmod{6}$, from the table, $2^d \cong 2 \pmod{9}$, and then $2^d + 1 \cong 3 \pmod{9}$. Similarly for the other residue $d$.