# Fermat's little theorem (lemma)

• May 3rd 2012, 04:24 AM
froodles01
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?
• May 3rd 2012, 05:09 AM
a tutor
Re: Fermat's little theorem (lemma)
$3^{55}=3(3^{18})^3$
• May 3rd 2012, 05:44 AM
froodles01
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)

why is it 3x . . . . (3^18)^3
the 3x has me confused, sorry.
• May 3rd 2012, 06:23 AM
a tutor
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$?
• May 3rd 2012, 06:47 AM
Deveno
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)
• May 23rd 2012, 03:01 AM
froodles01
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.
• May 23rd 2012, 06:50 AM
Deveno
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)