Skip to main content

Section 4.5 Greatest Common Divisor

The greatest common divisor has many applications. For example, in public key encryption the encoding and decoding keys need to be coprime and the algorithm requires finding solutions to \(a \otimes x = 1\) in \(\mathbb{Z}_n\) (introduced in Section 4.3), which also uses the greatest common divisor. The greatest common divisor also has applications
 1 
Google. Response to "What are some applications of the greatest common divisor?" Gemini 1.0, September 14, 2025.
to scheduling, synchronization, and resource allocation.

Subsection 4.5.A Greatest Common Divisor

We begin with the definition.

Definition 4.5.1 Greatest common divisor.

 
  1. For integers \(a\) and \(b\text{,}\) a common divisor of \(a\) and \(b\) is an integer \(d\) such that \(d \mid a\) and \(d \mid b\text{.}\) For example, the integer three is a common divisor of 12 and 18.
  2. For integers \(a\) and \(b\text{,}\) not both 0, the greatest common divisor of \(a\) and \(b\text{,}\) denoted \(\str{gcd}\)\((a,b)\text{,}\) is the largest integer dividing both \(a\) and \(b\text{.}\) For example, in Example 4.5.2 we show that \(\str{gcd}\)\((4,6)= 2\) and \(\str{gcd}\)\((6,15)=3\text{.}\)
  3. Note that the integer one is always a common divisor of any integers \(a\) and \(b\text{,}\) and so \(\gcd(a,b)\ge 1\text{.}\) It is possible for \(\gcd(a,b)=1\) if \(\pm 1\) are the only common divisors of \(a\) and \(b\text{.}\) If \(\gcd(a,b)=1\text{,}\) then \(a\) and \(b\) are coprime (or relatively prime). For example, in Example 4.5.2 we show that 4 and 15 are coprime. Recall that a fraction is in lowest terms if its numerator and denominator are coprime, as in Definition 4.1.16.
Let’s use the definition to find the greatest common divisor.

Example 4.5.2 Calculating \(\fn{gcd}\) by listing divisors.

Find each greatest common divisor by listing the divisors and common divisors.
  1. \(\str{gcd}\)\((4,6)\)
    Solution.
    Table 4.5.3 lists the divisors of 4 and 6. Their common divisors are \(\pm 1\) and \(\pm 2\text{.}\) The greatest of their common divisors is \(\str{gcd}\)\((4,6)= 2\text{.}\)
    Table 4.5.3. Divisors of 4, 6, and 15
    divisors of 4: \(\pm\)1, \(\pm\)2, \(\pm\)4
    divisors of 6: \(\pm\)1, \(\pm\)2, \(\pm\)3, \(\pm\)6
    divisors of 15: \(\pm\)1, \(\pm\)3, \(\pm\)5, \(\pm\)15
  2. \(\str{gcd}\)\((6,15)\)
    Solution.
    Similarly, Table 4.5.3 lists the divisors of 6 and 15. Their common divisors are \(\pm 1\) and \(\pm 3\text{.}\) The greatest of their common divisors is \(\str{gcd}\)\((6,15)=3\text{.}\)
  3. \(\str{gcd}\)\((4,15)\)
    Solution.
    Table 4.5.3 lists the divisors of 4 and 15. Their common divisors are \(\pm 1\text{.}\) The greatest of their common divisors is \(\str{gcd}\)\((4,15)=1\text{.}\)
Try calculating greatest common divisors.

Activity 4.5.A Greatest common divisor.

Do not use computational technology except to check.
  1. Calculate \(\str{gcd}\)\((75,10)\) by listing the divisors and common divisors.
  2. Show that 15 and 22 are coprime by listing the divisors and common divisors.
  3. Find an example of two odd integers that are coprime.
  4. Find an example of two odd integers that are not coprime.
  5. Can two even integers be coprime? Explain.
Note that listing all divisors of an integer is computationally nontrivial for large integers, and so this method for finding the greatest common divisor is not efficient. As we saw in Subsection 4.4.C, we can list the divisors of an integer from its prime factorization. Therefore, it is possible to compute the greatest common divisor of two integers from their prime factorizations. Note that finding the prime factorization of an integer is computationally nontrivial for large integers, and so this method for finding the greatest common divisor is also not efficient. Let’s look at an example anyway.

Example 4.5.5 Using prime factorization to calculate \(\fn{gcd}\).

Use the prime factorization of \(252 = 2^2 \cdot 3^2 \cdot 7\) and \(3,000 = 2^3 \cdot 3 \cdot 5^2\) to calculate \(\fn{gcd}(252,3000)\text{.}\)
Solution.
The positive divisors of 252 are integers of the form \(2^a \cdot 3^b \cdot 7^c\) where \(a = 0,1,2\text{,}\) \(b=0,1,2\text{,}\) and \(c=0,1\text{.}\) The positive divisors of 3,000 are integers of the form \(2^a \cdot 3^b \cdot 5^c\) where \(a=0,1,2,3\text{,}\) \(b=0,1\text{,}\) and \(c=0,1,2\text{.}\) Observe that \(5 \nmid 252\text{.}\) Therefore, no divisor of 252 is divisible by five. Similarly, \(7 \nmid 3,00\text{.}\) Therefore, no divisor of 3,000 is divisible by seven. The only other prime divisors are two and three, so the common divisors of 252 and 3,000 are integers of the form \(2^a \cdot 3^b\text{.}\) The highest power of two that divides 252 is \(2^2\) and the highest power of three that divides 3,000 is \(3^1\text{.}\) Therefore, \(a \le 2\) and \(b \le 1\text{.}\) The largest such integer is \(2^2 \cdot 3 = 12\text{.}\) Thus, \(\fn{gcd}(252,3000)=12\text{.}\)

Subsection 4.5.B The Euclidean Algorithm

The greatest common divisor is useful but difficult to compute directly, either by listing the divisors or by finding and using the prime factorizations. Fortunately, there is an efficient algorithm for computing the greatest common divisor, the Euclidean Algorithm. The Euclidean Algorithm is certainly on any top ten list of mathematical algorithms of all time
 2 
Others on my list include Newton’s Method (for approximating roots of differentiable functions), Gauss-Jordan Elimination (for solving systems of linear equations), the Simplex Method (for linear optimization), Metropolis Algorithm (and Monte Carlo Markov Chain methods) for optimization in general, QR Algorithm (for finding eigenvalues), Fast Fourier Transforms (for writing functions as sums of periodic functions), Dijkstra’s Algorithm (for finding minimum spanning trees in a graph), RSA Encription Algorithm (for public key cryptosystems), Data Compression Algorithms (for example using Singular Value Decomposition), not to mention a host of computer science algorithms such as quicksort and other sorting algorithms.
and is one of the oldest, dating back to Euclid (circa 300 BCE).
What drives the Euclidean Algorithm are the following key observations.
We leave the proofs of these observations for Exercise 44.(c) and Exercise 18. The algorithm repeatedly applies Theorem 4.5.6 (a), which by (b) gives smaller positive remainders at each step. After a finite number of steps, we are left with zero, which allows us to stop by (c).
Here is an example using the Euclidean Algorithm.

Example 4.5.7 Using the Euclidean Algorithm.

Use the Euclidean Algorithm to calculate \(\fn{gcd}(240,100)\text{.}\)
Solution.
First, divide 240 by 100 to get
\begin{equation*} 240 ~\fn{mod}~ 100 =40\text{.} \end{equation*}
By Theorem 4.5.6 (a), it follows that \(\fn{gcd}(240,100)=\fn{gcd}(100,40)\text{.}\)
Next, divide 100 by 40 to get
\begin{equation*} 100 ~\fn{mod}~ 40 =20\text{.} \end{equation*}
By Theorem 4.5.6 (a), it follows that \(\fn{gcd}(100,40)=\fn{gcd}(40,20)\text{.}\)
Last, divide 40 by 20 to get
\begin{equation*} 40 ~\fn{mod}~ 20 =0\text{.} \end{equation*}
By Theorem 4.5.6 (a) and (c), it follows that \(\fn{gcd}(40,20)=\fn{gcd}(20,0)=20\text{.}\)
Therefore, \(\fn{gcd}(240,100)=20\text{.}\)
Practice using the Euclidean Algorithm.

Activity 4.5.B Euclidean Algorithm.

Do not use computational technology except to check.
  1. When we use the Euclidean Algorithm to calculate \(\str{gcd}\)\((22,15)\) we get \(22 ~\fn{mod}~ 15 = 7\) \(15 ~\fn{mod}~ 7 = 1\) \(7 ~\fn{mod}~ 1 = 0\) Write the corresponding statement about \(\str{gcd}\) for each step and state the final answer.
  2. Use the Euclidean Algorithm to calculate \(\str{gcd}\)\((600,36)\text{.}\) Hint: \(16 \cdot 36 = 576\)

Subsection 4.5.C Coprime Integers

Many of the applications of the greatest common divisor use coprimality. The Euclidean Algorithm provides an efficient way to check if two integers are coprime, but we start with an example exploring how the prime factors can be used to determine if two integers are coprime to illustrate some of the theory.

Example 4.5.9 Showing two integers are coprime using their prime factors.

 
  1. Explain why distinct primes \(p\) and \(q\) are coprime.
    Solution.
    The positive divisors of \(p\) are 1 and \(p\text{,}\) while the positive divisors of \(q\) are 1 and \(q\text{.}\) Since \(p \neq q\text{,}\) their only common positive divisor is 1 and so \(\fn{gcd}(p,q)=1\text{.}\)
  2. Explain why the integers \(p^a\) and \(q^b\) are coprime when \(p\) and \(q\) are distinct primes.
    Solution.
    The positive divisors of \(p^a\) are 1, \(p\text{,}\) \(p^2\text{,}\) … \(p^a\) while the positive divisors of \(q^b\) are 1, \(q\text{,}\) \(q^2\text{,}\) …, \(q^b\text{.}\) Since \(p \neq q\) are primes, it follows from the uniqueness of prime factorization Theorem 4.4.11 that the only common positive divisor of \(p\) and \(q\) is 1 and so \(\fn{gcd}(p^a,q^b)=1\text{.}\)
  3. Explain why if \(n\) is odd, then 16 and \(n\) are coprime.
    Solution.
    The divisors of 16 are \(\pm1\text{,}\) \(\pm2\text{,}\) \(\pm4\text{,}\) \(\pm8\text{,}\) and \(\pm16\text{.}\) Since \(n\) is odd, we know \(2 \nmid n\text{.}\) By Theorem 4.4.4 (a), it follows that no even integer divides \(n\text{.}\) All divisors of 16 are even, except for \(\pm1\text{.}\) Therefore, the only common divisors of 16 and \(n\) are \(\pm1\) and so \(\fn{gcd}(16,n)=1\text{.}\)
  4. Explain why if \(3 \nmid n\) and \(5 \nmid n\text{,}\) then 15 and \(n\) are coprime.
    Solution.
    The only positive divisors of 15 are 1, 3, 5, and 15. Since \(3 \nmid n\) and \(5 \nmid n\text{,}\) it follows that also \(15 \nmid n\) and so the only common positive divisor of 15 and \(n\) is 1.
It is interesting (and useful) to count the number of integers less than \(n\) that are coprime to \(n\text{.}\) We begin with a definition.

Definition 4.5.10 Euler’s totient.

The number of integers from 1 to \(n\) that are coprime to \(n\) is denoted \(\varphi(n)\text{.}\) In this context, \(\varphi\) is Euler’s toitent (or Euler’s \(\varphi\) function).
 3 
\(\varphi\) is the Greek letter phi, sometimes written as \(\phi\text{.}\)
We compute \(\varphi(15)\) as an example.

Example 4.5.11 Calculating \(\varphi(15)\).

 
  1. Copy the list of integers
    \begin{equation*} 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\text{.} \end{equation*}
    Cross off all multiples of three on that list. Cross off all multiples of five on that list. Circle the remaining integers.
    Solution.
    The multiples of three are 3, 6, 9, 12, and 15. The multiples of five are 5, 10, and 15 again.
    \begin{equation*} \cancel{1},\underline{2},\cancel{3},\underline{4},\cancel{5},\cancel{6},\underline{7},\underline{8},\cancel{9},\cancel{10}, \underline{11},\cancel{12},\underline{13},\underline{14},\cancel{15} \end{equation*}
  2. Calculate \(\varphi(15)\)
    Solution.
    By Example 4.5.9 (d) these circled integers from (a) are coprime to 15. Thus, the integers from one to 15 that are coprime to 15 are
    \begin{equation*} 1, 2, 4, 7, 8, 11, 13, 14\text{.} \end{equation*}
    Since there are eight numbers on this list, it follows that \(\varphi(15)=8\text{.}\)
Your turn to practice working with Euler’s toitent.

Activity 4.5.C Euler’s phi function.

 
  1. Explain why if \(2 \nmid n\text{,}\) then \(\fn{gcd}(2,n)=1\text{.}\)
  2. Copy the list of integers
    \begin{equation*} 1,2,3,4,5,6,7,8\text{.} \end{equation*}
    Cross off all multiples of two on that list. Circle the remaining integers, which are not divisible by two and, therefore, are coprime to 8. Count to evaluate \(\varphi(8)\text{.}\)
  3. Explain why if \(2 \nmid n\) and \(5 \nmid n\text{,}\) then \(\fn{gcd}(10,n)=1\text{.}\)
  4. Copy the list of integers
    \begin{equation*} 1,2,3,4,5,6,7,8,9,10\text{.} \end{equation*}
    Cross off all multiples of two and all multiples of five on that list. Circle the remaining integers, which are not divisible by two or five and, therefore, are coprime to 10. Count to evaluate \(\varphi(10)\text{.}\)
  5. Copy the list of integers
    \begin{equation*} 1,2,3,4,5,6,7,8,9,10,11,12\text{.} \end{equation*}
    Use the method from (b) and (d) to find the list of integers coprime to 12 and evaluate \(\varphi(12)\text{.}\)
  6. Copy the list of integers
    \begin{equation*} 1,2,3,4,5,6,7\text{.} \end{equation*}
    Use the method from (b) and (d) to find the list of integers coprime to seven and evaluate \(\varphi(7)\text{.}\)
  7. Table 4.5.13 shows the values of \(\varphi(n)\) for \(n=1,2,\ldots, 16\text{.}\) Check your answers for \(\varphi(8)\text{,}\) \(\varphi(10)\text{,}\) \(\varphi(12)\text{,}\) and \(\varphi(7)\text{.}\)
    Table 4.5.13. The values of \(\varphi(n)\) for \(n=1,2, \ldots, 16\)
    \(n\) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
    \(\varphi(n)\) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8
  8. Conjecture a formula for \(\varphi(2^k)\text{.}\) Check your conjecture for \(n=32\) by listing the integers from 1 to 32, crossing off the integers that are not coprime to 32, circling the remaining integers that are coprime to 32, and counting to evaluate \(\varphi(32)\text{.}\)
  9. Conjecture a formula for \(\varphi(3^k)\text{.}\) Test your conjecture for \(n=27\) by listing the integers from 1 to 27, crossing off the integers that are not coprime to 27, circling the remaining integers that are coprime to 27, and counting to evaluate \(\varphi(27)\text{.}\)

Subsection 4.5.D Exercises

Subsubsection Exercises for 4.5.A Greatest Common Divisor

1. Practice.

Calculate each greatest common divisor by listing the divisors and common divisors. Do not use computational technology.
  1. Calculate \(\str{gcd}\)\((12,18)\) by listing the divisors and common divisors.
  2. Calculate \(\str{gcd}\)\((7,21)\) by listing the divisors and common divisors.
  3. Calculate \(\str{gcd}\)\((5,7)\) by listing the divisors and common divisors.
Check.
  1. Hint: \(\str{gcd}\)\((12,18)=6\text{.}\)
  2. Hint: The only divisors of 7 are \(\pm1, \pm 7\text{.}\)
  3. Hint: They are coprime.

2. Practice.

Show each pair of integers is coprime by listing the divisors and common divisors. Do not use computational technology.
  1. 8 and 35
  2. 13 and 17
  3. 1 and 15

3. Understand.

 
  1. Give an example of two even integers whose greatest common divisor equals two. Do not use the same example as Example 4.5.2.
  2. Give an example of two even integers whose greatest common divisor does not equal two.
  3. What can you say about the greatest common divisor of two even integers? Be specific.
Check.
  1. Hint: List divisors to check your answer. One strategy for finding an example is to use integers of the form \(2p\) and \(2q\) where \(p\) and \(q\) are distinct primes.
  2. Hint: Choose two integers that are multiples of four.

4. Understand.

Evaluate each greatest common divisor in terms of the positive integer \(n\) and explain your reasoning.
  1. \(\displaystyle \gcd(n,n)\)
  2. \(\displaystyle \gcd(n,1)\)
  3. \(\gcd(n,0)\) Hint: For any nonzero integer \(b\) we have \(0 = b(0)\) and so it follows that \(b \mid 0\text{.}\) What does that tell you about the divisors of 0? This part proves Theorem 4.5.6 (c).
Check.
Hint: The answer to each part is one or \(n\text{.}\)

6. Understand.

 
  1. Explain why this statement is true: If \(p\) and \(q\) are distinct primes, then \(p\) and \(q\) are coprime.
  2. Cicadas are insects that emerge from the ground in cycles of various lengths. Two common varieties in the central United States have cycles of 13 and 17 years. If cicadas do not want to emerge in the same years and compete for resources, why is it an advantage to have cycles that have coprime length?

7. Understand.

 
  1. Given a prime \(p\) and an integer \(n\text{,}\) what are the possible values of \(\fn{gcd}(p,n)\text{?}\) Hint: List the divisors of \(p\text{.}\)
  2. Describe your findings by copying and completing the conjecture. “Given a prime \(p\) and integer \(n\text{,}\) either \(\fn{gcd}(p,n) = \underline{~}\) which happens when \(\underline{\hspace{1in} ~}\) or \(\fn{gcd}(p,n) = \underline{~}\) which happens when \(\underline{\hspace{1in} ~}\text{.}\)”
Check.
  1. Hint: The divisors of \(p\) are \(\pm 1, \pm p\) and the greatest common divisor is always positive.
  2. Hint: One case is \(p \mid n\text{.}\)

8. Understand.

  Calculate each greatest common divisor using the prime factorization.
  1. \(\displaystyle \fn{gcd}(5^5,5^7)\)
  2. \(\displaystyle \fn{gcd}(5^5 \cdot 17^2,5^7 \cdot 17)\)
  3. \(\displaystyle \fn{gcd}(5^5 \cdot 17^2,5^7 \cdot 19)\)
  4. \(\displaystyle \fn{gcd}(2^5 \cdot 3^3 \cdot 7,2^3 \cdot 3^4 \cdot 5^2)\)
  5. \(\displaystyle \fn{gcd}(2 \cdot 5 \cdot 11,3 \cdot 7 \cdot 13)\)

9. Recap.

Do you know …
  1. What \(\fn{gcd}(a,b)\) means?
  2. What the greatest common divisor is?
  3. What coprime means?
  4. How to evaluate \(\str{gcd}\) by listing divisors?
  5. How to evaluate \(\str{gcd}\) from the prime factorization?

10. Explore.

Explain how to find the greatest common divisor of two integers from their prime factorization. You may want to refer to Exercise 8 for examples. Hint: One option is to explain in words. Another option is to write
\begin{equation*} a = p_1^{e_1} \cdot p_2^{e_2} \cdot \cdots \cdot p_k^{e_k} \end{equation*}
and
\begin{equation*} b = p_1^{x_1} \cdot p_2^{x_2} \cdot \cdots \cdot p_k^{x_k} \end{equation*}
where, as usual, \(p_1, p_2, \ldots, p_k\) are distinct primes and the exponents \(e_i, x_i \ge 0\) and then find a formula for the prime factorization of \(\fn{gcd}(a,b)\text{.}\)

11. Explore.

 
  1. In the \(xy-\)plane, graph the line segment from \((0,0)\) to \((15,20)\text{.}\) You are welcome to use DESMOS™ to graph the line by writing the equation and setting an appropriate range such as \(-2 \le x \le 17\) and \(-2 \le y \le 22\text{.}\)
  2. How many points on that line segment other than \((0,0)\) have integers in both coordinates? List them.
  3. What does your answer to 11.(b) have to do with the greatest common divisor? State your answer as a conjecture.
  4. Test your conjecture from 11.(c) by repeating parts 11.(a) and 11.(b) for the line segment from \((0,0)\) to \((6,15)\text{.}\)
Check.
  1. Hint: The line is \(y = \frac{20}{15}x\text{.}\) Use the fractions in DESMOS. You can show the grid lines counting by \(x=1\) and \(y=1\) to help count the points.
  2. Hint: Five points.
  3. Hint: What is \(\fn{gcd}(15,20)\text{?}\)
  4. Hint: It should work.

12. Explore.

Consider the statement \(Q\text{:}\) For any positive integers \(a\)\(,b\text{,}\) and \(n\text{:}\) if \(a \mid n\) and \(b \mid n\text{,}\) then \(ab \mid n\text{.}\)
  1. Give an example to show that \(Q\) is false. Hint: That is, find positive integers \(a\text{,}\) \(b\text{,}\) and \(n\) such that \(a \mid n\) and \(b \mid n\text{,}\) but \(ab \nmid n\text{.}\)
  2. Is \(Q\) true when \(a = 4\) and \(b = 6\text{?}\) Is \(Q\) true when \(a = 4\) and \(b = 5\text{?}\) No justification required.
  3. Conjecture when \(Q\) is true. Hint: Some relationship between \(a\) and \(b\) guarantees that \(Q\) is true.

13. Explore.

  An element \(a\) of \(\mathbb{Z}_n\) is a unit if there is a solution of \(a \otimes x = 1\) in \(\mathbb{Z}_n\text{.}\) Note that zero cannot be a unit because \(0 \otimes x = 0 \neq 1\) and one is always a unit because \(1 \otimes 1 = 1\text{.}\) In Section 4.3 Exercise 14, we calculated the examples in Table 4.5.27.
Table 4.5.27. The units in the integers mod \(n\) for \(n=5,6,8\) and 10
\(n\) units in \(\mathbb{Z}_n\)
5 \(1,2,3,4\)
6 \(1,5\)
8 \(1,3,5,7\)
10 \(1,3,7,9\)
  1. Find the units in \(\mathbb{Z}_{7}\text{.}\)
  2. Conjecture which elements are units in \(\mathbb{Z}_p\) when \(p\) is prime.
  3. Check that \(1, 5, 7, 11\) are units mod \(\mathbb{Z}_{12}\text{.}\) Hint: Find a solution to \(a \otimes x = 1\) for each of \(a=1,5,7,11\text{.}\)
  4. Check that \(9\) is not a unit by checking \(9 \otimes b \neq 1\) for \(b = 0, 1, 2, 3, \ldots, 11\text{.}\) Yes, that means writing the row for 9 in the multiplication table of \(\mathbb{Z}_{12}\text{.}\) You may use computational technology to calculate \(\fn{mod}\) 12.
  5. Conjecture which integers \(a\) have the property that \(a\) is a unit in \(\mathbb{Z}_n\text{.}\) Hint: your answer should involve \(a\) and \(n\text{.}\)

Subsubsection Exercises for 4.5.B The Euclidean Algorithm

14. Practice.

Use the Euclidean Algorithm to calculate each greatest common divisor. Start with \(a\) equal to the largest of the two integers.
  1. \(\displaystyle \fn{gcd}(12,18)\)
  2. \(\displaystyle \fn{gcd}(55,40)\)
  3. \(\displaystyle \fn{gcd}(5,7)\)
Check.
  1. \(8 \fn{ mod } 12 = 6\text{,}\) \(12 \fn{ mod } 6 = 0\text{,}\) and so \(\fn{gcd}(12,18)=6\text{.}\)
  2. Five
  3. Hint: They are coprime.

15. Understand.

We saw the Fibonacci numbers \(1, 2, 3, 5, 8, 13, 21, 34, 55, 89\) in the Squares and Dominoes puzzle Activity 2.1.A. Something strange happens when we use the Euclidean Algorithm to calculate the greatest common divisor of consecutive Fibonacci numbers.
  1. Use the Euclidean Algorithm to calculate \(\fn{gcd}(8,5)\text{.}\)
  2. Use the Euclidean algorithm to calculate \(\fn{gcd}(89,55)\text{.}\)
  3. What do you notice about the answer in each case?
  4. What do you notice about the process in each case?
Check.
  1. \(8 \fn{ mod } 5 = 3\text{,}\) \(5 \fn{ mod } 3 = 2\text{,}\) \(3 \fn{ mod } 2 = 1\text{,}\) and \(2 \fn{ mod } 1 = 0\text{,}\) and so \(\fn{gcd}(8,5)=1\text{.}\)
  3. Hint: We got the same answer.
  4. Hint: It takes a long time. (It might not surprise you to learn that Fibonacci numbers are a worst case scenario for the Euclidean Algorithm.)

16. Understand.

Use the Euclidean Algorithm to calculate \(\str{gcd}\)\((3n+2,2n+1)\text{,}\) where \(n\) is a fixed but unknown positive integer.

17. Understand.

Use the Euclidean Algorithm to show that any two consecutive positive integers are coprime. Start by restating what we are trying to show in terms of a positive integer \(n\text{.}\)

18. Recap.

Do you know …
  1. What the Euclidean Algorithm calculates?
  2. How to use the Euclidean Algorithm?

Subsubsection Exercises for 4.5.C Coprime Integers

19. Practice.

 
  1. Explain why if \(2 \nmid n\) and \(7 \nmid n\text{,}\) then \(n\) and 28 are coprime.
  2. Evaluate \(\varphi(28)\) using the method from Example 4.5.11
Check.
  1. Hint: List the divisors of \(28 = 2^2 \cdot 7\text{.}\)
  2. Hint: Write \(1,2,3,\ldots,28\text{.}\) Cross out the multiples of two and the multiples of seven.

20. Practice.

  Evaluate each quantity using the method from Example 4.5.11.
  1. \(\displaystyle \varphi(17)\)
  2. \(\displaystyle \varphi(18)\)
  3. \(\displaystyle \varphi(19)\)
  4. \(\displaystyle \varphi(20)\)
Check.
Hint: The answers in some order are six, eight, 16, and 18.

21. Understand.

 
  1. For any value of \(n\text{,}\) what is the smallest value of \(\varphi(n)\text{,}\) and which integers \(n\) give that smallest value? No justification required.
  2. For any specific integer \(n\text{,}\) what is the largest value of \(\varphi(n)\) in terms of \(n\text{,}\) and which integers \(n\) give that largest value? No justification required.
Check.
  1. Hint: \(\varphi(n)=1\) for exactly two values of \(n\text{.}\)
  2. Hint: The largest possible value is \(\varphi(n)=n-1\text{.}\) Look at your findings in Activity 4.5.C.

22. Recap.

Do you know …
  1. Why we only need to check for common prime divisors to determine if two integers are coprime?
  2. How to calculate Euler’s totient function of an integer?

24. Explore.

  Justify your conjecture from Exercise 23 by counting. Hint: Count the number of multiples of \(p\) that are less than \(p^k\text{.}\) What fraction of the integers from 1 to \(p^k\) are not coprime to \(p^k\text{?}\) What (remaining) fraction of the integers from 1 to \(p^k\) are coprime to \(p^k\text{?}\) Count the number of integers from 1 to \(p^k\) that are coprime to \(p^k\text{,}\) that is, calculate \(\varphi(p^k)\text{.}\) Simplify your final answer.
PrevTopNext