Results 1 to 6 of 6

Thread: 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)

    $\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 - -;
    Last edited by sleepingcat; Jun 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
    10
    Quote Originally Posted by sleepingcat View Post
    $\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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    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
    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

    $\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...
    Last edited by Moo; Jun 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
    $\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$
    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 :
    $\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.




    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum