# Thread: 2^a 2^b == 2^b+3 (mod 9)

1. ## 2^a 2^b == 2^b+3 (mod 9)

$\displaystyle 2^{a+b}\equiv 2^b+3 \mod9$
I did a case analysis on b mod 6 and found the congruences a has to satisfy, but I don't think my answer is right... Any good resources on modular arithmetic are appreciated also!

EDIT: Sorry, clarification. I am looking for necessary and sufficient conditions that a and b satisfy the congruence. Like I said, I broke into cases on a and b mod 6 and got as my answer
$\displaystyle a\equiv 2, b\equiv 0,2,4 \mod 6$
$\displaystyle a\equiv 4, b\equiv 1,3,5 \mod 6$
but the process is ugly and I don't think I'm right - -;

2. Originally Posted by sleepingcat
$\displaystyle 2^{a+b}\equiv 2^b+3 \mod9$
I did a case analysis on b mod 6 and found the congruences a has to satisfy, but I don't think my answer is right... Any good resources on modular arithmetic are appreciated also!
Let $\displaystyle a=b=0$ and then $\displaystyle 1 \equiv 1 + 3 (\bmod 9)$ and this is not true.

3. Originally Posted by ThePerfectHacker
Let $\displaystyle a=b=0$ and then $\displaystyle 1 \equiv 1 + 3 (\bmod 9)$ and this is not true.
I think the question was to solve for a and b. Would your case exclude all possibilities for some reason?

Thanks.
-Dan

4. Hi

$\displaystyle 2^{a+b} \equiv 2^b+3 ~ (\bmod ~ 9)$

--> $\displaystyle 2^{a+b}-2^b \equiv 3 ~ (\bmod ~ 9)$

$\displaystyle 2^b(2^a-1) \equiv 3 ~ (\bmod ~ 9)$

So one of the conditions will be that $\displaystyle 2^a-1$ is a multiple of 3.

- If a is even, that is to say a=2k, then $\displaystyle 2^a-1=2^{2k}-1=(2^2)^k-1=4^k-1$. But $\displaystyle 4 \equiv 1 ~(\bmod~3)$.

Therefore $\displaystyle 2^a-1 \equiv 1^k-1 ~(\bmod~3)$ << OK.

- If a is odd, that is to say a=2k+1, $\displaystyle 2^a-1=2 \cdot 4^k-1 \equiv 2-1 ~(\bmod~3)$ << NOT OK.

$\displaystyle \implies \boxed{\text{a is even.}}$

------------------------------------------------
Now, $\displaystyle 9=3^2 \quad \implies \quad \varphi(9)=6$.

$\displaystyle \varphi$ denotes Euler's totient function, and is used for Euler's theorem :

if x and n are coprime, then : $\displaystyle x^{\varphi(n)} \equiv 1 ~(\bmod~n)$
This is why you should study the congruences modulo 6.

$\displaystyle gcd(2,9)=1$, therefore, $\displaystyle 2^6 \equiv 1 ~(\bmod~9) \quad \implies \quad 2^{6k} \equiv 1 ~(\bmod~9)$
$\displaystyle \implies \quad \text{if } a \equiv r ~(\bmod~6) ~,~ \textbf{2}^\textbf{a}=2^{r+6k}=2^r \cdot (2^6)^k \equiv \textbf{2}^\textbf{r} ~(\bmod~9) \ {\color{red}\{1\}}$

-----------------------

Now, you know that a is even. So the only possibilities are :
$\displaystyle a \equiv 0~,~2~,~4 ~(\bmod~6)$

And from here, I don't know any other way than trial and errors , and being helped by the property $\displaystyle \color{red} \{1\}$.

I hope this helps you...

5. $\displaystyle 2^{a + b} \equiv 2^b + 3 \equiv 2^b - 6\left( {\bmod .9} \right)$

Thus: $\displaystyle 2^{a + b - 1} \equiv 2^{b - 1} - 3\left( {\bmod .9} \right)$

$\displaystyle 2^{a + b - 1} \equiv 2^{b - 1} - 3 \equiv 2^{b - 1} + 6\left( {\bmod .9} \right)$

$\displaystyle 2^{a + b - 2} \equiv 2^{b - 2} + 3\left( {\bmod .9} \right)$

In fact (we can also go from bottom to top in the above argument) $\displaystyle 2^{a + b} \equiv 2^b + 3\left( {\bmod .9} \right) \Leftrightarrow 2^{a + \left( {b + 2} \right)} \equiv 2^{\left( {b + 2} \right)} + 3\left( {\bmod .9} \right)$ supposing $\displaystyle b\geq{0}$

If $\displaystyle b = 0 \Rightarrow 2^a \equiv 2^0 + 3 \equiv 3\left( {\bmod .9} \right)$ but $\displaystyle 2^a \equiv 1;2;4;5;7;8\left( {\bmod .9} \right)$ (one of those options) for all naturals $\displaystyle a$, thus it is absurd to assume that b is even

If $\displaystyle b = 1 \Rightarrow 2^{a + 1} \equiv 5\left( {\bmod .9} \right)$ (1) which is possible and in fact there are infinitely many $\displaystyle a$ s that satisfy that congruence.

Note that: $\displaystyle 2^5 \equiv 5\left( {\bmod .9} \right)$ ,since $\displaystyle 2^{\phi \left( 9 \right)}=2^6 \equiv 1\left( {\bmod .9} \right)$ it follows that $\displaystyle a +1= 5 + 6 \cdot k$ satisfies (1) for all natural numbers $\displaystyle k$ (in fact it must be of that form)

In conclusion $\displaystyle b$ must be odd and $\displaystyle a = 4 + 6 \cdot k$ for some natural number $\displaystyle k$

6. ## new release

Originally Posted by Moo
Now, you know that a is even. So the only possibilities are :
$\displaystyle a \equiv 0~,~2~,~4 ~(\bmod~6)$

And from here, I don't know any other way than trial and errors , and being helped by the property $\displaystyle \color{red} \{1\}$.
If $\displaystyle a \equiv 0 ~(\bmod~6)$, $\displaystyle a=6k$

$\displaystyle \color{red} \{1\}$ --> $\displaystyle 2^a \equiv 1 ~(\bmod~9) \quad \implies \quad 2^a-1 \equiv 0 ~(\bmod~9) \neq 3 ~(\bmod~9)$

$\displaystyle \implies \boxed{a \not \equiv 0 ~(\bmod~6)}$

--------------------------
If $\displaystyle a \equiv 2 ~(\bmod~6) ~,~ a=6k+2$

$\displaystyle \color{red} \{1\}$ --> $\displaystyle 2^a \equiv 2^2 ~(\bmod~9)$

$\displaystyle \implies 2^a-1 \equiv 3 ~(\bmod~9)$

We want $\displaystyle 2^b(2^a-1) \equiv 3 ~(\bmod~9)$.

$\displaystyle 2^b(2^a-1) \equiv 3 \cdot 2^b ~(\bmod~9)$.

We want b such that $\displaystyle 3 \cdot 2^b \equiv 3 ~(\bmod~9)$. Dividing by 3, we get $\displaystyle 2^b \equiv 1 ~(\bmod~3)$

We can use Euler's theorem (or Fermat's little theorem, since 3 is prime).

2 & 3 are coprime.

So $\displaystyle 2^2 \equiv 1 ~(\bmod~3) \implies 2^r \equiv 1 ~(\bmod~3)$, with $\displaystyle r \equiv 0 ~(\bmod~2)$ *

Therefore $\displaystyle b \equiv 0 ~(\bmod~2)$

$\displaystyle \implies \boxed{(a=2+6k ~,~ b \text{ is even})}$ is solution.

---------------------------
If $\displaystyle a \equiv 4 ~(\bmod~6) ~,~ a=4+6k$

$\displaystyle \color{red} \{1\}$ --> $\displaystyle 2^a \equiv 2^4 ~(\bmod~9) \quad \implies \quad 2^a \equiv 7 ~(\bmod~9)$

$\displaystyle 2^a-1 \equiv 6 ~(\bmod~9)$

We want b such that $\displaystyle 2^b(2^a-1) \equiv 3 ~(\bmod~9)$, that is to say $\displaystyle 6 \cdot 2^b \equiv 3 ~(\bmod~9)$.

By dividing by 3 :

$\displaystyle 2 \cdot 2^b \equiv 1 ~(\bmod~3)$

$\displaystyle 2^{b+1} \equiv 1 ~(\bmod~3)$

Similarly to above, we get this :

$\displaystyle 2^2 \equiv 1 ~(\bmod~3) \implies 2^r \equiv 1 ~(\bmod~3)$, with $\displaystyle r \equiv 0 ~(\bmod~2)$ *

Therefore $\displaystyle b+1 \equiv 0 ~(\bmod~2) \implies b \equiv 1 ~(\bmod~2)$

Therefore, b has to be odd.

$\displaystyle \implies \boxed{(a=4+6k ~,~ b \text{ is odd})}$ is solution.