# This note has been used to help create the Euler's Theorem wiki

The fundamental theorem of arithmetic states that any positive integer \( N\) can be uniquely factorized into the form \( N = p_1 ^{q_1} p_2 ^{q_2} \ldots p_n^ {q_n} \), where \( p_i \) are distinct primes, and \( q_i\) are positive integers. How many integers \( 1 \leq k \leq N\) are there such that \( gcd(k, N) =1\)? This seems difficult to count directly, so instead, consider the integers \( 1 \leq k \leq N\) such that \( gcd(k, N)\neq 1\) (\(k\) are the integers divisible by \(p_i\) for some \(i\)). Of the integers less than \( N\), \( \frac {N}{p_1} \) of them are multiples of \( p_1\). Similarly, \( \frac {N}{p_2}\) of the integers less than \(N\) are multiples of \( p_2\). However, we have included multiples of \( p_1 p_2\) 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 \( i=1\) to \( n\), let \( P_i\) be the set of integers smaller than or equal to \( N\) that are multiples of \( p_i\). Then the number of integers that are multiples of \( p_i\) is \( |P_i| = \frac {N}{p_i}\). The number of integers that are multiples of \( p_ip_j\) is \( |P_i \cap P_j| = \frac {N}{p_ip_j}\). This holds true in general: for any subset \( S\) of \( \{ 1, 2, \ldots, n\} \), the number of integers that are multiples of \( \displaystyle \prod_{s\in S} p_s\) is \( \lvert \bigcap_{s\in S} P_s \rvert = \frac {N}{\prod_{s\in S} p_s}\).

Then, the set of numbers that satisfy \( \gcd(k, N)=1\) is exactly the set of numbers that are not a multiple of any \( p_i\), hence are not in any of the sets \( P_i\). By the Principle of Inclusion and Exclusion,

\[ \begin{aligned} N - \big\vert \bigcup_i P_i \big\vert = & N - \sum_{i} \big\vert P_i \big\vert + \sum_{i\neq j} \big\vert P_i \cap P_j \big\vert - \sum_{ i \neq j, j \neq k, k\neq i} \big\vert P_i \cap P_j \cap P_k \big\vert + \ldots + (-1)^n \big\vert \bigcap_i P_i \big\vert \\ = & N - \sum_{i} \frac {N}{p_i} + \sum_{i\neq j} \frac {N}{p_ip_j} - \sum_{ i \neq j, j \neq k, k\neq i} \frac {N}{p_i p_j p_k} + \ldots + (-1)^n \frac {N}{\prod_i p_i} \\ = & N \left( 1-\frac {1}{p_1} \right) \left(1-\frac {1}{p_2} \right) \left( 1-\frac {1}{p_3} \right) \ldots \left( 1-\frac {1}{p_n} \right) \\ \end{aligned} \]

The number of integers smaller than \( N\) that are coprime to \( N\) is **Euler's phi function** \( \phi(N)\).

Euler's Theorem: If \( \gcd (a, N) = 1\), then \( a^{\phi(N)} \equiv 1 \pmod{N}\).Proof: Let \( \mathcal{S}\) be the set of integers that are coprime to \( N\). Let \( a\mathcal{S}\) be the set of (possibly repeated) integers of the form \( \{ as : s \in \mathcal{S} \} \) taken modulo \( N\). First, we show that there are no repeats. If there are repeats, i.e., \( as_i \equiv as_j \pmod{N}\), then Modulo Arithmetic Property H implies \( s_i \equiv s_j \pmod{N}\). But since every element \( s\) in \( \mathcal{S}\) is smaller than \( N\), this is not possible. Second, we show that \( a\mathcal{S}\) is contained within \( \mathcal{S}\). This is true because given \( s\) an element of \( \mathcal{S}\), \( 1\leq \gcd(as, N) \leq \gcd(a,N) \times \gcd (s, N) = 1\times 1 = 1\), so \( \gcd(as, N)=1\) which shows that \( as\) is an element of \( S\). Since \( a\mathcal{S}\) is a set of \( \phi(N)\) distinct elements contained in \( \mathcal{S}\), which is also a set of \( \phi(N)\) distinct elements, it follows that these sets are the same modulo \( N\).

Since the sets contain the exact same elements modulo \( N\), the product of all the elements of \( a\mathcal{S}\) is equal to the product of all the elements of \( \mathcal{S}\) modulo \( N\). Therefore,

\[ as_1 \cdot as_2 \cdot \ldots \cdot as_{\phi(N)} \equiv s_1 \cdot s_2 \cdot \ldots \cdot s_{\phi(N)} \pmod{N}.\]

Since \( s_1 \cdot s_2 \cdot \ldots \cdot s_{\phi(N)} \) is coprime to \( N\), it follows from Modulo Arithmetic Property H that \( a^{\phi(N)} \equiv 1 \pmod{N}\).

Note: The set \( \mathcal{S}\) is also called a reduced residue system modulo N.

## Worked Examples

## 1. What is the units digit of \( {{9^7} ^ 5} ^3 \)?

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 \( {7^5}^3\) modulo \( \phi(10)=10\times(1-\frac {1}{2})\times(1-\frac {1}{5}) = 4\). Again by Euler's theorem, we need only determine the value of the exponent \( {5^3}\) modulo \( \phi(4)=4\times (1-\frac {1}{2})=2\). Then

\[ \begin{aligned} 5^3 &\equiv & 1^3 & \equiv & 1 & \pmod{2} \\ {7^5}^3 &\equiv & 7^1 & \equiv & 3^1 \equiv 3 &\pmod{4}\\ {{9^7}^5}^3 &\equiv & 9^3 & \equiv & 729 \equiv 9 &\pmod{10}\\ \end{aligned}\]

Note: Another approach is to realize that \( 9^n \pmod{10}\) is the sequence \( 9, 1, 9, 1, 9, 1, \ldots\) 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 \( \frac {5}{21}\).

Solution: By Euler's theorem, \( \phi(21)=21\times(1-\frac {1}{3})(1-\frac {1}{7})=12\), implying \( 10^{12}\equiv 1 \pmod{21}\). In fact, we can do better than this by applying Euler's theorem to \( \phi(3)=3\times(1-\frac {1}{3})=2\) and \( \phi(7)=7\times(1-\frac {1}{7}) = 6\). We know that \( 10^6 \equiv (10^2)^3 \equiv 1^3 \equiv 1 \pmod{3}\) and \( 10^6 \equiv 1 \pmod{7}\), thus \( 10^6 \equiv 1 \pmod{21}\). In particular, \( 10^6-1 = 21 \times 47619\). Hence, \[ \frac {5}{21} = \frac {5 \times 47619}{21 \times 47619} = \frac{238095}{999999}=0.238095238095......\]

\( \)

## 3. [Fermat's Little Theorem] If \( p\) is a prime and \( a\) is an integer, show that \( a^p \equiv a \pmod{p}\).

Solution: Observe that if \( p\) is a prime, then \( \phi(p)=p\times (1-\frac {1}{p}) = p-1\). Hence, by Euler's Theorem, if \( \gcd(a,p)=1\), then

\[ a^{p-1} \equiv 1 \pmod{p} \Rightarrow a^p \equiv a \pmod{p}.\]

What about the values of \( a\) such that \( \gcd(a,p)\neq 1\)? In this case, \( a\) will be a multiple of \( p\), so \( a^p \equiv 0^p \equiv 0 \equiv a \pmod{p}\).

Note: This can also be shown by induction on \( a\).

\( \)

## 4. Show that if \( n\) is an odd integer, then \( n\) divides \( 2^{n!} -1\).

Solution: By Euler's Theorem, \( n\) divides \( 2^{\phi(n)}-1\). Since \( \phi(n) < n\), we have \( n! = \phi(n) \cdot k\) for some integer \(k\). Since

\[ 2^{n!}-1 = (2^{\phi(n)}-1)(2^{\phi(n)\cdot(k-1)}+ 2^{\phi(n)\cdot(k-2)}+\ldots + 1),\]

it follows that \( n\) also divides \( 2^{n!}-1\).

## Comments

Sort by:

TopNewestResearches on set notation– Julian Poon · 2 years agoLog in to reply

Nice one but couldn't understood everything stated above. – Tushar Malik · 2 years, 7 months ago

Log in to reply

– Curtis Clement · 1 year, 3 months ago

Yea I think the first part could be explained without the use of the inclusion exclusion principleLog in to reply

– Mardokay Mosazghi · 2 years ago

which part do u need help with?Log in to reply

@Mardokay Mosazghi – Harshi Singh · 1 year, 9 months ago

can you explain the euler phi functionLog in to reply

– Swapnil Das · 1 year, 7 months ago

Its nothing but all the numbers less or equal to and coprime to a number, nothing else!Log in to reply

– Tushar Malik · 2 years ago

The third point in worked examples i.e. Fermat's little theorem.Log in to reply

Cool! :D – Finn Hulse · 2 years, 11 months ago

Log in to reply

Really interesting but one thing I wasn't clear about is that the the phi function of 3 (say) gives the number of integers less the 3 that are coprime to 3 so isn't only 2 the integer that satisfies this property. So the function would give 1 as the output and not 2 as in one of the worked examples? – Sarthak Tanwani · 2 years, 3 months ago

Log in to reply

IN particular, \( \phi (p ) = p-1 \) for all primes \(p\). – Calvin Lin Staff · 2 years, 3 months ago

Log in to reply

– Pranjal Jain · 2 years ago

Is there a wiki? If not, you should add it to wiki. Thanks.Log in to reply

– Sarthak Tanwani · 2 years, 3 months ago

Thanks!Log in to reply

wow....interesting facts – Shaun Yeoh · 2 years, 7 months ago

Log in to reply

Helpful! :-) – Romy Das · 2 years, 9 months ago

Log in to reply