Results 1 to 14 of 14

Math Help - congruences

  1. #1
    Junior Member
    Joined
    Mar 2008
    Posts
    33

    congruences

    I'm stuck with the following question
    Show that for each positive integer b, b^{61} \equiv b (mod \, 1001)

    Thank you for your help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    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
    Hello,

    You can take a look at the Chinese remainder theorem , as far as i see your problem, this is the only way i've found to get only elements of solution...


    If you were asked to show that it had a congruence with 1 mod 1001, i would have given you Euler's theorem
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2008
    Posts
    33
    Quote Originally Posted by Moo View Post
    , i would have given you Euler's theorem
    Oh yes, use Euler's Theorem for 2 times, thank you Moo
    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
    Nope, it won't work :s

    Because \varphi(1001)=6*10*12, which is not 61 o.O

    Perhaps you can see what to do, if so that's good for you
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Well 1001=7\cdot{11}\cdot{13}

    Let \theta=\text{lcm}\left(\phi(7),\phi(11),\phi(13)\r  ight)

    You can easily see that
    a^{\theta}\equiv{1}(\bmod.7)
    a^{\theta}\equiv{1}(\bmod.11)
    a^{\theta}\equiv{1}(\bmod.13)

    whenever a is coprime to 1001

    THen it follows (it is easy to prove) that a^{\theta}\equiv{1}(\bmod{1001})

    But: \theta=\text{lcm}\left(6,10,12\right)=60

    THus: a^{60}\equiv{1}(\bmod{1001}) if a is coprime to 1001
    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
    This is the problem... You have to show it for any integer, not coprime oO
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Moo View Post
    You can take a look at the Chinese remainder theorem , as far as i see your problem, this is the only way
    No, you do not need CRT, look at what PaulRS did. If you have x\equiv a(\bmod n_1), x\equiv a(\bmod n_2), .... , x\equiv a_k(\bmod n_k) so that \gcd(n_i,n_j)=1 whenever i\not = j then x\equiv a(\bmod n) where n=n_1\cdot ... \cdot n_k. This is not CRT, just property of relative primeness. CRT only enters when the a's are different for each modolus.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    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
    Oh, i didn't know this thing :-) d'you have a wiki link ?

    Why that :
    THus: a^{60}\equiv{1}(\bmod{1001}) if a is coprime to 1001
    ?

    Thanks !
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Moo
    Oh, i didn't know this thing :-) d'you have a wiki link ?

    Why that :
    Quote Originally Posted by Paul
    THus: a^{60}\equiv{1}(\bmod{1001}) if a is coprime to 1001
    ?

    Thanks !
    (Assuming a is such that \gcd(a,1001)=1).

    Because,
    a^6 \equiv 1(\bmod 7)
    a^{10}\equiv 1(\bmod 11)
    a^{12}\equiv 1(\bmod 13).

    Then,
    (a^6)^{10}\equiv 1^{10}(\bmod 7)
    (a^{10})^6\equiv 1^6(\bmod 11)
    (a^{12})^5\equiv 1^5(\bmod 13).

    Thus.
    a^{60}\equiv 1(\bmod 1001).

    Quote Originally Posted by Moo
    This is the problem... You have to show it for any integer, not coprime oO
    (What does oO mean?)

    But it will not work for any integer. Say a=7 then 7^{60}\not \equiv  7(\bmod 1001) (I just did it on my calculator ).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    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
    oO is a smiley

    That's the problem, the initial text said that it was for any integer... I couldn't verify with my calculator, thanks

    Thus.
    a^{60}\equiv 1(\bmod 1001).
    This implication seems odd to me. I don't see with which theorem/property we can say it (although i agree with the result )
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Moo View Post
    This implication seems odd to me. I don't see with which theorem/property we can say it (although i agree with the result )
    What is so strange? I showed you exactly what happens.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    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
    Well,

    If p & q are coprime, and x = 1 mod p and 1 mod q, why should x be = 1 mod pq ?


    aaah i see, perhaps Bézout's identity could help... need to see it later
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Moo View Post
    Well,

    If p & q are coprime, and x = 1 mod p and 1 mod q, why should x be = 1 mod pq ?


    aaah i see, perhaps Bézout's identity could help... need to see it later
    Let \gcd(p,q)=1 for p,q\in \mathbb{Z}^+.

    If p|a and q|a then pq|a.

    Thus if x\equiv 1(\bmod p) and x\equiv 1(\bmod q) it means p|(x-1) and q|(x-1) so pq|(x-1) thus x\equiv 1(\bmod pq).

    oO
    Follow Math Help Forum on Facebook and Google+

  14. #14
    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
    Ok, now it's all clear !



    Oo oO O.o o.O
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruences
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 11th 2010, 12:52 PM
  2. Congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 7th 2009, 02:26 PM
  3. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 18th 2009, 05:12 AM
  4. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 17th 2009, 10:40 PM
  5. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum