Math Tutorial of the Day:
Number Theory - Fermat's Little Theorem (FLT)
Concept: Fermat's little theorem states that if p is a prime number, then for any integer a, the number a^p − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
a^p = a mod p
For example, if a = 2 and p = 7, then 2^7 = 128, and 128 − 2 = 126 = 7 × 18 is an integer multiple of 7.
If a is not divisible by p, Fermat's little theorem is equivalent to the statement that a^(p - 1) - 1 is an integer multiple of p. In symbols, it is expressed as
a^(p - 1) = 1 mod p.
For example, if a = 2 and p = 7, then 2^6 = 64 - 1 = 63 which is a multiple of 7.
This theorem is named after Pierre de Fermat, who stated it in 1640. It is called the "little theorem" to distinguish it from Fermat's last theorem.
NOTE: mod means remainder. 25 mod 8 = 1 since 25 divided by 8 is 3 remainder 1. Just get the remainder :)
Further Examples:
1. Find the value of 3^13 mod 11.
Solution:
Since 13 is not divisible by 11, we will proceed to the 2nd statement above. 11 - 1 = 10. Therefore, 3^10 = 1 mod 11.
Then, divide 13 by 11 and get the remainder. What we are doing is that we are reducing the exponent to a smaller value.
13/11 = 1 remainder 2
This will become 3^3 mod 11 = 27 mod 11 = 5.
2. If today is Sunday, what day of the week will it be 5^2018 days from now?
Solution:
There are 7 days in a week. Therefore, we need to get the value of 5^2018 mod 7. Then add it to Sunday.
Using FLT, 7 - 1 = 6, therefore, 5^6 = 1 mod 7.
Then divide the exponent by 6 and get the remainder.
2018 mod 6 = 2. [Since 2018/6 = 336 remainder 2]
We reduce then the exponent to 2.
5^2 mod 7 = 25 mod 7 = 4.
Sunday + 4 = Thursday. :)
Try these simple exercises.
1. Find the value of 2^2019 mod 13.
2. Suppose there are only 5 days in a week (Monday, Tuesday, Wednesday, Thursday and Friday) and today is Friday. What day of the week will it be 2019^2018 days from now?
Sharing is caring :) <3
-Isaiah James Maling, 2019-
