5  Euler’s Theorem

Euler’s theorem is a fundamental statement in modular arithmetic. While it may seem daunting at first, this theorem is actually quite simple to understand once you break it down into its component parts.

In this book, the author takes you through the basics of Euler’s theorem step-by-step, explaining everything in a clear and concise manner. The accompanying illustrations are also very helpful, making it easy for beginners to follow along. By the end of the book, you will have a solid understanding of this important theorem and be able to apply it to various real-world scenarios.

Euler’s theorem is a statement in modular arithmetic that says that for any integer a and any prime number p, the congruence relation \(a^\phi(p)\equiv 1 \pmod{p}\) holds. Here, \(\phi(p)\) is Euler’s totient function, which gives the number of positive integers less than or equal to p that are coprime to p. This theorem is named after Leonhard Euler, who proved it in 1736.

Euler’s theorem has several important applications. For instance, it can be used to demonstrate Fermat’s little theorem, which states that for any prime number p and any integer a coprime to p, the congruence relation \(a^{(p-1)}\equiv1 (\pmod{p}\) holds.

Additionally, Euler’s theorem can be used to find modular multiplicative inverses. That is, given an integer a and a modulus m, Euler’s theorem can be used to calculate the modular multiplicative inverse of a modulo m. This is significant because modular multiplicative inverses are essential for many algorithms, such as the Extended Euclidean algorithm and the Chinese remainder theorem.

In summary, Euler’s theorem is an important result with many applications in mathematics and computer science. Overall, Euler’s theorem is a powerful tool that can be used to understand and manipulate numbers in modular arithmetic.

One way to apply Euler’s theorem is to find the modular inverse of a number. Suppose we want to find the modular inverse of 7 (modulo 11). We can use Euler’s theorem to do this as follows: since 7 is relatively prime to 11, we have \(7^10 = 1\) (mod 11). This means that the modular inverse of 7 is 10 (modulo 11).

Euler’s theorem can also be used to solve Congruence equations. For example, suppose we want to solve the equation \(3x \equiv 5 \pmod{7}\). Using Euler’s theorem, we can rewrite this equation as \(3x \equiv 5 \pmod{7} = 3x^6 \equiv 5x^6 \pmod{7}\), which can be further simplified to \(x^6 \equiv 35 \pmod{7}\). This equation can then be solved using modular exponentiation.

Thus, Euler’s theorem has many applications in mathematics and other fields. It is a useful tool for simplifying equations and solving Congruence equations.

Wilson’s theorem states that a natural number n is prime if and only if the factorial of its predecessor is congruent to negative one modulo the number itself. This theorem is named after Edward Wilson, who proved it in 1836.

Wilson’s theorem has a number of applications in cryptography and number theory. For example, it can be used to test whether a given number is prime; if the number passes the test, then it is probably prime, but if it fails, then it definitely isn’t prime. The theorem can also be used to find prime numbers in certain sequences of numbers. In general, Wilson’s theorem is a simple yet powerful tool for working with prime numbers.

In number theory, 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 other words, if we divide \(a^p - a\) by p, the remainder is always zero. This theorem is named after Pierre de Fermat, who first proved it in 1640.

The modular arithmetic properties of primes are important in number theory and have applications to computer science, cryptography, and other areas of mathematics.

For example, modular arithmetic is used in RSA encryption, which is a widely used method of data security. In RSA encryption, two large prime numbers are used to generate a public key and a private key. The public key can be shared with anyone, but the private key must be kept secret. To encrypt a message, the sender uses the recipient’s public key. To decrypt the message, the recipient uses their private key. Fermat’s little theorem is used to ensure that only the intended recipient can decrypt the message; if someone else tries to decrypt the message using the public key, they will not be able to because they do not have the correct private key. Without this security feature, RSA encryption would not be possible.

Fermat’s little theorem is a simple but powerful result with far-reaching implications. It is one of the building blocks of modern number theory and has helped to pave the way for many advances in mathematics and computer science.

Euler’s Totient-Function is a function named after 18th-century mathematician Leonhard Euler, who first described it. Basically, the Totient-Function takes a positive integer as input and outputs how many positive integers less than or equal to the input are relatively prime to the input.

In modular arithmetic, two numbers are said to be relatively prime if they have no common factors other than 1. For example, the numbers 3 and 4 are relatively prime because the only factor they have in common is 1. On the other hand, the numbers 6 and 8 are not relatively prime because they have the common factor 2. The Totient-Function is useful in modular arithmetic because it can be used to find modular inverses.

A modular inverse is an integer that when multiplied by another integer produces 1 modulo some number. For example, the modular inverse of 3 modulo 7 is 5 because 3*5 = 15 and 15 mod 7 = 1. Finding modular inverses can be useful for things like decrypting messages that have been encrypted using the RSA algorithm.

This theorem is extremely important because it allows mathematicians to work with very large numbers by breaking them down into smaller pieces.

For example, suppose we want to find the value of \(2^1000000\) (two to the one-millionth power). This number is too large to calculate directly, but we can use Euler’s Theorem to break it down into smaller pieces. Thus, Euler’s Theorem is a vital tool and without this theorem, many problems would be intractable.

Euler’s Theorem is probably the single most important theorem in modular arithmetic. This book will take you through the basics of Euler’s theorem step-by-step, explaining everything in a clear and concise manner. The accompanying illustrations are also very helpful, making it easy for beginners to follow along. By the end of the book, you will have a solid understanding of this important theorem and be able to apply it to various real-world scenarios. Conclusion

This book is an excellent introduction to Euler’s theorem and would be ideal for anyone who wants to learn more about it. The author takes you through the basics of the theorem step-by-step, explaining everything in a clear and concise manner. The accompanying illustrations are also very helpful, making it easy for beginners to follow along. By the end of the book, you will have a solid understanding of this important theorem and be able to apply it to various real-world scenarios.

5.1 Wilson’s Theorem

This theorem is named after one of Edward Waring’s students, John Wilson. But actually, Wilson only observed the result to be true and did not provide its proof. Later Euler proved Wilson’s theorem and then Gauss gave a generalization. Basically, the theorem states that the factorial of a prime number minus one is congruent to minus one modulo the prime. Interestingly, its converse is also well-known and gives a sufficient condition for an integer to be a prime.

Before we state and prove Wilson’s theorem let’s Illustrate with \(p=13.\)
For \(p=13\) we have \((13-1)!\equiv -1 \pmod{13}\) which we can prove by using the \((13-3)/2\) congruences
\(2\cdot 7 \equiv 1 \pmod{13}\), \(3\cdot 9 \equiv 1 \pmod{13}\),
\(4\cdot 10 \equiv 1 \pmod{13}\),
\(5\cdot 8 \equiv 1 \pmod{13}\), and
\(6\cdot 11 \equiv 1 \pmod{13}\). When these \((13-3)/2\) congruences are multiplied together and the factors are rearranged, we get \(2\cdot 3\cdot 4\cdot \cdot \cdot (13-2)\equiv 1 \pmod{13}\) and thus \((13-2)!\equiv 1 \pmod{13};\) whence \((13-1)!\equiv -1 \pmod{13}\).

Theorem 5.1 [Wilson] If \(p\) is prime, then \((p-1)!\equiv -1 \pmod{p}.\)

Proof. The cases \(p=2\) and \(p=3\) are evident. Choose any integer \(a\) from the list \(1,2,3, ... ,p-1.\) Recall that the linear congruence \(a x\equiv 1 \pmod{p}\) has a unique solution \(x,\) since \((a,p)=1.\) Notice that if \(a x\equiv 1 \pmod{p}\) and \(a=x\) then \(a\equiv \pm 1 \pmod{p}\) and so there are exactly \(\left(\frac{p-3}{2}\right)\) pairs left. If we omit the numbers \(1\) and \(p-1,\) the effect is to group the remaining integers \(2, 3, ... , p-2\) into pairs \(a\) and \(b\) where \(a\neq b,\) such that their product \(a b\equiv 1 \pmod{p}.\) When these \((p-3)/2\) congruences are multiplied together and the factors are rearranged, we get \(2\cdot 3\cdot 4\cdot \cdot \cdot (p-2)\equiv 1 \pmod{p}\) and thus \((p-2)!\equiv 1 \pmod{p};\) whence \((p-1)!\equiv -1 \pmod{p}\) as desired.

Theorem 5.2 [Converse of Wilson’s Theorem] If \(n>2\) is a positive integer such that \((n-1)!\equiv -1 \pmod{n},\) then \(n\) is prime.

Proof. Assume that \(n\) is not prime and \((n-1)!\equiv -1 \pmod{n}\); and so there is some nontrivial factor \(a\) of \(n\) for which \(a|(n-1)!\); whence \(a|1\) since \(n k-(n-1)!=1\) for some integer \(k.\) Therefore, \(a\) can not exist and so \(n\) is prime.

5.2 Fermat’s Theorem

Given a prime number \(p\) and a positive integer \(a\), Fermat’s Theorem says that \(a\) to the \(p-1\) power is congruent to 1 modulo \(p\). Fermat’s Theorem takes care of solving linear congruences with prime modulus and provides a formula for finding the solution.

Example 5.1  

Before stating and proving Fermat’s Theorem let’s consider the congruence \(5^{22}\equiv 1 \pmod{23}.\) To illustrate why this is true, let \(p=23\) and \(a=5\). Notice that \(1\cdot 5 \equiv 5 \pmod{23}\) and see \(\ref{fttab}\) for the other congruences.

Consequently, we have,
\[ \prod _{k=1}^{22} (k\cdot 5)=5^{22}22! \equiv 22! \pmod{23} \] Whence, \(5^{22}\equiv 1 \pmod{23}\).

Theorem 5.3 [Fermat] If \(p\) is prime and \(a\) is a positive integer with \((a,p)=1,\) then \(a^{p-1}\equiv 1 \pmod{p}\)

Proof. Consider the \(p-1\) integers: \(a, 2a, 3a,\)…, \((p-1)a.\) These integers have the following property: if \(r a\equiv s a \pmod{p}\) with \(1\leq r<s\leq p-1,\) then \(r\equiv s \pmod{p}\) because \((a,p)=1.\) Therefore, these integers must be congruent modulo \(p\) to \(1,2,3, ... , p-1\) taken in some order. Multiplying all of these congruence together yields \(a^{p-1}(p-1)!\equiv (p-1)! \pmod{p}\) and since \(((p-1)!,p)=1,\) we have \(a^{p-1}\equiv 1 \pmod{p}\) as desired.

If \(p\) is prime and \(a\) is a positive integer with \((a,p)=1,\) then \(a^p\equiv a \pmod{p}\) follows as well because \(a^{p-1} \equiv 1 \pmod{p}\) and so \(a^p\equiv a \pmod{p}\). If \((a,p)=p\) then \(a^p\equiv a\equiv 0 \pmod{p}\) and so in either case we have \(a^p\equiv a \pmod{p}\).

Example 5.2 Use Fermat’s theorem to solve \(23x\equiv 1 \pmod{53}\).

Solution. Since \(53\) is prime and \((23,53)=1\) we can apply Fermat’s theorem, to find \(23^{52}\equiv 1 \pmod{53}\). Therefore a solution is \(x\equiv 23^{51} \pmod{53}\). Using \(23^{25}\equiv 23 \pmod{53}\), we find the solution to be \(x\equiv 23\cdot 23 \cdot 23 \equiv 30 \pmod{53}\).

Example 5.3 Compute \(2^{340}\) modulo \(341\). Use this to show that the converse of Fermat’s Theorem is not true.

Solution. Since \(2^{340}\equiv 1 \pmod{341}\), if the converse of Fermat’s Theorem were true then \(341\) would be prime. However, \(341=11\cdot 13\) and so the converse of Fermat Little Theorem is not true.

Example 5.4 Show that if \(p\) is a prime and \(a\) is an integer such that \((a,p)=1,\) then \(a^{p-2}\) is an inverse of \(a\) modulo \(p.\)
Find the inverse of \(5\) modulo \(23.\)

Solution. By Fermat’s Theorem we know that \(a^{p-1}\equiv 1 \pmod{p}\) and so \(a\cdot a^{p-2}\equiv 1 \pmod{p}.\) Therefore, \(a^{p-2}\) is an inverse of \(a\) modulo \(p.\)
Since \(5^{22}=5\cdot 5^{21}\equiv \pmod{23}\) and \(5^{21}\equiv 14 \pmod{23}.\) We see that \(5\cdot 14\equiv 1 \pmod{23}\) and so \(14\) is the inverse of \(5\) modulo \(23.\)

Example 5.5 Show that if \(a\) and \(b\) are positive integers and \(p\) is a prime with \((a,p)=1,\) then the solutions of the linear congruence \(a x\equiv b \pmod{p}\) are the integers \(x\) such that \(x\equiv a^{p-2}b \pmod{p}.\)

Example 5.6 Solve the two linear congruences \(4x\equiv 11 \pmod{19}\) and \(5x\equiv 19 \pmod{23}.\)

Solution. Since \(a^{p-2}\) is the inverse of \(a\) modulo \(p\) we have
\[ a x\equiv a\left(a^{-1}b\right)=\left(a a^{p-2}\right)b=a^{p-1}b\equiv b \pmod{p} \] by Fermat’s Theorem.

Example 5.7 By Fermat’s Theorem we have \(4^{18}\equiv 1 \pmod{19}\) and \(5^{22}\equiv 1 \pmod{23}\); so \(x\equiv 4^{17}\cdot 11\equiv 17 \pmod{19}\) is the solution to \(4x\equiv 11 \pmod{19}\) and \(x\equiv 5^{21}\cdot 19\equiv 13 \pmod{23}\) is the solution to \(5x\equiv 19 \pmod{23}.\)

Example 5.8 Show \(p^{q-1}+q^{p-1}\equiv 1 \pmod{p q}\) when \(p\) and \(q\) are distinct primes.

Solution. By Fermat’s Theorem we have \(p^{q-1}\equiv 1 \pmod{q}\) and \(q^{p-1}\equiv 1 \pmod{p}\); thus we consider the system \(x\equiv 1 \pmod{p}\) and \(x\equiv 1 \pmod{q}.\) Using the Chinese Remainder Theorem we have,
\[ x\equiv 1\left(\frac{p q}{q}\right)p^{q-2}+1\left(\frac{p q}{p}\right)q^{q-2} \pmod{p q}. \] Finally since \((p,q)=1\), we have \(x\equiv p^{q-1}+q^{p-1}\equiv 1 \pmod{p q}\) as desired.

5.3 Euler’s \(\phi\)-function

Definition 5.1 For each integer \(n>1,\) let \(\phi (n)\) denote the number of positive integers less than \(n\) and relatively prime to \(n\) and let \(\phi (1)=1.\) The function \(\phi\) is called the totient function, or sometimes, Euler’s \(\phi\)-function.

Euler’s totient function as many amazing properties.
For example, notice that \[\begin{align*} & \phi (13)=13-1=12 \\ & \phi \left(5^3\right)=5^2-5^1=20 \\ & \phi (35)=\phi (5)\phi (7)=(5-1)(7-1)=24. \end{align*}\]

5.3.1 Properties of the Euler Function

Lemma 5.1 If \(p\) is a prime number, then \(\phi (p)=p-1.\)

Proof. Since 1, 2, 3, …, \(p-1\) are relatively prime to the prime \(p,\) \(\phi (p)=p-1.\)

Lemma 5.2 If \(p\) is a prime number, then \(\phi \left(p^r\right)=p^r-p^{r-1}.\)

Proof. By Euclid’s Lemma, the integers \(k\) such that \(1\leq k\leq p^r\) and \(k\) is divisible by \(p\) are \(p, 2p, 3p, ... ,\left(p^{r-1}\right)p.\) Thus the number of positive integers less than \(p^r\) and relatively prime to \(p^r\) is \[ p^r-1-\left(p^{r-1}-1\right)=p^r-p^{r-1} \] as desired.

Lemma 5.3 If \(p\) and \(q\) are distinct primes, then \(\phi (p q)=(p-1)(q-1).\)

Proof. By Euclid’s Lemma, an integer \(k\) will satisfy \((k,p q)>1\) if and only if \(p|k\) or \(q|k\) and the number of such \(k\) is \((p-1)+(q-1).\)
Thus the number of \(k\) such that \((k,p q)=1\) and \(1\leq k<p q\) is \[ p q-1-((p-1)+(q-1))=(p-1)(q-1) \] as desired.

Lemma 5.4 If \((m,n)=1,\) then \(\phi (m n)=\phi (m)\phi (n)\).

Proof. There are \(\phi (n)\) congruence classes which are represented by an integer relatively prime to \(n\) in \(\mathbb{Z}_n.\) Let these representatives be \(a_1, ... ,a_{\phi (n)}.\) The products \(a a_1, ... ,a a_{\phi (n)}\) are all distinct because \((a,n)=1\) and since each product is still relatively prime to \(n,\) there is a representative from each of the \(\phi (n)\) congruence classes \(a_1, ... ,a_{\phi (n)}.\) Therefore,
\[ a_1a_2\cdot \cdot \cdot a_{\phi (n)} \equiv \left(a a_1\right)\left(a a_2\right) \cdots \left(a a_{\phi (n)}\right) \equiv a^{\phi (n)}\left(a_1\cdot \cdot \cdot a_{\phi (n)} \right)\pmod{n}. \] Since \(\left(a_1\cdot \cdot \cdot a_{\phi (n)},n\right)=1,\) we have \(a^{\phi (n)}\equiv 1 \pmod{n}\) as desired.

Theorem 5.4 If \(n=p_1{}^{e_1}p_2{}^{e_2}\cdot \cdot \cdot p_k{}^{e_k}\) is the unique prime factorization of \(n,\) then \[ \phi (n)=\left(p_1{}^{e_1}-p_1{}^{e_1-1}\right)\left(p_2{}^{e_2}-p_2{}^{e_2-1}\right)\cdot \cdot \cdot \left(p_k{}^{e_k}-p_k{}^{e_k-1}\right). \]

Example 5.9 Show that if \(n\) is an odd integer, then \(\phi (4n)=2\phi (n).\)

::: {.proof }[Solution] Since \(n\) is an odd integer \((4,n)=1\) and so \(\phi (4n)=\phi (4)\phi (n)=2\phi (n).\)
:::

Example 5.10 Show that if \(m\) and \(n\) are positive integers then, \(m|n \Longrightarrow \phi (m)|\phi (n).\)

::: {.proof }[Solution] Let \(n=p_1^{e_1}\cdot \cdot \cdot p_s{}^{e_s}\) be the unique prime factorization of \(n.\) Since \(m|n\) we have \(m=p_1{}^{f_1}\cdot \cdot \cdot p_s{}^{f_s}\) where \(0\leq f_i\leq e_i\) for \(i=1,2, ... ,s.\) Using \(\phi \left(p^{\alpha }\right)=p^{\alpha }-p^{\alpha -1}\)
we have
\[\begin{align*} \phi (n) & =\phi \left(p_1^{e_1}\cdot \cdot \cdot p_s^{e_s}\right) \\ & =\phi \left(p_1^{e_1}\right)\cdot \cdot \cdot \phi \left(p_s^{e_s}\right) \\ & =\left(p_1^{e_1}-p_1^{e_1-1}\right)\cdot \cdot \cdot \left(p_s^{e_s}-p_s^{e_s-1}\right) \\ & =p_1^{e_1-1}\left(p_1-1\right)\cdot \cdot \cdot p_s{}^{e_s-1}\left(p_s-1\right) \\ & =p_1^{e_1-f_1}p_1^{f_1-1}\left(p_1-1\right)\cdot \cdot \cdot p_s^{e_s-f_s}p_s{}^{f_s-1}\left(p_s-1\right) \\ & =p_1^{e_1-f_1}\cdot \cdot \cdot p_s{}^{e_s-f_s}p_1^{f_1-1}\left(p_1-1\right)\cdot \cdot \cdot p_s{}^{f_s-1}\left(p_s-1\right) \\ & =p_1^{e_1-f_1}\cdot \cdot \cdot p_s{}^{e_s-f_s}\phi \left(p_1{}^{f_1}\right)\cdot \cdot \cdot \phi \left(p_s{}^{f_s}\right) \\ & =p_1{}^{e_1-f_1}\cdot \cdot \cdot p_s{}^{e_s-f_s}\phi (m) \end{align*}\] Therefore, \(\phi (m)|\phi (n)\) as desired.
:::

5.3.2 Solving Euler Functional Equations

Example 5.11 Solve the functional equation \(\phi (n)=10\).

::: {.proof }[Solution] The claim is that \(n=2^a3^b11^c\) for some integers \(a,b,\) and \(c.\) To see this let \(\alpha\) be the highest power of \(p\) dividing \(n,\) then there is an integer \(k\) with \((p,k)=1\) and \(\phi (n)=\phi \left(p^{\alpha }k\right)=\phi \left(p^{\alpha }\right)\phi (k)=\left(p^{\alpha }-p^{\alpha -1}\right)\phi (k)=p^{\alpha -1}(p-1)\phi (k)=10.\) Since \((p-1)|10\) we must have \(p-1=1,2,5,\) or \(10\) and so \(p=2,3,\) or \(11.\) Now we should try to bound the exponents \(a, b\), and \(c\). Since,
\[\begin{equation} \phi (n)=\phi \left(2^a3^b11^c\right)=\left(2^a-2^{a-1}\right)\left(3^b-3^{b-1}\right)\left(11^c-11^{c-1}\right)=10 \end{equation}\] the exponents \(a, b,\) and \(c\) must be less than or equal to \(2, 1,\) and \(1\) respectively. We tabulate to find the solutions.

\[ \footnotesize \begin{array}{|c|c|c|c|c|} \hline a & b & c & n & \phi (n) \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 11 & 10 \\ 0 & 1 & 0 & 3 & 2 \\ 0 & 1 & 1 & 33 & 20 \\ 0 & 2 & 0 & 9 & 6 \\ 0 & 2 & 1 & 99 & 60 \\ \hline \end{array} \hspace{.5cm} \begin{array}{|c|c|c|c|c|} \hline a & b & c & n & \phi (n) \\ \hline 1 & 0 & 0 & 2 & 1 \\ 1 & 0 & 1 & 22 & 10 \\ 1 & 1 & 0 & 6 & 2 \\ 1 & 1 & 1 & 66 & 20 \\ 1 & 2 & 0 & 18 & 6 \\ 1 & 2 & 1 & 198 & 60 \\ \hline \end{array} \hspace{.5cm} \begin{array}{|c|c|c|c|c|} \hline a & b & c & n & \phi (n) \\ \hline 2 & 0 & 0 & 4 & 2 \\ 2 & 0 & 1 & 44 & 20 \\ 2 & 1 & 0 & 12 & 4 \\ 2 & 1 & 1 & 132 & 40 \\ 2 & 2 & 0 & 36 & 12 \\ 2 & 2 & 1 & 396 & 120 \\ \hline \end{array} \normalsize \] :::

Example 5.12 Solve the functional equation \(\phi (n)=12\). ::: {.proof }[Solution] The claim is that \(n=2^a3^b5^c7^d13^e\) for some integers \(a,b,c,d,\) and \(e.\) To see this let \(\alpha\) be the highest power of \(p\) dividing \(n,\) then \(\phi (n)=12=p^{\alpha -1}(p-1)\phi (k)\) for some integer \(k.\) Since \((p-1)|12\) we must have \(p-1=1,2,3,4,6,12\) and so \(p=2,3,5,7,13.\) Now we should try to bound the exponents if we can. If \(\alpha =2,\) then \(p|12\) and so \(p=2\) or \(p=3.\) Therefore, \(c, d\) and \(e\) must be \(0\) or 1. If \(\alpha =3,\) the \(\left.p^2\right|12\) and so \(p=2.\) Therefore, \(b\) must be 0,1, or 2. If \(a=4,\) then \(\left.p^3\right|12\) and so \(p\neq 2.\) Therefore, \(a\) must be \(3\) or less. If \(p=5,\) then \(12=4\phi (k)\) and so \(\phi (k)=3\) which is not possible. We are left with \(n=2^a3^b7^d13^e\) and \(0\leq a\leq 3,\) \(0\leq b\leq 2\), \(0\leq d\leq 1,\) and \(0\leq e\leq 1.\) These results are summarized in \(\ref{efunc12}\).

:::

5.3.3 Reduced Residue System

Definition 5.2 A reduced residue system modulo \(n\) is a set of \(\phi (n)\) integers such that each element of the set is relatively prime to \(n,\) and no two different elements of the set are congruent modulo \(n.\)

Notice the set \(A=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 \}\) is a reduced residue system modulo 13 since \(A\) contains \(\phi(13)=12\) integers which are all relatively prime with \(13\) and no two integers of \(A\) are congruent modulo \(13\). The set \(B=\{1, 5, 7, 11\}\) is a reduced residue system modulo 12 since \(B\) contains \(\phi(12)=4\) integers which are all relatively prime with \(12\) and no two integers of \(B\) are congruent modulo \(12\). It is not hard to check that the following sets \(C\), \(D\), and \(E\) are each a reduced residue system modulo 28. \[ C=\{1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27\} \] \[ D=\{\pm 1,\pm 3,\pm 5,\pm 9,\pm 11, \pm 13\} %\] \[ \qquad %\text{and}\quad E=\{\pm 5,\pm 15,\pm 25,\pm 45,\pm 55, \pm 65\} \] Notice \(E\) was obtain from \(D\) by multiplying every integer of \(D\) by \(5\).

Lemma 5.5 If \[ \left\{\vlist{r}{{\phi(m)}}\right\} \] is a reduced residue system modulo \(m\) and \((a,m)=1,\) then \[ \left\{\vlist{ar}{{\phi(m)}}\right\} \] is also a reduced residue system modulo \(m.\)

Proof. For \(\left\{\vlist{ar}{{\phi(m)}}\right\}\) to be a reduced residue system modulo \(m\) we need to show that \[\begin{equation} \label{rrset1} a r_i\not \equiv a r_j \qquad \text{ for all } 1\leq i<j\leq \phi (m). \end{equation}\] and \[\begin{equation} \label{rrset2} \left(a r_i,m\right)=1 \qquad \text{ for all } 1\leq i\leq \phi (m) \end{equation}\] To prove \(\ref{rrset1}\), assume the contrary, \(1\leq i<j\leq \phi (m)\) and \(a r_i\equiv a r_j \pmod{m}\). Then \(r_i\equiv r_j \pmod{m}\) because \((a,m)=1\). But \(r_i\equiv r_j \pmod{m}\) can not happen because \(\left\{\vlist{r}{{\phi(m)}}\right\}\) is a reduced residue system modulo \(m\). Therefore, \(a r_i\not \equiv a r_j \pmod{m}\) and so \(\ref{rrset1}\) is proven.

To show \(\ref{rrset2}\) we suppose \(1\leq i\leq \phi (m)\) and that \(p\) is a prime divisor of \(\left(a r_i,m\right)\). Since \(p|m\) we can not have \(p\left|r_i\right.\) because \(\left(r_i,m\right)=1\). It follows that, \(\left(p,r_i\right)=1\) and \(p\left|a r_i.\right.\)
By Euclid’s lemma \(p|a\). Clearly, \(p|a\) and \(p|m\) contradict \((a,m)=1\). Thus there is no prime divisor of \(\left(a r_{i},m\right)\) for any \(1\leq i\leq \phi (m)\) and so \(\ref{rrset2}\) is proven.
Therefore, \(\left\{\vlist{ar}{{\phi(m)}}\right\}\) is also a reduced residue system modulo \(m.\)

5.4 Euler’s Theorem

Theorem 5.5 [Euler] If \((a,m)=1,\) then \[\begin{equation} \label{euler} a^{\phi (m)}\equiv 1 \pmod{m}. \end{equation}\]

Proof. Let \(\left\{\vlist{r}{{\phi(m)}}\right\}\) denote the reduced residue system modulo \(m\) consisting of positive integers less than \(m.\) By \(\ref{lemrrs}\), we know that \[ \left\{\vlist{ar}{{\phi(m)}}\right\} \] is also a reduced residue system modulo \(m.\) Moreover, the integers \(\vlist{r}{{\phi(m)}}\) are congruent to the integers \(\vlist{ar}{{\phi(m)}}\) modulo \(m\) in some order. It follows that
\[ a^{\phi (m)}r_1\cdot r_2 \cdots r_{\phi (m)} \equiv r_1 \cdot r_2 \cdots r_{\phi (m)} \pmod{m} \] and since \(\left(r_1\cdot r_2 \cdots r_{\phi (m)},m\right)=1\) we divide by \(r_1\cdot r_2\cdots r_{\phi (m)}\) to obtain \(\ref{euler}\).

Example 5.13 Prove that the solution to the linear congruence \(a x\equiv b \pmod{m}\) is \(x\equiv a^{\phi (m)-1}b \pmod{m}\) provided \((a,m)=1.\)
Then use Euler’s \(\phi\)-function to solve the linear congruence \(4 x\equiv 781 \pmod{1183}\).

Solution. If \((a,m)=1,\) then by Euler’s theorem \(a^{\phi (m)}\equiv 1 \pmod{m}\) and so multiplying by \(b\) we have \[ a^{\phi (m)}b=a\left(a^{\phi (m)-1}b\right)\equiv b \pmod{m} \] and so \(x\equiv a^{\phi (m)-1}b \pmod{m}\) is a solution. By \(\ref{lincongchar}\), this solution is unique.
To solve the given linear congruence equation notice \((4,1183)=1\), and so by Euler’s theorem, the solution is \(x \equiv a^{\phi (m)-1} b \pmod{m}\) where \(a=4,\) \(m=1183,\) \(b=781,\) and \(\phi (1183)=936\). Therefore the unique solution is \(x\equiv 4^{935}(781)\equiv 491 \pmod{1183}\).

Example 5.14 Find the last digit in the decimal expansion of \[ n=2\cdot(7^{1000})+7\cdot(3^{99,999}). \]

Solution. Since \(\phi (10)=4\) and \(7^{1000}=7^{4(250)},\) by Euler’s Theorem we have, \[ 7^{1000}=\left(7^4\right)^{250} \equiv 1^{250}\equiv 1 \pmod{10}. \] So the last digit in the expansion of \(7^{1000}\) is 1 and thus the last digit in the expansion of \(2\left(7^{1000}\right)\) is of course 2.
Since \(\phi (10)=4\) and \(3^{99,999}=3^{4(24999)+3}\) by Euler’s Theorem we have, \[ 3^{99,999}=\left(3^4\right)^{24999}3^3 \equiv 27\equiv 7 \pmod{10}. \] So the last digit in the expansion of \(3^{99,999}\) is 7 and thus the last digit in the expansion of \(7\left(7^{1000}\right)\) is of course 9. Since the sum of integers with last digit of 2 and last digit of 9 is 1, the last digit of \(2\left(7^{1000}\right)+3^{99,999}\) is 1.

5.5 Exercises

Exercise 5.1 What is the remainder when \(16!\) is divided by 19?

Exercise 5.2 What is the remainder when \(5!\) 25! is divided by 31?

Exercise 5.3 What is the remainder when \(18!\) is divided by 437?

Exercise 5.4 What is the remainder when \(40!\) is divided by 1763?

Exercise 5.5 Find the least positive residue of \(8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\) modulo 7.

Exercise 5.6 Show that \(10!+1\) is divisible by 11 by grouping together pairs of inverses modulo 11 that occur in \(10!.\)

Exercise 5.7 Show that \(12!+1\) is divisible by 13 by grouping together pairs of inverses modulo 13 that occur in \(12!.\)

Exercise 5.8 Show that if \(m\) and \(k\) are positive integers, then \(\phi(m^k)=m^{k-1}\phi(m)\).

Exercise 5.9 Show that if \(p\) is prime then \[ 1^{p-1}+2^{p-1}+3^{p-1}+\cdot \cdot \cdot +(p-1)^{p-1}\equiv -1 \pmod{p}. \]

Exercise 5.10 Show that if \(p>2\) is prime then \[ 1^p+2^p+3^p+\cdot \cdot \cdot +(p-1)^p\equiv 0 \pmod{p}. \]

Exercise 5.11 Show that if \(p\) is prime and \(p\equiv 3 \pmod{4},\) then \[ \left(\frac{p-1}{2}\right)!\equiv \pm 1 \pmod{p}. \]

Exercise 5.12 What is the remainder when \(18!\) is divided by \(437?\)

Exercise 5.13 Use Fermat’s theorem to solve \(23x\equiv 1 \pmod{91}\).

Exercise 5.14 Find the least positive residue of \(9!+10!+11! +12!+13!\) modulo \(11\).

Exercise 5.15 Determine \(\phi (n)\) for \(n=1,2,3,4,5\) and \(6.\)

Exercise 5.16 Show that \(\phi (5186)=\phi (5187)=\phi (5188).\)

Exercise 5.17 Find the least positive residue of \(3^{999,999,999}\) modulo 7 and of \(2^{1,000,000}\) modulo 17.

Exercise 5.18 Use Euler’s theorem to find the least positive residue of \(3^{100,000}\) modulo 35.

Exercise 5.19 Suppose \(p\equiv 3 \pmod{4}\). Show that \((p+1)/4\) is an integer and is the multiplicative inverse of 4 modulo \(p\).

Exercise 5.20 Which is true:

  • if \(m|n\), then \(\phi(m)|\phi(n)\) or
  • if \(\phi(m)|\phi(n)\), then \(m|n\).

Both, neither, or one of them.

Exercise 5.21 Show that if \(m\) and \(k\) are positive integers, then \[ \phi \left(m^k\right)=m^{k-1}\phi (m). \]

Exercise 5.22 Show that if \(a\) and \(m\) are positive integers with \((a,m)=(a-1,m)=1,\) then \[ 1+a+a^2+\cdot \cdot \cdot +a^{\phi (m)-1}\equiv 0 \pmod{ m}. \]

Exercise 5.23 Show that if \(c_1,c_2, ... ,c_{\phi (m)}\) is a reduced residue system modulo \(m,\) where \(m\) is a positive integer greater than 2, then \(c_1+c_2+c_3+\cdots + c_{\phi (m)}\equiv 0 \pmod{m}.\)

Exercise 5.24 Find the value of the Euler phi-function for the given integer.

  • 100
  • 256
  • 1001
  • \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\)
  • \(10!\)
  • \(20!\)

Exercise 5.25 Find all positive integers \(n\) such that \(\phi (n)=6.\)

Exercise 5.26 Find all positive integers \(n\) such that \(\phi (n)=14.\)

Exercise 5.27 Find a reduced residue system modulo for each of the following integers.

  • \(9\)
  • \(10\)
  • \(14\)
  • \(16\)
  • \(17\)

Exercise 5.28 Solve the congruence \(5x\equiv 3 (\text{mod} 14)\) by using Euler’s theorem.

Exercise 5.29 Show that \(\phi (5186)=\phi (5187)=\phi (5188).\)

Exercise 5.30 Show that if \(n\) is an odd integer, then \(\phi (4n)=2\phi (n).\)

Exercise 5.31 Solve the functional equation \(\phi (n)=6\).

Exercise 5.32 Find the second to last digit in the decimal expansion of \(43^{52}.\)

Exercise 5.33 Show that if \(n\) is an odd integer, then \(\phi (4n)=2\phi (n).\)

Exercise 5.34 Solve the functional equation \(\phi (n)=6\).

Exercise 5.35 Show that if \(m\) and \(k\) are positive integers, then \(\phi(m^k)=m^{k-1}\phi(m)\).

Solution. If \(n=p_1{}^{e_1}p_2{}^{e_2}\cdot \cdot \cdot p_k^{e_k}\) is the unique prime factorization of \(n,\) then \[ \phi (n)=\left(p_1^{e_1}-p_1^{e_1-1}\right)\left(p_2^{e_2}-p_2^{e_2-1}\right)\cdot \cdot \cdot \left(p_k^{e_k}-p_k^{e_k-1}\right). \]

Exercise 5.36 Determine which of the following quadratic congruences has solutions \ (a) \(16x^2+5x+1\equiv 0 \pmod{31}\)
\ (b) \(16x^2-5x+1\equiv 0 \pmod{101}\).

Solution. Let \(y=2a x+b\) and \(d=b^2-4 a c,\) then we have a simplified version \(y^2\equiv d \pmod{p}.\)

Exercise 5.37 Let \(p\) be an odd prime. Show that the quadratic congruence equation \(a x^2+bx +c\equiv 0 \pmod{p}\) has a solution if and only if \[\left(\frac{b^2-4ac}{p}\right)=1.\]

Exercise 5.38 Find the second to last digit in the decimal expansion of \(43^{52}.\)

Exercise 5.39 Use Euler’s theorem to find any \(x\) that satisfies the linear congruence equation \(3x\equiv 13 (\text{mod} 17).\)

Exercise 5.40 Determine \(\phi (10440125)\).