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

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

$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
$a\equiv 2, b\equiv 0,2,4 \mod 6$
$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
$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 $a=b=0$ and then $1 \equiv 1 + 3 (\bmod 9)$ and this is not true.

3. Originally Posted by ThePerfectHacker
Let $a=b=0$ and then $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

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

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

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

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

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

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

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

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

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

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

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

$gcd(2,9)=1$, therefore, $2^6 \equiv 1 ~(\bmod~9) \quad \implies \quad 2^{6k} \equiv 1 ~(\bmod~9)$
$\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 :
$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 $\color{red} \{1\}$.

I hope this helps you...

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

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

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

$
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) $
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 $b\geq{0}$

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

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

Note that: $
2^5 \equiv 5\left( {\bmod .9} \right)
$
,since $
2^{\phi \left( 9 \right)}=2^6 \equiv 1\left( {\bmod .9} \right)

$
it follows that $
a +1= 5 + 6 \cdot k
$
satisfies (1) for all natural numbers $k$ (in fact it must be of that form)

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

6. ## new release

Originally Posted by Moo
Now, you know that a is even. So the only possibilities are :
$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 $\color{red} \{1\}$.
If $a \equiv 0 ~(\bmod~6)$, $a=6k$

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

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

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

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

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

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

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

We want b such that $3 \cdot 2^b \equiv 3 ~(\bmod~9)$. Dividing by 3, we get $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 $2^2 \equiv 1 ~(\bmod~3) \implies 2^r \equiv 1 ~(\bmod~3)$, with $r \equiv 0 ~(\bmod~2)$ *

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

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

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

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

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

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

By dividing by 3 :

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

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

Similarly to above, we get this :

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

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

Therefore, b has to be odd.

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