Results 1 to 5 of 5

Math Help - Modular arithmetic.

  1. #1
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Modular arithmetic.

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

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

    Thanks for any help

    Is it because:

    2^{341}={2^{10}}^{30}*2^{41}\equiv2^{41}={(2^{10})  }^4*2\equiv2mod(341)
    Last edited by hmmmm; March 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
    9,854
    Thanks
    321
    Awards
    1
    Quote Originally Posted by hmmmm View Post
    Why does 2^{10}\equiv1mod(11) and 2^{30}\equiv1mod(31) imply that

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

    Thanks for any help

    Is it because:

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

    and
    \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
    9,854
    Thanks
    321
    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
    9,854
    Thanks
    321
    Awards
    1
    Quote Originally Posted by hmmmm View Post
    Why does 2^{10}\equiv1mod(11) and 2^{30}\equiv1mod(31) imply that

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

    Thanks for any help

    Is it because:

    2^{341}={2^{10}}^{30}*2^{41}\equiv2^{41}={(2^{10})  }^4*2\equiv2mod(341)
    The first case is simple: 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 341 \equiv 11~\text{(mod 30)} \implies 2^{341} \equiv 2^{11}~\text{(mod 31)}. since you are given that 2^{10} \equiv 1~\text{(mod 11)} and 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: March 28th 2010, 05:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 03:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum