Results 1 to 2 of 2

Thread: Is there a quicker way to solve this congruence

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    Is there a quicker way to solve this congruence

    Is $\displaystyle 2^{35} \equiv 1 \textrm{ mod } 561$?

    In the question we were given maple commands to use so I assume we were meant to do it that way. Is there a way to solve this without a calculator?

    I had to use one but just did it like...

    $\displaystyle 2^8 = 256$,
    so $\displaystyle 2^{16} = 450$ mod 561
    and $\displaystyle 2^{32} = (2^{16})^2 = 103$ mod 561...

    Then $\displaystyle 2^{35} = 2^{32} 2^3 = 103 \times 8$ which is not equal to 1 mod 561..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by Deadstar View Post
    Is $\displaystyle 2^{35} \equiv 1 \textrm{ mod } 561$?


    Since $\displaystyle 561=3\cdot 11\cdot 17$ , we can do:

    *** Arithmetic modulo $\displaystyle 3$ : $\displaystyle 2^{35}=(2^3)^{11}\cdot 2^2=2^{11}\cdot 2^2=(2^3)^4\cdot 2=2^4\cdot 2=2^3\cdot 2^2=2^3=2\!\!\!\pmod 3$

    *** Arithmetic modulo $\displaystyle 11$ : $\displaystyle 2^{35}=(2^{11})^3\cdot 2^2=2^3\cdot 2^2=32=10=-1\!\!\!\pmod {11}$

    *** Arithmetic modulo $\displaystyle 17$ : $\displaystyle 2^{35}=(2^{17})^2\cdot 2=2^2\cdot 2=8\!\!\!\pmod {17}$ .


    Well, now use the Chinese Remainder Theorem to find an element $\displaystyle x\in\mathbb{Z}\,\,\,s.t.\,\,\,x=2\!\!\!\pmod 3\,,\,x=-1\!\!\!\pmod {11}\,,\,x=8\!\!\!\pmod{17}$ .

    I found $\displaystyle x=-298=263\!\!\!\pmod{561}\Longrightarrow 2^{35}=263\!\!\!\pmod{561}$ , as you can easily check with any calculator.

    Tonio






    In the question we were given maple commands to use so I assume we were meant to do it that way. Is there a way to solve this without a calculator?

    I had to use one but just did it like...

    $\displaystyle 2^8 = 256$,
    so $\displaystyle 2^{16} = 450$ mod 561
    and $\displaystyle 2^{32} = (2^{16})^2 = 103$ mod 561...

    Then $\displaystyle 2^{35} = 2^{32} 2^3 = 103 \times 8$ which is not equal to 1 mod 561..
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solve linear congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Aug 23rd 2010, 03:50 AM
  2. Solve a Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 7th 2010, 05:35 AM
  3. Solve quad congruence
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 19th 2009, 05:54 AM
  4. How do I solve this congruence?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 19th 2009, 08:08 PM
  5. congruence [I have no idea how to solve this]
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 27th 2008, 04:55 PM

Search Tags


/mathhelpforum @mathhelpforum