2^a 2^b == 2^b+3 (mod 9)

sleepingcat · #1 $Old$ June 19th, 2008, 06:10 PM

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

ThePerfectHacker · #2 $Old$ June 19th, 2008, 08:24 PM

Quote:

Originally Posted by sleepingcat $View Post$

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

topsquark · #3 $Old$ June 20th, 2008, 05:30 AM

Quote:

Originally Posted by ThePerfectHacker $View Post$

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

Moo · #4 $Old$ June 20th, 2008, 10:36 AM

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 :

Quote:

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...

PaulRS · #5 $Old$ June 20th, 2008, 10:37 AM

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

Moo · #6 $Old$ June 20th, 2008, 11:52 AM

Quote:

Originally Posted by Moo $View Post$

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.