Results 1 to 4 of 4

Math Help - Fermat's Little Theorem Help

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    51

    Question Fermat's Little Theorem Help

    Hi all,

    I am kind of stuck with these proofs, which seemingly involve FLT ultimately. Since they're more or less related, I'm posting all three:

    Let a be some integer. Prove that (let == be the symbol for congruence):

    - a^21 == a (mod 15)
    - a^7 == a (mod 42)
    - if gcd(a,35) = 1 (i.e., a and 35 are coprimes), then a^12 == 1 (mod 35)

    After tinkering with the problems a bit, I suspect that the solution involves the GCD of the exponent and the modulus. So, more specifically, I'd like help specially in rewriting the congruences so that the modulus is prime, while keeping it true. That the modulus is prime is obviously required by the FLT hypotesis.

    Any help or tip for one or more of the proofs will be greatly appreciated. Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Notice that \mathbb{Z}_{35}^{\times} \simeq \mathbb{Z}_{5}^{\times} \times \mathbb{Z}_7^{\times} \simeq \mathbb{Z}_4 \times \mathbb{Z}_6

    The group \mathbb{Z}_4 \times \mathbb{Z}_6 has property than anything raised to 12 gives the identity element. Therefore, if \gcd(a,35)=1 then [a]_{35}\in \mathbb{Z}_{35}^{\times}. It follows that [a]_{35}^{12} = [1]_{35} i.e. a^{12}\equiv 1(\bmod 35)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    \color{red}(*) first note that if d \mid n, then a^d - 1 \mid a^n - 1.

    Quote Originally Posted by Rafael Almeida View Post

    a^21 == a (mod 15)
    by FLT: 5 \mid a^5 - a. but: a^5-a=a(a^4 - 1) \mid a(a^{20}-1)=a^{21} - a. hence: 5 \mid a^{21} - a. \ \ \ (1)

    by FLT:  3 \mid a^3 - a. but: a^3 - a = a(a^2 - 1) \mid a(a^{20}-1)=a^{21}-a. hence: 3 \mid a^{21} - a. \ \ \ (2).

    now (1) and (2) complete the proof.


    a^7 == a (mod 42)
    by FLT: 7 \mid a^7 - a. again by FLT: 2 \mid a^2 -a =a(a-1) \mid a(a^6-1)=a^7 - a, and 3 \mid a^3 - a =a(a^2 -1) \mid a(a^6 -1) = a^7 - a. so: 42=2 \times 3 \times 7 \mid a^7 - a.


    if gcd(a,35) = 1 (i.e., a and 35 are coprimes), then a^12 == 1 (mod 35)
    since \gcd(a,5)=1, by FLT we have: 5 \mid a^4 - 1. but a^4 -1 \mid a^{12}-1. thus: 5 \mid a^{12} - 1. \ \ \ (1)

    since \gcd(a,7)=1, by FLT we have: 7 \mid a^6 - 1. but: a^6 - 1 \mid a^{12} - 1. thus: 7 \mid a^{12} - 1. \ \ \ (2)

    now (1) and (2) complete the proof.

    Q.E.D.
    Last edited by NonCommAlg; October 26th 2008 at 04:35 PM. Reason: it's FLT not LFT! lol
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2008
    Posts
    51
    Thank you two, this solves it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermatís Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2011, 06:52 PM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2010, 01:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 09:47 PM
  5. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 28th 2008, 08:15 AM

Search Tags


/mathhelpforum @mathhelpforum