Results 1 to 4 of 4

Math Help - Fermat's Thm applied

  1. #1
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101

    Fermat's Thm applied

    If gcd(a,35) = 1, show that a^12 equiv/ 1 (mod 35)
    the hint in the book says remember, by Femat's thm: a^6 equiv/1 (mod 7) and a^4 equiv/1 (mod 5)

    So since gcd(a,5) = 1 and gcd(a,7) = 1, you can apply Fermat's them - and prove the hint

    But thats where I'm stuck - is there another theorem I've forgot where you can multiply the exponent and mod???? is it a property I don't remember??

    help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ok - but how do you show that combined - they are the same as 35 -
    I understand how 5 | a^{12} - 1 and  7 | a^{12} - 1 - but how do you put them together?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    One can show that: If a \equiv b \ (\text{mod } m_1) and a \equiv b \ (\text{mod } m_2), then a \equiv b \ (\text{mod } \text{lcd}(m_{1}, m_2) )

    Or if you prefer, purely by definitions:
    5 \mid a^{12} - 1 \ \iff \ a^{12} = 1 + 5k_1 \ \iff 7a^{12} = 7 + 35k_1
    7 \mid a^{12} - 1 \ \iff \ a^{12} = 1 + 7k_2 \ \iff 5a^{12} = 5 + 35k_2

    Add the equations to get: 12a^{12} = 12 + 35(k_1 + k_2) \ \iff 12a^{12} \equiv 12 \ (\text{mod 35})

    Since (12, 35) = 1, we have: a^{12} \equiv 1 \ (\text{mod } 35)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat Quotient
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 1st 2010, 06:49 AM
  2. fermat's little thm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 28th 2009, 10:37 AM
  3. Fermat's
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 24th 2008, 06:36 PM
  4. Fermat pseudoprime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 2nd 2008, 09:15 PM
  5. fermat...or not fermat?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 22nd 2006, 09:16 AM

Search Tags


/mathhelpforum @mathhelpforum