# 2 Divisibility

Anyone who has ever taken a high school math class knows that divisibility is an important concept. But what exactly is divisibility, and how can it be used to solve problems? This book provides a comprehensive guide to understanding divisibility and covers topics such as prime numbers, composite numbers, GCDs, and more. If you’re looking to improve your understanding of math and want to learn everything there is to know about divisibility, then this is the perfect book for you!

Number theory is the study of integers and their properties. One of the most important concepts in number theory is divisibility. Divisibility is a way of determining whether one number is a multiple of another number. For example, we say that 6 is divisible by 3 because 3 x 2 = 6. We also say that 10 is divisible by 5 because 5 x 2 = 10. In general, we say that a number a is divisible by another number b if there exists an integer c such that a = b x c.

Divisibility is a critical concept for advanced college students because it is the basis for many other number theoretic concepts and results. For example, the Euclidean algorithm for finding the greatest common divisor of two numbers relies on the concept of divisibility. Furthermore, many proofs in number theory involve showing that one number is divisible by another number. As a result, students must have a strong understanding of divisibility and be able to apply it in various contexts.

First focus on specific properties of divisibility such as the division algorithm and modular arithmetic. And then we focus on specific applications of divisibility such as greatest common divisors and least common multiples. We make sure to provide plenty of examples and practice problems for you to work through. By doing so, you’ll help ensure that they gain a strong understanding of this important number theoretic concept.

A prime number is a positive integer that has no divisors other than 1 and itself. In other words, a prime number cannot be evenly divided by any other number except for 1 and itself. For example, the number 7 is prime because it can only be evenly divided by 1 and 7. The number 10 is not prime because it can be evenly divided by 1, 2, 5, and 10. Prime numbers are an important concept in mathematics, and they have a wide range of applications in cryptography and coding theory.

Divisibility in the integers is a fundamental topic in number theory, and the study of prime numbers has led to the development of important theoretical tools like the Chinese Remainder Theorem and the Euclidean algorithm. In addition, prime numbers are used in public key cryptography, which is a technique for secure communication that is used by militaries, banks, and other organizations.

The greatest common divisor (GCD) of two integers is the largest integer that evenly divides both numbers. For example, the GCD of 24 and 18 is 6 because 6 is the largest integer that evenly divides 24 and 18. The Euclidean algorithm is a method for finding the GCD of two integers that is based on the concept of divisibility. The algorithm is named after the Greek mathematician Euclid, who first described it in his book Elements, around 300 BC, making it one of the oldest algorithms still in use today.

The Euclidean algorithm is a powerful tool that has a wide range of applications. In particular, it can be used to find the GCD of two numbers when one number is much larger than the other. It can also be used to find the LCM of two numbers and to solve linear Diophantine equations.

The Euclidean algorithm is based on the following property of divisibility: if a is divisible by b, then a - b is also divisible by b. This property can be used to find the GCD of two numbers when one number is much larger than the other.

The Fundamental Theorem of Arithmetic is a theorem that states that every positive integer is divisible by a unique (up to ordering) set of primes. In other words, if a and b are two positive integers with no common factors (i.e., they are co-prime), then a*b is divisible by all of the primes that divide a and by all of the primes that divide b.

This theorem is one of the cornerstones of number theory, and it has many applications in mathematics and computer science. It is also a useful tool for proving other results in number theory. For example, it can be used to show that there are infinitely many prime numbers. The proof of the theorem is relatively simple, but it relies on some interesting ideas.

The theorem is a fundamental result in number theory, and it has important applications in cryptography and security. The theorem was first proved by Euclid in his Elements, and it has been central to number theory ever since.

A linear Diophantine equation is an equation of the form ax + by = c, where a, b, and c are integers. This type of equation has infinitely many integral solutions if a and b are relatively prime, and no solutions if they are not.

In general, the set of all solutions to a linear Diophantine equation forms a line in the plane. However, some equations have special solutions that do not lie on this line. For example, the equation 2x + 3y = 5 has the solution x = 2 and y = -1, which is not on the line 2x + 3y = 5. These special solutions are called non-trivial solutions. The most common method to solve a linear Diophantine equation is the Euclidean algorithm.

The study of linear Diophantine equations is a branch of mathematics known as number theory. Number theory is the study of the positive integers, which are the whole numbers greater than 0. Integer solutions to linear Diophantine equations have applications to many areas of mathematics, including cryptography and coding theory.

I wrote this book for people who want to improve their understanding of mathematics. In it, I cover the basics of divisibility and explain how to use divisibility to solve problems. I also include worked examples and practice problems so that you can test your knowledge as you go.

When teaching divisibility to advanced college students, it is important to stress the importance of writing proofs. A proof is a logical argument that shows that a statement is true. By stressing the importance of writing proofs, students will be better prepared to understand and apply the concept of divisibility in their future studies.

When it comes to teaching mathematics, there is no one-size-fits-all approach. Different students learn in different ways, and what works for one may not work for another. However, some general principles can help to make math instruction more effective.

First, it is important to create a foundation of basic skills. Without a strong understanding of basic concepts, students will struggle to progress to more advanced material. Second, it is important to provide plenty of practice opportunities. Students need to be able to work through problems on their own in order to develop fluency and confidence.

Finally, it is important to emphasize understanding over rote memorization. Understanding the underlying concepts is key to being able to apply mathematics in the real world. By following these principles, you will build a strong foundation that will serve you well throughout your life.

This book is a comprehensive guide to understanding divisibility. If you’re looking to improve your understanding of math and want to learn everything there is to know about divisibility, then this is the perfect book for you! The author does a great job of explaining complex concepts in an easy-to-understand way, making it ideal for anyone who wants to strengthen their understanding of divisibility. I would highly recommend this book to anyone looking for a better grasp of how divisibility works.

## 2.1 The Integers

Discuss axioms and the properties of the integers.

## 2.2 Divisibility and The Division Algorithm

We begin by stating the definition of divisibility, the main topic of discussion. We then give a few examples followed by several basic lemmas on divisibility. The Well-Ordering Axiom, which is used in the proof of the Division Algorithm, is then stated. Examples demonstrating how to use the Division Algorithm as a method of proof are then given.

Certainly the sum, difference and product of any two integers is an integer. The same can not be said about the ratio of two integers. For example, while 2 and 3 are integers, the ratio \(2/3\) is not an integer. We simply can not take any to integers and divide them. The study of the integers is to a great extent the study of divisibility.

**Definition 2.1 **If \(a\) and \(b\) are integers with \(a\neq 0,\) we say that \(a\) **divides** \(b,\) written \(a | b,\) if there exists an integer \(c\) such that \(b=a c\).

Here are some examples of divisibility:

- \(3|6\) since \(6=2(3)\) and \(2\in \mathbb{Z}\)
- \(6|24\) since \(24=4(6)\) and \(4\in \mathbb{Z}\)
- \(8|0\) since \(0=0(8)\) and \(0\in \mathbb{Z}\)
- \(-5|-55\) since \(-55=11(-5)\) and \(11\in \mathbb{Z}\)
- \(-9|909\) since \(909=-101(-9)\) and \(-101\in \mathbb{Z}\)

There are other common ways of saying \(a\) divides \(b\). Namely, \(a|b\) is equivalent to all of the following:

- \(a\) is a
**divisor**of \(b\) - \(a\) divides \(b\)
- \(b\) is
**divisible by**\(a\) - \(b\) is a
**multiple of**\(a\) - \(a\) is a
**factor of**\(b\)

Any integer \(n\), except \(0\), has just a finite number of divisors. For if \(a|n\) where \(a\) and \(n\) are positive integers, then \(n=ak\) for some integer \(k\). Since \(k\) is a positive integer, we see that \(n=ak\geq a\). Hence any nonzero integer \(n\) can have a most \(2|n|\) divisors.

We now state and prove the transitive and linear combination properties of divisibility.

**Lemma 2.1 (Transitive Property of Divisibility]) **Let \(a\), \(b\), and \(c\) be integers. If \(a | b\) and \(b | c\), then \(a | c\).

*Proof*. Suppose \(a|b\) and \(b|c,\) then there exists integers \(m\) and \(n\) such that \(b=m a\) and \(c=n b.\) Thus \[
c=n b=n(m a)=(n m )a.
\] Since \(nm\in \mathbb{Z}\) we see that \(a|c\) as desired.

We say an integer \(n\) is a **linear combination** of \(a\) and \(b\) if there exists integers \(x\) and \(y\) such that \(n=ax+by\). For example, \(7\) is a linear combination of \(3\) and \(2\) since \(7=2(2)+1(3)\). The next lemma says that if an integer divides to other integers, then it divides any linear combination of these two integers.

**Lemma 2.2 (Linear Combinations) **Let \(a\), \(b\), and \(c\) be integers. If \(c|a\) and \(c|b,\) then \(c|(x a+y b)\) for any positive integers \(x\) and \(y\).

*Proof*. Suppose \(c|a\) and \(c|b\). Then there exists integers \(m\) and \(n\) such that \(a=m c\) and \(b=n c.\) Assume \(x\) and \(y\) are arbitrary integers. We have \[
x a+y b=x(m c)+y(n c)= c(x m+ y n)
\] Since \(x m+ y n \in \mathbb{Z}\) we see that \(c|(x a+y b)\) as desired.

We now state and prove the antisymmetric and multiplicative properties of divisibility.

**Lemma 2.3 (Antisymmetric Property of Divisibility) **Let \(a\) and \(b\) be nonzero positive integers. If \(a | b\) and \(b |a\), then \(a= b.\)

*Proof*. Suppose \(a|b\) and \(b|a,\) then there exists integers \(m\) and \(n\) such that \(b=m a\) and \(a=n b.\) Notice that both \(m\) and \(n\) are positive since both \(a\) and \(b\) are.

Then we have \[
a=n b= n(m a) = (n m) a.
\] Thus, \(n m=1\) and so in particular \(n= 1.\) Whence, \(a= b\) as desired.

**Lemma 2.4 (Multiplicative Property of Divisibility) **Let \(a\), \(b\), and \(c\) be integers. If \(c\neq 0\) and \(a|b\) then \(a c|b c.\)

*Proof*. Suppose \(a|b\). Then there exists an integer \(n\) such that \(b=n a.\) By substitution we find, \[
b c=(n c) a=(a c) n.
\] Since \(c\neq 0\), it follows that \(ac\neq 0\), and so \(a c| b c\) as needed.

**Lemma 2.5 **Let \(a\) and \(b\) be integers. If \(a|b,\) then \(a^n|b^n\) for any natural number \(n.\)

*Proof*. We will use mathematical induction. Since \(a|b\) certainly implies \(a|b,\) the case for \(k=1\) is trivial. Assume that \(a^k|b^k\) holds for some natural number \(k>1\). Then there exists an integer \(m\) such that \(b^k=m a^k.\) Then \[
b^{k+1}=b b^k
=b \left(m a^k\right)
=(b m )a^k
=(m' a m )a^k
=M a^{k+1}
\] where \(m'\) and \(M\) are integers. Whence, \(a^{k+1}|b^{k+1}\) as desired.

Before we state and prove the Division Algorithm, let’s recall the Well-Ordering Axiom, namely:

Every nonempty set of positive integers contains a least element.

This is an incredible important and powerful statement. We will use the Well-Ordering Axiom to prove the **Division Algorithm** .

The proof of the Division Algorithm illustrates the technique of proving **existence** and **uniqueness** and relies upon the Well-Ordering axiom.

**Theorem 2.1 (Division Algorithm) **If \(a\) and \(b\) are nonzero positive integers, then there are unique positive integers \(q\) and \(r\) such that \[
a=b q+r \qquad \text{and} \qquad 0\leq r<b.
\]

*Proof*. First we prove existence. Let \(b\) be an arbitrary natural number greater than \(0\) and let \(S\) be the set of multiples of \(b\) that are greater than \(a\), namely,

\[S=\{b i \mid i\in \mathbb{N} \text{ and } b i > a \}.\]

Now we prove uniqueness. Suppose \[ a=bq_1 +r_1, \quad a=b q_2+r_2, \quad 0\leq r_1<b, \quad 0\leq r_2<b. \] If \(q_1=q_2\) then \(r_1=r_2\). Assume \(q_1<q_2\). Then \(q_2=q_1+n\) for some natural number \(n>0\). This implies \[ r_1=a-b q_1=bq_2+r_2-b q_1=b n +r_2\geq b n\geq b \] which is contrary to \(r_1<b\). Thus \(q_1<q_2\) cannot happen. Similarly, \(q_2<q_1\) cannot happen either, and thus \(q_1=q_2\) as desired.

We say an integer \(a\) is of the form \(bq+r\) if there exists integers \(b,\) \(q,\) and \(r\) such that \(a=bq+r.\) Notice that the division algorithm, in a certain sense, measures the divisibility of \(a\) by \(b\) using a remainder \(r\).

**Example 2.1 **Show \(3\) divides \(a(a^2+2)\) for any natural number \(a\).

*Solution*. Equivalently, we need to show that \(a\left(a^2+2\right)\) is of the form \(3k\) for some \(k\) for any natural number \(a.\) By the division algorithm, \(a\) has exactly one of the forms \(3 k,\) \(3k+1,\) or \(3k+2.\) If \(a=3k+1\) for some \(k,\) then

\[(3k+1)\left((3k+1)^2+2\right)=3(3k+1)\left(3k^2+2k+1\right)\] which shows \(3|a(a^2+2)\). If \(a=3k+2\) for some \(k,\) then

\[(3k+2)\left((3k+2)^2+2\right)=3(3k+2)\left(3k^2+4k+2\right)\] which shows \(3|a(a^2+2)\). Finally, if \(a\) is of the form \(3k\) then we have

\[a\left(a^2+2\right)=3k\left(9k^2+2\right)\] which shows \(3|a(a^2+2)\). Therefore, in all possible cases, \(3|a(a^2+2))\) for any positive natural number \(a\).

The advantage of the Division Algorithm is that it allows us to prove statements about the positive integers (integers) by considering only a finite number of cases. The next three examples illustrates this.

**Example 2.2 **Show \(6\) divides the product of any three consecutive positive integers.

*Solution*. Let \(m\) be an natural number. We need to show that \(m(m+1)(m+2)\) is of the form \(6 k\). The division algorithm yields that \(m\) is either even or odd (not both). In either case, \(m(m+1)(m+2)\) must be even. The natural number \(m(m+1)(m+2)\) is also divisible by 3, since one of \(m,\) \(m+1,\) or \(m+2\) is of the form \(3k\). Since \(m(m+1)(m+2)\) is even and is divisible by 3, it must be divisible by 6.

**Example 2.3 **Prove that, for each natural number \(n\), \(7^n-2^n\) is divisible by \(5\).

*Solution*. Let \(P\) be the set of natural number for which \(7^n-2^n\) is divisible by \(5\). Clearly, \(7^1-2^1=5\) is divisible by \(5\), so \(P\) is nonempty with \(0\in P\). Assume \(k\in P\). We find \[\begin{align*}
7^{k+1}-2^{k+1}
& = 7\cdot 7^k-2\cdot 2^k \\
& = 7\cdot 7^k-7\cdot 2^k+7\cdot 2^k-2\cdot 2^k \\
& = 7(7^k- 2^k)+2^k(7 -2)
\end{align*}\] The induction hypothesis is that \((7^k- 2^k)\) is divisible by 5. Now since both \((7^k-\cdot 2^k)\) and \(7-2\) are divisible by 5, so is any linear combination of \((7^k- 2^k)\) and \(7-2\). Hence, \(7^{k+1}-2^{k+1}\) is divisible by 5 by \(\ref{lincombdiv}\). Therefore, \(k+1\in P\) and so \(P=\mathbb{N}\) by mathematical induction.

## 2.3 Prime Numbers

Several of the most basic and interesting questions concerning the integers involves the prime numbers. For example,This question is easy to understand, but no one has been able to answer it.

From a certain point of very, the prime numbers are the building blocks for the integers; that is to say, every integer greater than 1 has a prime factor. Indeed, every positive integer is a product of primes. This result was known to the ancient Greeks and is sometimes referred to as Euclid{’}s lemma.

One of the first questions that comes to mind is concerning prime numbers is: `how many prime numbers are there?" or maybe even`

why are primes so important to talk about?“.

What about these questions: `without using trial division, how can one determine whether a given integer is prime or composite?",`

is it possible for given a function to find all the prime numbers?”, ``are there arbitrarily long sequences of integers, all of which are not primes?“. These simple questions have kept mathematicians busy for thousands of years.

**Definition 2.2 **A **prime number** is a natural number greater than 1 that is divisible by no natural numbers other than 1 and itself. A natural number greater than 1 that is not prime is called a **composite number** .

The idea, passing over 1, is to find a prime number and then cross out all of the multiples of this prime number. For example, 2 is prime but every even number is not and so cross all even numbers off the list. Next, 3 is prime and so cross out every multiple of three, because they are not prime. Continue in this fashion, and then the numbers left are the prime numbers. Of course for a given large integer this is not practical, if your time is limited. Since the time of Eratosthenes, sophisticated versions of this algorithm (called the **Sieve of Eratosthenes** ) have achieved new results.

\[
\begin{array}{llllllllll}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10
\\
11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20
\\
21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30
\\
31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40
\\
41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50
\\
51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60
\\
61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70
\\
71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80
\\
81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90
\\
91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100
\end{array}
\] Consider the first 5 rows in the above array. How many primes are there in the first 5 rows? How many in the last five rows? If one carries out the sieve of Eratosthenes between 10,000 and 10,050, you will find that there are just 4 prime numbers. Can we find 5 rows where there are no prime numbers? What is the last prime number?

The following lemma, while known to Euclid, is proven using the (modern) Well-Ordering Axiom.

**Lemma 2.6 (Prime Divisor) **Every natural number greater than 1 has a prime divisor.

*Proof*. Assume, for a contradiction, that there exists an natural number greater than 1 that does not have a prime divisor. Then since the set of all natural numbers greater than 1 without a prime divisor is nonempty, the Well-Ordering Axiom states that this set must have a least positive natural number, say \(n,\) that does not have a prime divisor and is greater than 1. Since \(n\) does not have a prime divisor and \(n\) divides \(n\), \(n\) must not be prime. Thus, \(n=a b\) and since \(a<n,\) \(a\) must have a prime divisor and similarly for \(b.\) Therefore, \(n=a b\) must have a prime divisor. This contradiction, leads us to the desired conclusion that every natural number greater than 1 must have a **prime divisor** .

The following proof of the infinitude of primes is a great example of what is called proof **by contradiction** . The idea is to suppose that there are finitely many prime numbers, and then use these primes to create another natural number whose prime divisor can not be in the original list of all prime numbers.

**Theorem 2.2 (Euclid) **There are infinitely many primes.

*Proof*. Assume that the prime numbers are listed in ascending order with \(p_1=2,\) \(p_2=3,\) \(p_3=5,\) and so on; and assume (for a contradiction) that \(p_k\) is the last prime. Consider the natural number,

\[
P=p_1p_2\cdots p_k+1.
\] Since every positive natural number greater than 1 has a prime divisor, \(P\) has a prime divisor, say \(p_m.\) However, \(p_m\) can not divide \(P\) since \(P\) is of the form, \(P=c p_m+1.\) Therefore \(p_k\), the last prime number, cannot exist.

## 2.4 Greatest Common Divisors

Perhaps the most useful result concerning great common divisors is Bezout’s lemma. This fact states that the greatest common divisor of two integers is always a linear combination of these two integers. In fact we can say more, the greatest common divisor of two given integers is always the least positive linear combination of these two integers.

**Definition 2.3 **Let \(a\) and \(b\) be two integers that are not both zero. Then the **greatest common divisor** of \(a\) and \(b\) is the largest integer that divides both \(a\) and \(b.\) The greatest common divisor of \(a\) and \(b\) is denoted by \((a,b)\) or sometimes by \(\gcd (a,b).\)

The integers 4 and 8 have greatest common divisor of 4 and we write \((4,8)=4\) since 4 is the largest integer that divides both 4 and 8. Also \((23,2)=1\) and \((9,51)=3.\)

**Definition 2.4 **A **linear combination** of \(a\) and \(b\) is an integer of the form \(m a+n b\) where \(m\) and \(n\) are integers.

Note that given 2 and 51 we can form many different linear combinations, here are three examples: \[
3(2)+7(51)=363,
\qquad
3(2)-7(51)=-351,
\] and \(-31(2)+0(51)=-62.\) The connection between liner combination and greatest command visors is **Bezout’s identity** .

**Theorem 2.3 (Bezout’s Identity) **Let \(a\) and \(b\) be integers, not both zero. Then \((a,b)=a m +b n\) for some integers \(m\) and \(n\).

*Proof*. Assume \(a\) and \(b\) are integers and w.l.o.g. assume \(a\neq 0\). Consider the set

\[
S=\{a x+b y \mid a x+b y>0, \, x \text{ and } y \text{ are integers}\}.
\] Since \(S\) is nonempty, because \(|a|\) is in \(S,\) the Well-Ordering Axiom yields a least positive natural number \(d\) such that \(d=a m+b n\) for some integers \(m\) and \(n.\) The idea is to show that \(d=(a,b).\) To do this we use the Division Algorithm obtaining \(q\) and \(r\) such that \(a=q d+r\) where \(0\leq r<d.\) If \(r>0,\) then \(r\) is in \(S\) because \[
r=a-q d=a-q(a m+b n)=a(1-q m)+b(-q n).
\]

But we can not have \(r\) is in S because \(r<d\) and \(d\) is the least in \(S.\) Therefore \(r=0\) and so \(d|a.\) Using the same argument with \(a\) replaced by \(b,\) it is shown that \(d|b.\) To show \(d=(a,b)\) it remains to show that \(d\) is greater than any other common divisor of \(a\) and \(b;\) and so let \(c\) be a common divisor of \(a\) and \(b.\) Then, \(c\mid a m+b n\) that is \(c\mid d\) and so \(d\geq c.\)

**Corollary 2.1 **There are an infinite number of ways to write \((a,b)\) as a linear combination of \(a\) and \(b.\)

*Proof*. Let \(d=(a,b).\) There exists integers \(m\) and \(n\) such that \(d=a m+b n\) and thus, for any integer \(k,\) we have \[
d=(m+k(b/d))a+(n-k(a/d))b
\] which expresses \((a,b)\) as a linear combination of \(a\) and \(b.\)

**Corollary 2.2 **Let \(a\) and \(b\) be integers, then the set of linear combinations of \(a\) and \(b\) is the set of multiples of \((a,b)\).

*Proof*. By \(\ref{linecombgcd}\), if \(d=(a,b)\) then \(d=a m+b n\) for some integers \(m\) and \(n.\) Thus every multiple of \(d\) is also a linear combination of \(a\)and \(b.\) Conversely, let \(a x+b y\) be a linear combination of \(a\) and \(b.\) Then using \(\ref{lincombdiv}\), \(d|a m+b y\) and so \(a m+b y\) is a multiple of \(d.\)

Two integers are said to be **relatively prime** if their greatest common divisor is 1.

**Definition 2.5 **If \((a,b)=1\) then \(a\) and \(b\) are said to be **relatively prime** .

Note that \((2,5)=1\) and so 2 and 5 are relatively prime. But \((8,24)=8\) and so 8 and 24 are not relatively prime.

**Definition 2.6 **Integers \(a_1,\) \(a_2,\) \(\text{...},\) \(a_n\) are called **pairwise relatively prime** when \(\left(a_i,a_j\right)=1\) for every possible \(i\) and \(j\) with \(i\neq j.\)

For example, The integers 3, 5, 7 are pairwise relatively prime because \((3,5)=1,\) \((5,7)=1,\) and \((3,7)=1.\) The integers 4, 19, 27 are pairwise relatively prime because \((4,19)=1,\) \((4,27)=1,\) and \((4,27)=1.\)

The integers 10, 14, and 35 are **mutually relatively prime** because \((10,14,35)=1\) (there is no common divisor for all three) however they are not pairwise relatively prime because \((10,14)=2.\)

**Example 2.4 **Show that if \(k\) is an integer, then the integers \(6k-1,\) \(6k+1,\) \(6k+2,\) \(6k+3,\) and \(6k+5\) are relatively prime.

*Solution*. Suppose that \((6k+a,6k+b)=d.\) Then \(d|(b-a).\) We have \(a,b\in \{-1,1,2,3,5\},\) so if \(a<b\) it follows that \(b-a\in \{1,2,3,4,6\}.\) Hence \(d\in \{1,2,3,4,6\}.\) To show that \(d=1\) it is sufficient to show that neither 2 nor 3 divides \((6k+a,6k+b).\) If \(p=2\) or \(p=3\) and \(p|(6k+a,6k+b)\) then \(p|a\) and \(p|b.\) However, there are no such pairs \(a,b\) in the set \(\{-1,1,2,3,5\}.\)

**Example 2.5 **Show that every positive integer greater than 6 is the sum of two relatively prime integers greater than 1.

*Solution*. By the previous example, we know that \(6k-1,\) \(6k+1,\) \(6k+2,\) \(6k+3,\) and \(6k+5\) are pairwise relatively prime. To represent \(n\) as the sum of two relatively prime integers greater than one, let \(n=12k+h,\) \(0\leq h<12.\) We now examine the twelve cases, one for each possible value of \(h,\) in the following tables:

\[\begin{array}{c|c} h & n \\ \hline 0 & (6k-1)+(6k+1) \\ 1 & (6k-1)+(6k+2) \\ 2 & (6k-1)+(6k+3) \\ 3 & (6k+1)+(6k+2) \\ 4 & (6k+2)+(6k+2) \\ 5 & (6k+2)+(6k+3) \end{array}\]

\[\begin{array}{c|c} h & n \\ \hline 6 & (6k+1)+(6k+5) \\ 7 & (6k+2)+(6k+5) \\ 8 & (6k+3)+(6k+5) \\ 9 & (12k+7)+2 \\ 10 & (12k+7)+3 \\ 11 & (12k+9)+2 \end{array}\]

So for all possible cases very positive integer greater than 6 is the sum of two relatively prime integers greater than 1.

**Corollary 2.3 **Let \(a\) and \(b\) be integers, then \((a,b)=1\) if and only if there exists integers \(m\) and \(n\) such that \(a m+b n=1\).

*Proof*. If \((a,b)=1\) then by \(\ref{linecombgcd}\) there exists integers \(m\) and \(n\) such that \(1=a m +b y.\) Conversely, suppose \((a,b)=d\) and that \(1=a x+b y\) for some integers \(x\) and \(y.\) Then \(d|1\) because \(d|a\) and so \(d=1.\)

**Example 2.6 **Show that \(3k+2\) and \(5k+3\) are relatively prime.

*Solution*. Since \(5(3k+2)-3(5k+3)=1,\) the previous proposition implies that \((3k+2,5k+3)=1.\)

**Theorem 2.4 **Let \(a\) and \(b\) be integers, then \((a,b)\) is the least positive integer that is a linear combination of \(a\) and \(b\).

*Proof*. This follows from the Well-Ordering Axiom as in the proof of (i). The proof is left for the reader as Exercise \(\ref{linecombgcd}\).

**Example 2.7 **What is \(\left(a^2+b^2,a+b\right),\) where \(a\) and \(b\) are relatively prime integers that are not both 0?

*Solution*. Let \(p\) be a prime dividing \(\left(a^2+b^2,a+b\right)\). Then

\[
p \, | (a+b)^2 - (a^2+b^2) =2 a b.
\] Now if \(p|a,\) then \(p|b\) since \(p|(a+b).\) But \((a,b)=1,\) so \(p\nmid a.\) Similarly, \(p\nmid b.\) Therefore, \(p|2\) and so \(p=1\) or \(p=2.\) If \(a\) and \(b\) have the same parity, then \(2|(a+b)\) and \(2\left|\left(a^2+b^2\right)\right.\) and so \(\left(a^2+b^2,a+b\right)=2.\) But if \(a\) and \(b\) have opposite parity, then \(a+b\) and \(\left(a^2+b^2,a+b\right)=1.\)

**Corollary 2.4 **If \((a,b)=d,\) then \((a/d,b/d)=1\).

*Proof*. If \((a,b)=d\) then \(d=a m+b n\) for some integers \(m\) and \(n.\) Since \(d|a\) and \(d|b\) we have \(1=(a/d) m+(b/d) n\) and by \(\ref{lestlinercomb}\) \((a/d,b/d)=1.\)

**Theorem 2.5 **Let \(a\) and \(b\) be integers, then \((a,b)=d\) if and only if \(d|a,\) \(d|b,\) and if \(c\) is another common divisor then \(c|d\).

*Proof*. If \((a,b)=d\) then by definition, \(d|a\) and \(d|b.\) Let \(c\) be a common divisor of \(a\) and \(b\) with \(a=c x\) and \(b=c y\) for some integers \(x\) and \(y.\) By \(\ref{linecombgcd}\), there exists \(m\) and \(n\) such that \(d=a m+b n;\) and therefore we have \(d=c (x m+y n).\) Whence, \(c|d.\)

**Corollary 2.5 **If \(b|a c\) and \((a,b)=1,\) then \(b|c\).

*Proof*. If \(b| a c\) there exists an integer \(k\) such that \(a c = b k\). Since \((a,b)=1\) there exists integers \(m\) and \(n\) such that \(a m+b n=1\). Then \[
c=c (1)=c (a m + b n) = (a c) m + b c n = b k m+b n = b ( k m + c n)
\] which shows \(b|c\) since \(km + c n\) is an integer.

**Corollary 2.6 **If \(b|a\), \(c|a\), and \((b,c)=1\), then \(b c|a\).

*Proof*. If \(b|a,\) \(c|a,\) and \((b,c)=1,\) there exist natural numbers \(s\), \(t\), \(m\) and \(n\) with \(a= sb\), \(a =t c\), and \(bm+nc=1\). Then \[
a=a(1)=a(bm+nc)=a b m+a n c = t c b m +s b n c= bc(tm+sn)
\] which shows \(bc|a\) since \(tm+sn\) is an natural number.

**Corollary 2.7 **If \((a,b c)=1\), then \((a,b)=1\) and \((a,c)=1\); and conversely.

*Proof*. If \((a,b c)=1\), there exists natural numbers \(u\) and \(v\) such that \(a u+ b c v=1\). Since 1 is a linear combination of \(a\) and \(b\) and is also a linear combination of \(a\) and \(c\), it follows \((a,b)=1\) and \((a,c)=1\).

Conversely, if \((a,c)=1\) then \((a,b)=1\) there exists natural numbers \(s\), \(t\), \(m\) and \(n\) such that \(a s+b ct=1\) and \(a m+b n=1\). Multiplying, \[ 1=(a s+b ct)(a m+b n)=a (sm+sbn+ctm)+ bc (tn) \] which shows 1 is a linear combination of \(a\) and \(bc\) and so \((a,bc)=1\).

**Corollary 2.8 **If \((a,b)=1\) and \(c|a\), then \((c,b)=1\).

*Proof*. If \((a,b)=1\) and \(c|a,\) then there exists natural numbers \(m\), \(n\), and \(k\) such that \(am+bn=1\) and \(a=ck\). Then \[
1=am+bn=c(km)+bn
\] which shows \((b,c)=1\).

## 2.5 Euclidean Algorithm

Divide \(a\) by \(b,\) obtaining the quotient \(q_1\) and the remainder \(r_1\). Then, if \(r_1\) is not zero, divide \(b\) by \(r_1\) obtaining the quotient \(q_2\) and remainder \(r_2\). Then if \(r_2\) is not zero then we repeat this process and divide \(r_1\) by \(r_2\), obtaining the quotient \(q_3\) and remainder \(r_3\). This process, or *algorithm*, is repeated until we first obtain the remainder of zero. At the conclusion of the process we have the greatest common divisor which is the last nonzero remainder.

The next lemma is used in the proof of the Euclidean Algorithm.

**Lemma 2.7 **If \(a\) and \(b\) are positive integers. If \(a=b q+r\) for some positive integers \(q\) and \(r\), then \((a,b)=(b,r)\).

For example, in the case that \(288=40(7)+8\) we have \[\begin{align*} S& =\{d\in \mathbb{Z} \mid d\mid 288 \text{ and } d\mid 40\} \\ & =\{\pm1, \pm 2, \pm 4\pm, 8\pm\} \end{align*}\] \[\begin{align*} T& =\{d\in \mathbb{Z} \mid d\mid 40 \text{ and } d\mid 8\} \\ & =\{\pm1, \pm 2, \pm 4\pm, 8\pm\} \end{align*}\] Clearly, \(S=T\) and both sets are finite.

*Proof*. Assume \(a=bq+r\). Let \(S\) and \(T\) be the set of common divisors of \(a\) and \(b\) and of \(b\) and \(r\), respectively; that is, \[ S=\{d\in \mathbb{Z} : d\mid a \text{ and } d\mid b\} \quad \text{and}\quad T=\{d\in \mathbb{Z} : d\mid b \text{ and } d\mid r\}. \] Let \(d\in S\). So \(d\) divides \(a\) and \(b\) and thus divides \(b\) and \(r=a-b q\). Hence \(d\in T\). To show the reverse inclusion \(T\supseteq S\), if \(d\in T\) then \(d\) divides \(b\) and \(r\). Then \(d\) divides \(a=bq+r\) and \(b\), and so \(d\in S\).

We have shown \(S\subseteq T\) and \(T\subseteq S\); and therefore, \(S=T\). Since these are finite sets the greatest common divisor of \(a\) and \(b\) is the same as the greatest common divisor of \(b\) and \(r\).

**Example 2.8 **Find \((345688, 245994)\).

*Solution*. By the Division Algorithm, \[\begin{align*}
& 345688 =245994(1)+99694 \, \text{ with } \, 0\leq 99694 < 245994 \\
& 245994 =99694(2)+46606 \, \text{ with } \, 0\leq 46606 < 99694 \\
& 99694 =46606(2)+6482 \, \text{ with } \, 0\leq 6482 < 46606 \\
& 46606 =6482(7)+1232 \, \text{ with } \, 0\leq 1232 < 6482 \\
& 6482 =1232(5)+322 \, \text{ with } \, 0\leq 322 < 1232 \\
& 1232 =322(3)+266 \, \text{ with } \, 0\leq 266 < 322 \\
& 322 =266(1)+56 \, \text{ with } \, 0\leq 56 < 266 \\
& 266 =56(4)+42 \, \text{ with } \, 0\leq 42 < 56 \\
& 56 =42(1)+14 \, \text{ with } \, 0\leq 14 < 42 \\
& 42 =14(3)+0 \, \text{ with } \, 0\leq 0 < 14
\end{align*}\] Therefore, \((345688, 245994)=14\).

**Example 2.9 **Let \(d=(328,288)\). Find \(d\) and write it as a linear combination of 328 and 288.

*Solution*. By the Division Algorithm, \[\begin{align*}
328 & =288(1)+40 \, \text{ with } \, 0\leq 40<288 \\
288 & =40(7)+8 \, \text{with} \, 0\leq 8<40 \\
40 & =8(5)+0 \, \text{ with } \, 0\leq 8<40
\end{align*}\] Now, \(d=(328,288)=8\) follows from \[
(328,288)=(288,40)=(40,8)=(8,0)=8
\] by \(\ref{euallemm}\). We can use the above computation to write \(8\) as a line recombination of 328 and 288 using back substitution: \[\begin{align*}
& 8=288-40(7) \\
& 8=288-[328-288(1)](7) \\
& 8= 8(288)-7(328)
\square
\end{align*}\]

One way to view the **Euclidean algorithm** is as the repeated application of the Division Algorithm and repeated application of \(\ref{euallemm}\).

We can visualize the greatest common divisor. For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60.

The greatest common divisor of two numbers \(a\) and \(b\) is the product of the prime factors shared by the two numbers, where a same prime factor can be used multiple times, but only as long as the product of these factors divides both \(a\) and \(b\). For example, since 1386 can be factored into \(2 \times 3 \times 3 \times 7 \times 11\), and 3213 can be factored into \(3 \times 3 \times 3 \times 7 \times 17\), the greatest common divisor of 1386 and 3213 equals \(63 = 3 \times 3 \times 7\), the product of their shared prime factors. In particular, if two numbers have no prime factors in common, they are relatively prime.

A important feature of the Euclidean algorithm is that it can find the gcd efficiently without having to compute the prime factors.

Factorization of large integers is believed to be a computationally very difficult problem, and the security of many modern cryptography systems is based upon its infeasibility.

Consider the question of finding the greatest common divisor of two numbers. For example, let \(a=288\) and \(b=3266\), what is \((3266,288)\)? We apply the Division Algorithm and \(\ref{euallemm}\) to obtain \[ 3266=11(288)+98 \text{ with } 0\leq 98 <288 \text{ and } (3266,288)=(288,98). \] Again, we apply the Division Algorithm and \(\ref{euallemm}\) to obtain \[ 288=2(98)+92 \text{ with } 0\leq 92 <98 \text{ and } (3266,288)=(288,98)=(98,92). \] Again, we apply the Division Algorithm and \(\ref{euallemm}\) to obtain \[ 98=1(92)+6 \text{ with } 0\leq 6 <92 \text{ and } (3266,288) %=(288,98)=(98,92) =(92,6) =2. \] We now write this process in a general format.

**Theorem 2.6 **Let \(a\) and \(b\) be positive positive integers with \(a\geq b\). If \(b\nmid a\), then apply the division algorithm repeatedly as follows:

{2} & & & \ & & & \ & & &

This process ends after a finite number of steps; that is, for some \(k\): \[ r_{k-2}=r_{k-1} q_k+r_k \text{ with } 0\leq r_k<r_{k-1} \] where $r_{k-1}=r_k q_{k+1}+0 $ and \(r_k=(a,b)\).

*Proof*. The proof follows from the property: if \(a=b q+r,\) then \((a,b)=(b,r).\) Thus, if \(b|a,\) then \(a=b q+0\) and so \((a,b)=(b,0)=b.\) Notice \[
(a,b)
=\left(b,r_0\right)
=\left(r_0,r_1\right)
=\cdot \cdot \cdot =\left(r_{k-2},r_{k-1}\right)
=\left(r_{k-1},r_k\right) =\left(r_k,0\right) =r_k.
\] by \(\ref{euallemm}\) as desired.

In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers.