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?

Re: Fermat's little theorem (lemma)

$\displaystyle 3^{55}=3(3^{18})^3$

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.

Re: Fermat's little theorem (lemma)

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

Can you see that $\displaystyle 3^{55}=3(3^{18})^3$?

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:

3^{18} = 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:

3^{55} (mod 19)

= 3^{18(3) + 1} (mod 19)

= (3^{18(3)})(3^{1}) (mod 19) (from the rules of exponents)

= (3^{18})^{3}(3) (mod 19)

= (3^{18} (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)

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.

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 43^{43} = 9^{43} (mod 17).

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

9^{43} = 9^{(16)(2) + 11} (mod 17)

= (9^{16})^{2}(9^{11}) (mod 17)

= (1)^{2}(9^{11}) = 9^{11} (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":

9^{2} = 81 = 13 (mod 17)

9^{4} = (9^{2})^{2} = 13^{2} = 169 = 16 = -1 (mod 17)

9^{8} = (9^{4})^{2} = 1 (mod 17)

therefore, 9^{11} = 9^{8+3} = (9^{8})(9^{3}) = (1)(9^{3}) = 9^{3} (mod 17)

finally, 9^{3} = (9^{2})(9) = (13)(9) = 117 = 15 (mod 17)

hence 43^{43} = 15 (mod 17)