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?
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)
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.
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)