This note has been used to help create the
The fundamental theorem of arithmetic states that any positive integer can be uniquely factorized into the form , where are distinct primes, and are positive integers. How many integers are there such that ? This seems difficult to count directly, so instead, consider the integers such that ( are the integers divisible by for some ). Of the integers less than , of them are multiples of . Similarly, of the integers less than are multiples of . However, we have included multiples of in both of these sets, thereby double counting.
The Principle of Inclusion and Exclusion (PIE) is a method to count the number of elements in overlapping sets. For to , let be the set of integers smaller than or equal to that are multiples of . Then the number of integers that are multiples of is . The number of integers that are multiples of is . This holds true in general: for any subset of , the number of integers that are multiples of is .
Then, the set of numbers that satisfy is exactly the set of numbers that are not a multiple of any , hence are not in any of the sets . By the Principle of Inclusion and Exclusion,
The number of integers smaller than that are coprime to is Euler's phi function .
Euler's Theorem: If , then .
Proof: Let be the set of integers that are coprime to . Let be the set of (possibly repeated) integers of the form taken modulo . First, we show that there are no repeats. If there are repeats, i.e., , then Modulo Arithmetic Property H implies . But since every element in is smaller than , this is not possible. Second, we show that is contained within . This is true because given an element of , , so which shows that is an element of . Since is a set of distinct elements contained in , which is also a set of distinct elements, it follows that these sets are the same modulo .
Since the sets contain the exact same elements modulo , the product of all the elements of is equal to the product of all the elements of modulo . Therefore,
Since is coprime to , it follows from Modulo Arithmetic Property H that .
Note: The set is also called a reduced residue system modulo N.
1. What is the units digit of ?
Solution: Finding the units digit of a number is equivalent to working modulo 10. By Euler's theorem, we need only determine the value of the exponent modulo . Again by Euler's theorem, we need only determine the value of the exponent modulo . Then
Note: Another approach is to realize that is the sequence which has period 2. Since the parity of the exponent is odd, this implies the last digit is 9.
2. Calculate (by hand) the value of .
Solution: By Euler's theorem, , implying . In fact, we can do better than this by applying Euler's theorem to and . We know that and , thus . In particular, . Hence,
3. [Fermat's Little Theorem] If is a prime and is an integer, show that .
Solution: Observe that if is a prime, then . Hence, by Euler's Theorem, if , then
What about the values of such that ? In this case, will be a multiple of , so .
Note: This can also be shown by induction on .
4. Show that if is an odd integer, then divides .
Solution: By Euler's Theorem, divides . Since , we have for some integer . Since
it follows that also divides .