Results 1 to 5 of 5

Thread: Modular arithmetic.

  1. #1
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Modular arithmetic.

    Why does $\displaystyle 2^{10}\equiv1mod(11)$ and $\displaystyle 2^{30}\equiv1mod(31)$ imply that

    $\displaystyle 2^{341}-2$ is divisible by both 11 and 31?

    Thanks for any help

    Is it because:

    $\displaystyle 2^{341}={2^{10}}^{30}*2^{41}\equiv2^{41}={(2^{10}) }^4*2\equiv2mod(341)$
    Last edited by hmmmm; Mar 10th 2011 at 01:40 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by hmmmm View Post
    Why does $\displaystyle 2^{10}\equiv1mod(11)$ and $\displaystyle 2^{30}\equiv1mod(31)$ imply that

    $\displaystyle 2^{341}-2$ is divisible by both 11 and 31?

    Thanks for any help

    Is it because:

    $\displaystyle 2^{341}={2^{10}}^{30}*2^{41}\equiv2^{41}={(2^{10}) }^4*2\equiv2mod(314)$
    I can't actually answer your question, however
    $\displaystyle \displaystyle 2^{300} \equiv 258~\text{(mod 314)}$

    and
    $\displaystyle \displaystyle 2^{41} \equiv 202~\text{(mod 314)}$

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    sorry I keep doing this it should be 341 not 314 really sorry I have edited the thread
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by hmmmm View Post
    sorry I keep doing this it should be 341 not 314 really sorry I have edited the thread
    (chuckles) I should have caught that myself, I kept trying to put in 341 in my calculator...

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by hmmmm View Post
    Why does $\displaystyle 2^{10}\equiv1mod(11)$ and $\displaystyle 2^{30}\equiv1mod(31)$ imply that

    $\displaystyle 2^{341}-2$ is divisible by both 11 and 31?

    Thanks for any help

    Is it because:

    $\displaystyle 2^{341}={2^{10}}^{30}*2^{41}\equiv2^{41}={(2^{10}) }^4*2\equiv2mod(341)$
    The first case is simple: $\displaystyle 341 \equiv 1~\text{(mod 10)} \implies 2^{341} \equiv 2^{1}~\text{(mod 11)}$

    That's directly by the (slightly more general case of) Fermat's little theorem.

    I'm still working on the next part, but I note that $\displaystyle 341 \equiv 11~\text{(mod 30)} \implies 2^{341} \equiv 2^{11}~\text{(mod 31)}$. since you are given that $\displaystyle 2^{10} \equiv 1~\text{(mod 11)}$ and $\displaystyle 2^{30} \equiv 1~\text{(mod 31)}$ this has the feel of some kind of division algorithm in the works.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 11:07 PM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 01:37 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 28th 2010, 05:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 13th 2008, 03:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum