Results 1 to 6 of 6

Math Help - 2^a 2^b == 2^b+3 (mod 9)

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    16

    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 - -;
    Last edited by sleepingcat; June 20th 2008 at 05:20 AM. Reason: Clarification
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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...
    Last edited by Moo; June 20th 2008 at 08:50 AM. Reason: tiny typo
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    <br />
2^{a + b}  \equiv 2^b  + 3 \equiv 2^b  - 6\left( {\bmod .9} \right)<br />

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

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

    <br />
2^{a + b - 2}  \equiv 2^{b - 2}  + 3\left( {\bmod .9} \right)<br />

    In fact (we can also go from bottom to top in the above argument) <br />
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)<br />
supposing b\geq{0}

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

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

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

    In conclusion b must be odd and <br />
a = 4 + 6 \cdot k<br />
for some natural number k
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6

    new release

    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.




    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum