Results 1 to 7 of 7
Like Tree1Thanks
  • 1 Post By Deveno

Math Help - Fermat's little theorem (lemma)

  1. #1
    Junior Member froodles01's Avatar
    Joined
    Nov 2011
    From
    Surrey UK
    Posts
    43
    Thanks
    1

    Post Fermat's little theorem (lemma)

    I'm doing Number Theory, completed multiplication, division etc, but now moved on to Fermat's little theorem.
    Having a bit of trouble seeing how to go about a couple of examples I have.
    Generally
    a^(p-1) 1 (mod p)

    where p is a prime number
    & a is an integer

    i) 3^18 divided by 19
    so p=19 & a=3
    3^18 1 (mod 19)
    Hence remainder is 1

    Fine

    ii) 3^55 divided by 19
    but 55 isn't a prime, so how do I do this, please?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    65

    Re: Fermat's little theorem (lemma)

    3^{55}=3(3^{18})^3
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member froodles01's Avatar
    Joined
    Nov 2011
    From
    Surrey UK
    Posts
    43
    Thanks
    1

    Re: Fermat's little theorem (lemma)

    Yes, the example solution tells me this, too & goes on two steps further which is
    = 3 x 1^3
    = 3 (mod19)

    I'm still feeling a bit thick about this.

    why is it 3x . . . . (3^18)^3
    the 3x has me confused, sorry.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    65

    Re: Fermat's little theorem (lemma)

    I'm not sure what you are confused about. Can you clarify?

    Can you see that 3^{55}=3(3^{18})^3?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Fermat's little theorem (lemma)

    the prime number p, in this case, is 19 (what goes in the modulus). the fact that 55 isn't prime isn't relevant.

    what we DO know is that:

    318 = 1 (mod 19) this is FLT with p = 19, a = 3, and p-1 = 18.

    THEN we use the division algorithm to write 55 = 18q + r (divide 55 by 18, and compute the remainder).

    since 18*3 = 54, we get q = 3 and r = 1:

    55 = 18(3) + 1. therefore:

    355 (mod 19)

    = 318(3) + 1 (mod 19)

    = (318(3))(31) (mod 19) (from the rules of exponents)

    = (318)3(3) (mod 19)

    = (318 (mod 19))3(3 (mod 19)) (the usual rules of multiplication still hold mod 19)

    = (1 (mod 19))(3 (mod 19))

    = (1)(3) (mod 19)

    = 3 (mod 19)
    Thanks from froodles01
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member froodles01's Avatar
    Joined
    Nov 2011
    From
    Surrey UK
    Posts
    43
    Thanks
    1

    Re: Fermat's little theorem (lemma)

    Thanks for a brilliant explanation, however I have another similar question I don't seem to be able to finish.
    Could someone help with this please?

    43^43 divided by 17

    FLT is a^p-1 ≡ 1 (mod p)
    & I know that 43 = 2*16+11

    I have used the steps as in above explanation,
    43^43 = 2^16(2) + 11 (mod 17)
    = 2^16(2) + 11 (mod 17)
    = (2^16(2))(2^11) (mod 17)
    = (2^16)^2 (2)^11 (mod 17)
    = (2^16 (mod 17))^2 * (2 (mod 17))^11

    er. . . not quite sure what to do next.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Fermat's little theorem (lemma)

    that's not the method i wrote.

    we have, first of all, 43 = 9 (mod 17) (we reduce "a" mod p).

    so 4343 = 943 (mod 17).

    now 43 = (16)(2) + 11, so

    943 = 9(16)(2) + 11 (mod 17)

    = (916)2(911) (mod 17)

    = (1)2(911) = 911 (mod 17) <---FLT used HERE (with a = 9, and p-1 = 16)

    note we've done two things here: we've reduced the number being exponentiated from 43 to 9, and we've reduced the exponent from 43 to 11.

    from here, we have to do things "the hard way":

    92 = 81 = 13 (mod 17)
    94 = (92)2 = 132 = 169 = 16 = -1 (mod 17)
    98 = (94)2 = 1 (mod 17)

    therefore, 911 = 98+3 = (98)(93) = (1)(93) = 93 (mod 17)

    finally, 93 = (92)(9) = (13)(9) = 117 = 15 (mod 17)

    hence 4343 = 15 (mod 17)
    Last edited by Deveno; May 23rd 2012 at 05:53 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  2. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: February 24th 2010, 06:56 PM
  3. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 28th 2008, 08:15 AM
  4. Fermat's Little Theorem 2
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: October 7th 2008, 06:47 PM
  5. Lemma & Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 17th 2006, 09:53 PM

Search Tags


/mathhelpforum @mathhelpforum