6 Number Theory

Number Theory is an exciting branch of mathematics that explores the properties and relationships of numbers, particularly integers. In this chapter, we will focus on understanding key concepts that are foundational not only to number theory but also to many areas of mathematics. You will be introduced to prime numbers, which are numbers greater than 1 that have no divisors other than 1 and themselves. We’ll also dive into divisibility rules, which provide quick and easy methods for determining whether one number is divisible by another, such as the rules for divisibility by 2, 3, 4, 5, 6, 8, 11, and 12.

In addition to these concepts, we will explore different methods of proof that can help us establish mathematical truths. You will learn about algebraic proofs, which use equations and logical steps, and bar-diagram proofs, which use visual representations to help illustrate how numbers relate to one another. These techniques will not only enhance your understanding of number theory but also give you new tools to teach your students in a clear and engaging way. By the end of the chapter, you’ll have a deeper appreciation for the beauty and power of integers and how they can be used to solve a wide variety of problems.

6.1 Definitions, and Representation of Natural Numbers

In this section we will study the concept of divisibility and the division algorithm, abstract number representations, and introduction to basic proofs in number theory.

It is important to get a few terms out of the way. The set of natural numbers is denoted by a bold capital letter $ℕ=\{1,2,3,4,...\}$, whereas the set of integers is $ℤ=\{0,1,-1,2,-2,3,-3,...\}$ is the set of whole numbers, which includes the naturals, and 0, plus all the opposites of these natural numbers.

In what follows I may use the idea of integers, and natural numbers interchangeably since often whatever applies to natural numbers often applies to integers in the context of what follows. However, for the purposes of number theoretic concepts to be covered in 5th and 6th grades, natural numbers would be sufficient.

Suppose we have a dividend D, a divisor d, and suppose D is evenly divisible by d, and the quotient is q. The following statements are equivalent:

d divides D
d is a divisor of D
d is a factor of D
D is a multiple of d
D is divisible by d
The product of d and q is D

We will use the symbol ‘|’ to represent the verb “divides”. For example “3 | 12” means “3 divides 12,” which is equivalent to saying “12 is a multiple of 3” and “3 is a factor of 12”.

Definition: $d | D$if and only if there exists an integer $q$ such that $dq=D$.

Example 1: Since $14\ =\ 2\ \times 7$, it follows that $2\ |\ 14$.

Equivalently, ‘ ∤ ‘ means “does not divide.” So, 3 ∤ 14 is a true statement. In general, when we say that

d ∤ D this means that when D is divided by d, we have a remainder r>0. So, the reason why 3 ∤ 14 is because $14\ =\ 3\times 4+2$ where $r=2$.

Definition: $d ∤ D$if and only if there exists a $r>0$, and a $q$ such that $dq+r\ =D$

Example 2: Note that $7\ ∤\ 15$ because when we divide 15 by 7 we get 2, with a remainder 1 so that we could write $15=2\times 7+1$

The d = 2 division diagrams to the right represent numbers 1 through 6 depicted in a way that shows the result of dividing by 2. The number of rows represent the divisor 2, while the number of columns represent the quotient. The extra square represents the remainder. For example, $5\div 2=2R1$ NOTE: The remainder can only be either 0, or 1. It cannot equal the divisor 2.

The d=3 division diagrams on the right indicate the potential division of numbers 1 through 10 by 3. The first numbers 1 and 2 are in orange because they technically represent remainders. For example, when it comes to D= 1 we have: $1\div 3\ =\ 0\ R\ 3$ or equivalently, we would say, $3\times 0+1\ =1$. The numbers which are in white are evenly divisible by 3 without a remainder. NOTE: When the divisor d = 3, the remainder r could only be 0, 1, or 2. It cannot be 3, or larger.

Diagram of the numbers 1 through 10 depicted based on their divisibility by 3. All are put in 3 rows, with remainders highlighted in orange.

Here we revisit the Quotient-Remainder Theorem from 3.3.1:

The Quotient Remainder Theorem: When we divide the dividend D by a divisor d, we may obtain a quotient q, and a reminder r such that $D=dq\ +\ r$ where $0\leq r<d$.

We will now use the square diagram to represent an arbitrary number k. To do this we will use the ellipses … as follows: A bar representing an abstract number n. . The idea is that the … space contains an arbitrary number of small squares. We are now ready to define even and odd numbers.

Definition: An integer $n$ is even if and only if there is an integer $k$ such that $n=2k$.

An arbitrary even integer $n$ may be depicted using a bar diagram by combining two copies of A bar representing an abstract number n. as follows:

Diagram Definition: An even integer $n$: An abstract representation of an even number.

Theorem: Sum of even numbers is even:

Diagram Proof: Here we merely provide two depictions of the concept of even number, and then push them together, appending one next to the other to indicate that the result must also be composed of two copies of the same number.

The abstract representation of the sum of two even numbers equaling an even number.

Algebraic Proof: Let m, and n be two even numbers. This means there exist integers k, and l such that m = 2k, and n = 2l. Let’s add the two even numbers: $m+n=2k+2l\ =\ 2(k+l)$. Since $k+l$ is an integer, it follows that $m+n$ is even.

Definition: An integer $n$ is odd if and only if there is an integer $k$ such that $n=2k+1$.

Diagram Definition: An odd integer $n$: An abstract representation of an odd number.

Theorem: The sum of two odd integers is even.

Diagram Proof: Diagram proof that the sum of two odd numbers is even.

Algebraic Proof: Suppose we have two odd numbers m, and n. We must show that m+n is even. Since m is an odd number m=2k+1 for some whole number k. Since n is an odd number n = 2l+1. Let’s add m and n: $m+n\ =\ (2k+1)\ +\ (2l+1)\ =\ 2k+\ 2l\ +\ 2\ \ =\ \ 2\ (k+l+1)$. Since $k+l+1$ is some integer, it follows that $m+n$ is even.

6.2 Exercises

Verify that (a) $5\ |\ 35$, (b) 8 ∤ 35 by using the definitions of ∤, and |.
Draw a division diagram for $d=4$ for numbers 1 through 12. Be sure to color all the remainders. What is the maximum number of remainders we could have? Explain why this would be the case regardless of the dividend.
Illustrate the quotient-remainder theorem by dividing 134 by 7.
Prove that the sum of an even number and an odd number is odd using (a) a bar diagram, and (b) algebraic proof. Be sure to justify/explain the various parts of the bar diagram.
Give an algebraic proof that the product of two odd numbers is odd.
Give an algebraic proof that the product of an even number and an odd number is even.
Give a diagram proof that the product of an even number and an odd number is even. HINT: Use digital drawing software like Microsoft Whiteboard to make an even number of copies of a bar diagram which represents an odd number. Then try to rearrange the remainder (orange colored square) so as to “fill all gaps” in showing the result is even.
EXTRA CREDIT: Take a closer look at the division diagrams for d = 3. The dividends D where the remainder is 1 are called numbers which are congruent mod 1, and we write $\equiv 1(mod\ 3)$ So, for example we can say $7\equiv 1\ (mod\ 3)$, but $8\equiv 2\ (mod\ 3)$. The latter is true because when we divide 8 by 3, the remainder is 2. Show that the sum of a number n which is congruent to 1 (mod 3) and a number m which is congruent to 2 (mod 3) is a number which is evenly divisible by 3. In mathematical notation, the latter statement is written as follows: If $m\equiv 1\ (mod\ 3)$, and $n\equiv 2\ (mod\ 3)$, then $m+n\equiv \ 0\ (mod\ 3)$. For example, note that $7+8=15,$which is divisible by 3.

6.3 Divisibility Criteria

In this section we establish a set of theorems that will be used in sections 6.3 - 6.5, especially in establishing divisibility criteria.

Theorem 6.2.1: (The Sum Theorem) Suppose $d\ |\ A$, and $d\ |\ B$, it follows that $d\ |\ (A+B)$.

Diagram Proof: The main idea here is to draw a rectangular array diagram for A, represented using $d$ rows, and do the same for B, indicating that both are divisible by $d$. Addition of these two arrays involves merely appending them, which should result in a corresponding rectangular array having $d$ rows, showing that the sum is also divisible by $d$.

Bar diagram of the sum of A, and B which are divisible by d (since they have d rows). The sum apparently also has d rows.

Algebraic Proof: Suppose $d\ |\ A$, then there exists an integer $k$ such that $A=dk$. Further suppose that $d\ |\ B$. It follows that there exists an integer $l$ such that $B\ =\ dl$. Now, let’s add: $A+B\ =\ dk\ +\ dl\ =\ d(k+l)$. Since the sum is a multiple of the integer $(k+l)$, it follows that $d\ |\ (A\ +\ B)$.

What does it mean to say that $12\ |\ 24$? It simply means that if we were to write the fraction $\frac{24}{12}$ that we could reduce this in such a way that the denominator would be 1. But this is possible only if 24 can be factored into 12, and some other number: $\frac{2\ \cdot 12}{12}$, and we can cancel the 12s. But we also know that $4\ |\ 12$. Does it follow that $4\ |\ 24$? Well, if 12 must exist in factored-form in the numerator, then 4 must also exist given that it’s a factor of 12: $\frac{2\cdot 3\cdot 4}{4\cdot 3}$. This shows that 4 must also divide 12!

Here’s another version of the argument: What does it mean that 12 divides 24?

It means that 12 times some whole number is equal to 24. So, we can say that there is a whole number k such that 12 * k = 24. or 12k=24

Similarly, we know that 4 divides 12. This means that there is a whole number s such that

$4s=12$.

We must show that 4 divides 24. This means we must show that there is a whole number such that 4 multiplied by this whole number equals 24. In other words, a k such that

$12k=24$

Let’s replace (substitute) the 12 in the second equation with 4s that is in the first equation:

$(4s)k=24$

$4(sk)=24$

Since s, and k are whole numbers, so is their product sk. The above equation shows that 4 times sk is 24.

Theorem 6.2.2: (The Factor Theorem): Suppose D| A, and suppose d| D. It follows that d | A.

Diagram Proof: If D	A, this means that A can be represented as a rectangular array in a division diagram with D many rows. The green column is a vertical strip of D squares.

Now, since we know that $d\ |\ D$, it follows that this green strip can be split up into a set of equal parts each of which had $d$ squares (measurement division interpretation). On the right you can see a depiction of the green strip that has been split up in d copies, each of which is of equal size. This gives us the idea that we can actually split the entire array A into d copies as well since D is just one of its columns. Below you can see the split of A into d copies of Small bar diagram representing an abstract number.

Small bar diagram representing an abstract number.

along its rows, effectively splitting up A into d equal copies, implying that $d\ |\ A$.

Bar diagram representing d copies of the number in question.

Algebraic Proof: We know that D divides A. This means that there is a whole number $k$ such that $dk=A$. Similarly, we know that d divides D. This means that there is a whole number $s$ such that $ds\ =\ D$. We need to show that d divides A. This means that we need to show that A is a multiple of d, or equivalently that d multiplied by some whole number equals A. We will substitute in ds for D in the equation $Dk=A$, getting $dsk=A$. This shows that d times (sk) is A. So, d divides A.

The factor theorem can also be depicted as follows: If $d\ |\ D$ and $D\ |\ A$, then $d\ |\ A$, which means it’s also sometimes called the transitive property of divisibility.

We are now ready to begin our investigations of criteria for divisibility by 2, 3, 9, and 11. We will begin with the criterion when the divisor is 2. For the remainder of the theorems we will restrict ourselves to 4-digit dividends for simplicity. We must first identify the even digits:

Definition: The even digits are 0, 2, 4, 6, and 8

Theorem 6.2.3: (Divisibility Criterion for 2) A natural number is divisible by 2 (or even) if and only if its ones digit is even.

Proof: For simplicity, here we will only prove the case when the dividend has 4-digits. Let $n$ be a 4-digit number with an even ones digit. In expanded form

$n=1000a+100b+10c+d$, where $a,b,c,d$ are its digits. Since $d$ is an even digit it can be

represented as $2k$ where $k$ is some natural number (e.g. if $d=6,$ then $k=3$). This means we can

Rewrite $n$ as follows:

$n=1000a+100b+10c+2k=2(500a+50b+5c+k)$,

indicating that $n$ is a multiple of 2, so it’s even. Note that alternatively, we can use the Sum Theorem and state that since $2\ |\ 1000a$, $2\ |\ 100b$, $2\ |\ 10c$, and $2\ |\ d$, then it follows that 2 divides their sum, which is $n.$

Theorem 6.2.4: (Divisibility Criterion for 4) A number number is divisible by 4 if and only if the number formed by its tens and ones digits is divisible by 4.

Proof: Left as an exercise

Theorem 6.2.5: (Divisibility tests for 3, and 9)

A natural number is divisible by 3 if and only if the sum of its digits is divisible by 3.
A natural number is divisible by 9 if and only if the sum of its digits is divisible by 9.

Proof: Here we only prove the criterion for 3, and leave the one for 9 as an exercise. For simplicity we will also restrict ourselves to the case that this natural number has only 4 -digits. Let
$n=1000a+100b+10c+d$. We can rewrite this expanded for as follows:
$n=999a+a+99b+b+9c+c+d=999a+99b+9c+(a+b+c+d).$
Now, since we know that the sum of the digits of $n$ is divisible by 3, there exists a whole number $k$ such
that $a+b+c+d=3k$. Making the relevant substitution and factoring-out 3 we now have
$n=999a+99b+9c+3k=3(333a+33b+3c+k)$, showing that 3 divides $n$.

Theorem 6.2.6 (Divisibility Criterion for 11): A natural number is divisible by 11 if and only if the alternating sum of its digits is a multiple of 11.

Example 1: We know that 3894 is divisible by 11 because $3-8+9-4=0$, which is a multiple of 11 ($0\times 11=0)$.

Example 2: We can tell that 55,913 is divisible by 11 because $5-5+9-1+3=11$, which is a multiple of 11 $(1\times 11=11)$.

Proof of Theorem 6.2.6:

Proof: Once again, we will restrict ourselves to the 4-digit case. We rewrite the dividend $n$ in expanded form, and assume that $a-b+c-d=11k$ and rewrite $n$ as follows:

$n=1000a+100b+10c+d$
$=(1001a-a)+(99b+b)+(11c-c)+d$
$=\ (1001a+99b+11c)+(-a+b-c+d)$
$=\ 11(91a+9b+c)-11k$
$=11(91a+9b+c-k)$

The last expression indicates that $n$ is therefore a multiple of 11, proving the theorem.

Theorem 6.2.7: A natural number $n$ is divisible by 6 if and only if $2\ |\ n$ and $3\ |\ n$.

Proof: Suppose $6\ |\ n$, then by the Factor Theorem, $n$ must be divisible by all of the factors of 6, namely 2, and 3. Now, for the converse, suppose $2\ |\ n$, then $n=2k$ for some natural number $k$. Since we know that $3\ |\ n$ also, then $3\ |\ 2k$, meaning that $k=3l$ for some natural number $l$. So, $n=2\cdot 3\cdot l=6l$, showing that $6\ |\ n$.

Theorem 6.2.8: Let $n$ and $d$ be natural numbers, and let the prime factorization of $d={{p}_{1}}^{k1}\cdot {{p}_{2}}^{k2}\cdot ...\cdot {{p}_{n}}^{kn}$ where d is decomposed into $n$ distinct primes with corresponding multiplicities ${k}_{1}$, ${k}_{2}$,…${k}_{n}$

6.4 Exercises

Which of the following numbers are divisible by 3, by 9, or by 11?

2,838 34,521 (c) 10,234,341	(d) 792 (e) 8,394 (f) 26,341	(g) 333,333 (h) 179

Which of the numbers below divide the number 19,612,560
```
 3   4   5   6   8   9   11
```
Prove that if a 5-digit number $n$ has an even ones digit, then $2\ |\ n$. HINT: Start by letting $n=10,000a+1000b+100c+d$ and assume that d is an even digit, which means $d=2k$ for some whole number $k$.
Prove that a 4-digit number $n$ is divisible by 5 if its ones digit is either 0, or 5. HINT: Do it using two cases, one for each potentiality.
Prove that if a 5-digit number $n$ has tens and ones digits that are divisible by 4, then $4\ |\ n$. For example, we know that 4 | 23416 because 4 | 16, and similarly we know that $23438$ is not divisible by 4 because even though 38 is even, it’s not divisible by 4.
Prove that if the sum of the digits of a 5-digit number $n$ is a multiple of 9, then 9 | n.
Prove that if the alternating sum of a 6-digit number $n$ is a multiple of 11, then $11\ |\ n$. HINT: Let $n=100,000a+10,000b+1000c+100d+10e+f$. Now rearrange this sum in such a way as to ensure that each of the individual summands are divisible by 11. The remaining alternating sum $-a+b-c+d-e+f=-(a-b+c-d+e-f)$ can safely be assumed is divisible by 11
Determine for which value(s) of the digit X is it true that the number 81,X19 divisible by 11?
Determine for which value(s) of the digit X is the number 37X,364 divisible by 4?
Determine for which value(s) of the digit X is the number 37X,879 divisible by 3?
What criterion could we propose for divisibility by 8? State the criterion, and prove it for a 5-digit number.
Use algebraic, and diagram proof that if $a\ |\ b$, then $a\ |\ xb$ for any whole number $x$.
Prove algebraically that if $\ a\ |\ b$ and $a\ |\ c$ then $a\ |\ sb\ +\ tc$ for any integers $s$, and $t$.
Use algebraic proof to show that if $a\ |\ b$ and $a,b>0$, then $a\leq b$.
EXTRA CREDIT: Let $a,\ b,\ c,$ and $d$ be integers with $a,c\ne 0$ Prove that:

If $a\ |\ b$ and $c\ |\ d$, then $ac\ |\ bd$.
If $ac\ |\ bc$, then $a\ |\ b$.

16. EXTRA CREDIT: Prove that if $n$ is an odd integer, then ${4\ |\ (n}^{2}-1)$.

   17\.  EXTRA CREDIT:  Prove that for any natural numbers $a$, and $x$ if $a\ |\ {x}^{2}$, then $a\ |\ x$.

6.5 Primes, and the Fundamental Theorem of Arithmetic

Before proceeding, a brief note about the mathematical proofs that will be presented in this, and subsequent sections. Unlike in the previous section here we will be employing proof by contradiction, known in Latin as a reductio ad absurdum. This is a powerful method of proof that establishes the truth of a statement by assuming its negation and demonstrating that this assumption leads to a logical contradiction. Unlike direct proofs, which proceed by constructing a logical chain from assumptions to conclusion, proofs by contradiction rely on demonstrating that the negation of the desired conclusion cannot coexist with established truths or axioms. This method traces its roots to ancient Greek mathematics and philosophy, prominently used by Euclid in his proof of the infinitude of primes and by early philosophers like Aristotle. The structure of a proof by contradiction begins by assuming the opposite of what is to be proven, deriving logical consequences from this assumption, and arriving at an inconsistency that invalidates the negation. In the next two sections, this method will be employed to prove several critical theorems, showcasing its ability to address problems where direct proofs might be less effective or feasible.

Most whole numbers can be broken down into smaller whole numbers through a process called factoring. For example, 51 can be written as $3\times 17$, and 48 can be written as $6\times 8$. But the process doesn’t stop there. If we continue factoring, 6 becomes $2\times 3$, and 8 becomes $2\times 4$, with 4 breaking down further into $2\times 2$. Eventually, we reach numbers that can no longer be broken into smaller whole number factors. These are the prime numbers, the fundamental “building blocks” of all whole numbers. A prime number is unique because it can only be divided evenly by 1 and itself. The discovery that every whole number greater than 1 is either a prime number or can be expressed as a product of primes is known as the Fundamental Theorem of Arithmetic, a cornerstone of number theory and the study of mathematics.

Definition: A prime number is a whole number larger than 1 which is divisible by exactly two distinct whole numbers, namely by the prime number, and 1. All other whole numbers are called composite.

The first few primes numbers are: 2 3, 5, 7, 11, 13, 17, 19, 23, 29

The Sieve of Eratosthenes (c. 275 - 195 B.C.) is a method of identifying prime numbers by successively checking eac number. We begin by listing all whole numbers larger than 1, and underline 2. Since all multiples of 2 are not prime, we could cross them out:

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

Next, we underline 3, the next prime number, and cross-off all the multiples of 3, which can be guaranteed to not be prime. We can determine the composite which are multiples of 3 by adding their digits, and checking if the sum is divisible by 3:

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

Next, we underline 5, and cross-off all the multiples of 5, of which we have only 25, 35, and we 7 crossing off all its multiples, which include only 49 on the list below:

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

Note that all the remaining numbers already on this list which have not been crossed-off are primes.

Now that we have a method of finding prime numbers, let’s investigate how to find the prime-factorization of composite numbers. Suppose we want to prime factorize the number 24. We could use our knowledge of divisibility and note that 24 is divisible by 3 (since $2+4=6$) and by 2 (since the ones digit is 4), and therefore 24 is divisible by 6. We would then use the tree method to split up 24 into its factors 6 and 4, and then subsequently break-up 6 into 2, and 3, and 4 into 2 and 2.

This process must be continued until we reach prime numbers which cannot be factored anymore. Thus we have the leaves of the tree which form the prime factorization of 24: $24\ =\ 2\ \cdot 2\cdot 2\cdot 3\ =\ {2}^{3}\cdot 3$

Note that the factorization process using the tree method is not unique, and it can take place in several different ways. The end result is the same, however.

Lemma 6.3.1: Every whole number $N>1$ is a multiple of a prime.

Proof: We begin by listing all the factors of $N$ which are larger than 1.. Let $p>1$ be the smallest factor of $N$. We claim that $p$ must be prime. Otherwise, suppose there is a $t$ which divides $p$. Now this would mean $1<t<p$. Then by the Factor Theorem (Theorem 6.2.2), it follows that $t$ divides $N,$ and since $1<t<p<N$, it follows that $N$ has a smaller factor than $p$, which contradicts the fact that $p$ was chosen as the smallest factor. Therefore, $p$ is a prime factor of $N$.

Theorem 6.3.1. (The Fundamental Theorem of Arithmetic): Every whole number $N>1$ can be written as a product of primes uniquely.

Proof: (Existence) Let $N$ be a whole number, and let ${p}_{1}$ be its prime factor (Lemma 6.3.1). Therefore $N={p}_{1}{n}_{1}$ where ${n}_{1}$ is some whole number. If ${n}_{1}$ is prime, then we are done. Otherwise, if ${n}_{1}$is composite, again by Lemma 6.3.1, it has a prime factor ${p}_{2}$ such that ${n}_{1}={p}_{2}{n}_{2}$, implying that we can rewrite $N$ as follows:

$N={p}_{1}{p}_{2}{n}_{2}$

We can continue this process, obtaining a decreasing sequence of whole numbers ${n}_{1},{n}_{2},{n}_{3},...$ This means that either one of the ${n}_{i}$ will be prime, or ${n}_{i}=1$ for some natural number $i$. Once that happens we can write:

$N={p}_{1}{p}_{2}{p}_{3}...{p}_{i-1}$

Proof: (Uniqueness) See Theorem 6.4.3

Now that we understand the importance of prime numbers as building blocks for all whole numbers, we may want to devise a plan in identifying them. The method of the Sieve of Eratosthenes can certainly identify them, but this is a highly tedious process. For example, how would we go about determining whether 101 is a prime number? Are we to check for all potential factors of 101 by checking all consecutive natural numbers starting with 2 all the way to 101? Certainly not! We need not check all natural numbers between 1 and 101 because the primes are sufficient (think about why!). But should we check all the prime divisors of 101? Here too the answer is no! It turns out that we need only check up to primes which are less than $\sqrt{101}.$

Theorem 6.3.1 The Primality Test: To determine whether a whole number $N$ is prime it is sufficient to check for all prime divisors up to the prime $p$ such that ${p}^{2}\leq N$.

Proof: Suppose a given whole number $N$ is not divisible by 2, 3, 5, …, $p$ where ${p}^{2}\leq N.$ We will show that $N$ must be prime, and cannot be divisible by any other prime larger than $p$. Suppose $q$ is prime and $q>p$, and $q$ divides $N$. Let $N/q=s$. We claim that $s$ must be less than $p$. To see why, suppose for the sake of contradiction that $s\geq p$. Then $qs\geq qp$. But $qs=q\cdot \frac{N}{q}\ =\ N$, which means $N\geq qp>{p}^{2}$, which contradicts the assumption that ${p}^{2}\leq N$. It follows that $s<p.$ Now either $s$ is prime, or has prime factors smaller than $p$, and given that $s$ is a factor of $N$, it follows that there are prime factors which divide $N$, contradicting the assumption that all prime factors up to $p$ do not divide $N$. Therefore it follows that $N$ does not have any other prime factors larger than $p$.

Example 1: Determine whether 101 is a prime number.
Solution: We must check all potential prime divisors 2, 3, 5, … up to a prime $p\leq \sqrt{101}\approx 10$. This means we must check only up to 7. Now we know that 101 is not divisible by 2 since it has an odd ones digit. It’s not divisible by 3 because $1+0+1=2$, and 3 does not divide 2. It’s not divisible by 5 because its ones digit is neither 0 nor 5. Finally, it’s not divisible by 7 because 101 divided by 7 leaves a remainder. Therefore 101 is a prime number.

Example 2: Determine whether 4807 is a prime number.

Solution: Now the $\sqrt{4807}\approx 70$, thus we must check all primes up to 70. Note that $4-8+0-7=-11$, and since this is a multiple of 11, it follows that 4807 is not prime.

The question of whether there are infinitely many prime numbers is one of the oldest and most profound inquiries in mathematics. Primes, the building blocks of integers, have intrigued mathematicians since antiquity. The Greeks, particularly Euclid, made significant contributions to this question, culminating in a proof that primes are indeed infinite. This result, presented in Euclid’s Elements around 300 BCE, marked a foundational achievement in number theory.

Theorem 6.3.2: There are infinitely many prime numbers.

Proof: We proceed by contradiction. Assume, for the sake of contradiction, that there are only finitely many primes. Let these primes be ${p}_{1},{p}_{2},...{p}_{n}$. Define the number $N$ as the product of all these primes plus one:

$N={p}_{1}\cdot {p}_{2}\cdot {p}_{3}\cdot ...\cdot {p}_{n}+1$

By construction, N is not divisible by any of the primes ${p}_{1},{p}_{2},...{p}_{n}$ , because dividing N by any ${p}_{i}$ leaves a remainder of 1. Therefore, N must either be a prime itself or have a prime factor not included in the original list.
In either case, this contradicts the assumption that ${p}_{1},{p}_{2},...{p}_{n}$represent all the primes. Hence, our assumption that the number of primes is finite must be false. Therefore, there are infinitely many primes.

Finally, a note about counterexamples in mathematics. A counterexample is a specific instance or example that demonstrates a claim or statement is false. Even if a claim seems broadly true, finding just one counterexample is sufficient to disprove it, highlighting the importance of precision in mathematical reasoning. Counterexamples are particularly useful when the claim is a universal one, claiming that a property is true quantified over all instances. For instance, the statement “All prime numbers are odd” can be refuted by the counterexample 2, which is a prime number but not odd. Similarly, the claim “the square of any real number is greater than or equal to the number itself” is false because $(\frac{1}{2}{)}^{2\ }=\frac{1}{4}<\frac{1}{2}$. Counterexamples play a crucial role in refining conjectures and ensuring mathematical rigor.

6.6 Exercises

Find the prime factorization of the following composites (HINT: Be sure to use the divisibility rules of section 6.2 to determine whether any of these numbers are divisible by 2, 3, 5, 11. Then use the tree method. Be sure to write the prime factorization in exponential notation.)

600 7920 154 10,000	2057 31,625 97 33,792

2. The list of factors of 40 can be written as follows:

1	2	4	5
40	20	10	8

Note that 1 and 40, 2 and 20, 4 and 10, are “partner” factors because their product makes 40.

Make a similar table of factors for the numbers 68, 36, 84, and 144. Do you see a pattern? Why do some numbers have an even number of factors, while others have an odd number of factors?
Prove that a number $N$ has an even number of factors unless it is the square of a whole number.

3. For the following problems, note that $7!$ is pronounced “7 factorial”, and it represents the product of consecutive whole numbers from 1 to 7: $7!=\ 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$. Note that numbers written in factorial notation can be easily prime-factorized. For example, $7!\ =\ 7\cdot (2\cdot 3)\cdot 5\cdot (2\cdot 2)\cdot 3\cdot 2\cdot 1=\ {2}^{4}\cdot {3}^{2}\cdot 5\cdot 7$. Note that the standard decimal form of $7!$ is 5040.

Note that while $7!$ is a fairly large number, were able to prime factorize it fairly easily.

Write the prime factorization of $12!$ in exponential form as above.
Is $12!$ divisible by 10, 30, 120, 1000, or 10,000? HINT: First prime factorize these potential divisors, then determine whether $12!$ has a sufficient number of copies (multiplicities) of their corresponding prime factors.
Is $30!$ divisible by 2,400,000?
Which is larger ${2}^{10}$ or $10!$? Explain!
What is the remainder when 13! is divided by 17? Explain how you would know the answer without using a calculator, or actually dividing?
Find the largest $n$ such that 20! Is divisible by $1{2}^{n}$.

4. How many zeros are at the end of the decimal form of the following numbers? HINT: Count the number of copies of $10=2\cdot 5$ in their prime factorization.

10!
50!
1000!

5. Determine which of the following numbers are prime. Be sure to provide an explanation outlining the reasoning you used in making that determination with or without a calculator.

6. Determine whether the following statements are true, or false. If false, provide a counterexample. If true, provide a proof.

All odd numbers are prime.
For any two integers $a$, and $b$, it follows that $(a+b{)}^{2}={a}^{2}+{b}^{2}$.
For any natural number $n=0,1,2,3,4,...$, it follows that ${n}^{2}+n+11$ is a prime number.
All prime numbers larger than 2 do not have an even ones digit.
All prime numbers larger than 5 must have a 3, 7, or a 9 in the ones digit.
If $n$ is composite, then all of its divisors are also composite.
The sum of any two prime numbers larger than 2 is even.
The sum of any consecutive three numbers is divisible by 3.

7. For the following exercises, begin by explaining why 7! Is divisible by 2, 3, 4, 5, 6, and 7.

Prove that the number 7!+2, 7!+3, 7!+4, 7!+5, 7!+6, and 7!+7 are all composite by providing a factor for each.
Is the number 37! + 23 prime or composite? Explain!
Find 1000 consecutive numbers that are composite. HINT: Start with 1000! + 2

8. Prove that every prime number $p>3$ when divided by 6 will either result in a remainder of 1 or 1 less than $p$. In other words, for any prime $p>3$, $p\equiv 1\ (mod\ 6)$ or $p\equiv -1\ (mod\ 6)$. For example, if $p=23$, then 23 divided by 6 results in 5 for a remainder. In other words, $23\equiv \ 5\ (mod\ 6)$. Similarly, if $p=37$, then $37\ \equiv 1\ (mod\ 6)$. HINT: By the Quotient-Remainder Theorem (Theorem 3.3.1), we can write $p=6q+r$ for some whole numbers $q$ and $r$ where $0\leq r<6$. Since we know that $p$ is prime, we can eliminate options for $r.$

6.7 The GCF, and LCM

6.7.1 The Greatest Common Factor

The concepts of the Greatest Common Factor (GCF) and Least Common Multiple (LCM) make use of the prime factorization ideas already discussed. THe GCF, and the LCM are essential for simplifying fractions, enabling students to express answers in their simplest form and fostering a deeper understanding of equivalence in fractions. The GCF particularly helps in problem-solving scenarios that involve dividing quantities into equal parts or groups, reinforcing number sense and divisibility. The LCM, on the other hand, plays a pivotal role in operations with fractions, particularly when finding common denominators for addition and subtraction. It also aids in solving problems related to repeating cycles or patterns, encouraging students to see relationships between numbers. By emphasizing the importance of GCF and LCM, teachers can equip students with the tools they need to approach fractions and number theory with confidence and accuracy.

Let’s begin with the idea of the GCF. For example, let’s list all the factors of 24, and 36:

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

Factors of 36: 1, 2, 3, 4, 6, 9, 12, 36

It’s clear that 24, and 36 have common factors, namely 1, 2, 3, 4, 6, and 12, and the last one on this list is the largest common factor. This Listing Method is not the most efficient method of finding the greatest common factor. But first, let’s formulate the formal definition.

Definition: The Greatest Common Factor of two numbers $a$ and $b$ is the greatest whole number which is a factor of both $a$ and $b$. We will write GCF (a,b) to denote this number, and set $GCF(a,0)=a$ for all nonzero whole numbers $a$.

Note that some elementary books sometimes use the term GCD (Greatest Common Divisor, or Denominator in the context of fractions).

When these numbers are large it is much more efficient to use other methods. There are three primary routes for finding the greatest common factor (GCF) of two numbers: the listing method, where you list the factors of each number and identify the largest common one; the common primes method, where you break each number into its prime factors and multiply the common prime factors; and the Euclidean Algorithm, which uses division to efficiently compute the GCF.

The common primes method works because every number can be uniquely expressed as a product of primes (prime factorization). The GCF is determined by multiplying all the prime factors that appear in both numbers with the smallest power of each common factor, as this represents the largest number that divides both.

Example 1: Calculate GCF (90, 300).

We begin by prime-factoring both of these numbers, and arranging these primes in separate columns, organizing them in such a way as to list all common prime factors underneath one another:

90 =	2 $\cdot$	3 $\cdot$	3 $\cdot$	5
300 =	2 $\ \cdot$	3 $\cdot$		5 $\cdot$	2 $\cdot$	5

Since the common factors of 90, and 300 are 2, 3, and 5, it follows that GCF (90, 300) = $2\cdot 3\cdot 5\ =\ 30$

Example 2: Calculate the GCF of the following numbers already in prime-factored form: ${2}^{3}{\cdot 3}^{2}\cdot 5\cdot {7}^{2}$, and ${2}^{2}\cdot {3}^{5}\cdot {5}^{2}\cdot 11$.

Solution: We do not need to evaluate the actual values of these numbers because the hard work of prime-factoring has been done for us. We merely need to collect their common primes. They appear to have two copies of 2 in common, two copies of 3, one copy of 5, and that’s it! Thus,

$GCF({2}^{3}{\cdot 3}^{2}\cdot 5\cdot {7}^{2},\ \ \ {2}^{2}\cdot {3}^{5}\cdot {5}^{2}\cdot 11)\ =\ {2}^{2}\ \cdot {3}^{2}\cdot 5$

The key here is to select from the common primes, picking the smaller of the two exponents.

The Euclidean Algorithm

Suppose we are looking for the GCF of two large numbers $a$ and $b$. These numbers may be so large that both the listing, and the common primes method would be prohibitively difficult. Instead, what if we were to try dividing $a$ by $b$ (suppose $a>b$)? By the division algorithm we would obtain a quotient $q$ with a possible remainder $r$: $a=qb+r$.

Now, suppose $n$ is a factor of b, and r, then by the Sum Theorem (Theorem 6.2.1) $n$ would be a factor of $qb+r$, which means it’s a factor of $a$. But we also have $r=a-qb$, which means that $n$ must a factor of both $a$ and $b$. This means that whatever is a common factor of $a$ and $b$ must also be a common factor of $b$ and $r$.

Let’s see this method via an example.

Example 3: Find the $GCF(2520,2002)$!

Solution: We begin by dividing 2520 by 2002, giving us a remainder of 518. Thus, we can write:

$GCF(2520,2002)\ =\ GCF\ (2002,\ 518)$

We now repeat this process, dividing 2002, and 518. Now 518 goes into 2002 at most 3 times, giving us 1554, with a remainder 448. Thus, we write:

$GCF(2520,2002)\ =\ GCF\ (2002,\ 518)=\ GCF\ (518,\ 448)$

Continuing this process, we get:

$GCF(2520,2002) = GCF (2002, 518)= GCF (518, 448) = GCF (448, 70) =GCF(70,28) $

$=GCF(28,14)=14 $

6.7.2 The Least Common Multiple

Let’s find the Least Common Multiple of 12, and 30 using the listing method. We will begin by listing their corresponding multiples:

Multiples of 12: 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, 132, 144, 156, 168, 180, 192, 156, 168, 180,

Multiples of 30: 30, 60, 90, 120, 150, 180, 210, 240, 270, …

It appears that 120 is the least of the common multiples. By the way, the listing method would reveal other multiples like 240, 360, 480, etc… i.e. the other common multiples will be multiples of 120, the least of the common multiples.

As you would expect, the listing method is the least efficient method of finding the LCM. Instead for most cases we would use the common primes method. Let’s think about the common multiples of 12, and 30. Now, $12=2\cdot 2\cdot 3$ while $30=2\cdot 3\cdot 5$. Any multiple of 12 would have to contain all the prime factors of 12, and having at least their corresponding multiplicities. Thus, the LCM of 12, and 30 must contain at least 2 copies of 2, and at least 1 copy of 3 (because 2 has multiplicity 2, and 3 has a multiplicity 1 in 12), and since the LCM must be a common multiple, it must also contain one copy of 5 (since 30 contains this 5). Thus, the $LCM(12,30)=2\cdot 2\cdot 3\cdot 5=60$

Example 1: Find the Least Common Multiple of 60, and 84.

Solution: We begin by prime-factoring 60, and 84 and listing their primes in separate columns, grouping the common ones:

$60 =$	$2\ \cdot$	2 $ $	3 $$	5
$84 =$	2 $ $	2 $ $	3 $\cdot$		7
LCM =	2	2	3	5	7

We then bring-down all the prime-factors (and not just the common ones). This way we ensure that the product of these primes will be the LCM. Thus, $LCM(60,\ 84)\ =\ 2\cdot 2\cdot 3\cdot 5\cdot 7=420$

Example 2: Find the Greatest Common Factor, and the Least Common Multiple of 1848 and 1980

Solution: We begin by prime factoring the two numbers using the tree method:

We notice that $(1+4)-(8+8)=5-16=-11$, which is a multiple of 11, indicating that 1848 is divisible by 11. Similarly, we notice that 168 is divisible by 4 because 68 is divisible by 2 twice. The rest of the prime factorization is easy. The prime factorization of 1848 is as follows: $1848\ =\ {2}^{3}\cdot 3\cdot 7\cdot 11$
In a similar fashion we notice that 1980 is divisible by 11 because: $(1+8)-(9+0)=0$ and 0 is divisible by 11. Thus, we divide 1980 by 11, obtaining 180, then split this up into $10\cdot 18$, and so on. THus: $1980\ =\ {2}^{2}\cdot {3}^{2}\cdot 5\cdot 11$ These prime factorizations are represented in the chart below.

1748	2	2	2	3	7	11
1980	2	2		3		11	3	5
GCF	2	2		3		11
LCM	2	2	2	3	7	11	3	5

To form the GCF in the above chart, we “bring down” those factors which 1748, and 1980 have in common. To form the LCM, we simply “bring down” all of the primes. Thus,

$GCF\ (1748,1980)\ =\ 2\cdot 2\cdot 3\cdot 11=132$

$LCM(1748,1980)=2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5\cdot 7=2,520$

If we look back at the table for 1748, and 1980 we notice that the LCM consists of the products of primes of 1748, and 1980 except it does not include the duplicate copies which appear in the GCF. This means that the products of the GCM, and LCM should be the product of the two numbers:

Theorem 6.4.1: $GCF(a,b)\cdot LCM\ (a,b)\ \ =\ ab$

This above equation also provides an alternative way to computer the LCM:

$LCM(a,b)\ =\ \frac{ab}{GCF(a,b)}$

Example 3: Find the Least Common Multiple of 10101, and 10104.

Solution: It’s much easier to first find the GCF of these numbers by using the Euclidean Algorithm, then use Theorem 6.4.2 to find the Least Common Multiple. We proceed by dividing the larger by smaller, and obtain a remainder of 3. Thus, we write:

$GCF(10104,10101)=GCF(10101,3)$

Now, since $1+0+1+0+1=3$, it follows that $3|10101$. Thus, we can say:

$GCF(10104,10101)=GCF(10101,3)=3$

Now using Theorem 6.4.2 we can say:

$LCM(10104,10101)\ =\ \frac{10104\cdot 10101}{GCF(10104,10101)}=102,060,504\div 3\ =34,020,168$

Proof of the Fundamental Theorem of Arithmetic

Recall that we have already shown that every whole number can be written as a product of primes. In this section we will complete the proof of the full statement of the Fundamental Theorem of Arithmetic, which further stipulates that this representation of numbers as products of primes should be unique. This effectively states that there is only one way to represent any whole number as a product of primes (except for reordering the factors). For the final proof we will need two lemmas:

Lemma 6.4.1 (Bezout’s Lemma): Let $a$, and $b$ be whole numbers. Then there exist integers $s,t$ such that

$GCF(a,b)=sa+tb$

Proof: Let’s collect all possible positive linear combinations of the two whole numbers $a$, and $b$, and put them in a set S. $S=\{sa+tb$ | $s,\ t$ are integers such as $sa+tb>0$}. Since S is a collection of positive whole numbers it must have a smallest element. Let’s call this element $d$. We will show (part 1) that $d$ is a common factor of $a$ and $b$, and (part 2) that $d$ is the greatest common factor.

Part 1: First, let’s show that $d$ is a factor of $a$. Suppose $d$ doesn’t divide $a$. Then by the Quotient-Remainder Theorem (Theorem 3.3.1) there is a $q$ and an $r$ such that

$a\ =\ dq\ +r$ where $0\leq r<d$

Let’s solve for $r$, and replace $d$ with $sa+tb$ (since $d$ is one of the elements of $S$):

$r=a-dq=a-(sa+tb)q=a-qsa-qtb=(1-qs)a-(qt)b$

Now, since $(1-qs)$ is an integer, and $qt$ is also an integer, it follows that $r$ is in the form $sa+tb$, implying that $r$ must be one of the numbers in $S$. However, since $d$ was the smallest element in $S$, and we know that $r<d$ (by the Quotient Remainder Theorem), it follows that $r=0$. This means that $d$ does divide $a$. A similar argument will show that $d$ divides $b$, indicating that $d$ is the common factor of $a$ and $b$

Part 2: Now we must show that $d$ is the greatest of the common factors. To show this, we will presume there is another common factor, and show that this common factor must be less than $d$. Suppose there is another common factor $c$ which divides $a$, and $b$. This means there are whole numbers $u$ and $v$ such that $a=cu$ and $b=cv$. Now we know that $d$ was from $S$ so $d=sa+tb$ for some integers $s$ and $t$. So, we can write:

$d=sa+tb=s(cu)+t(cv)=c(su)+c(tv)=c(su+tv)$

This indicates that $c|d$, which means that $c\leq d$.

Lemma 6.4.2: (Euclid’s Lemma) Let $p$ be a prime number which divides $ab$. Then $p$ is a factor of either $a$ or $b$.

Proof: If $p$ is a factor of $a$, then we are done. Otherwise, this means $GCF\ (a,p)=1$. By Bezout’s Lemma, we can find integers $t$ and $s$ such that $sa+tp=1$. Now we multiply both sides by $b$:

We are now ready to complete the uniqueness component of the proof of the Fundamental Theorem of Arithmetic. Let’s suppose there are two different ways to factor a positive integer $n$ into primes:

$n={p}_{1}{p}_{2}...{p}_{k}$ and $n={q}_{1}{q}_{2}...{q}_{m}$,

Where each ${p}_{i}$ and each ${q}_{i}$ are primes. Our goal is to show that in fact the multisets¹ $\{{p}_{1},{p}_{2},..,{p}_{k}\}$ and $\{{q}_{1},{q}_{2},...{q}_{m}\}$ consist of exactly the same primes, but possibly in a different order.

To show that these sets are the same, let’s pick a prime ${p}_{1}$ from the first set. It clearly divides $n$, so it must also divide ${q}_{1}{q}_{2}...{q}_{m}$. Now by Euclid’s Lemma above, ${p}_{1}$ must therefore divide one of ${q}_{1}$, ${q}_{2}$, …${q}_{m}$. Let’s say it divides ${q}_{j}$. But since ${q}_{j}$ is prime, this could only mean that ${p}_{1}={q}_{j}$. At this point we perform a rearranging so that ${q}_{j}$ is labelled as ${q}_{1}$, so that ${p}_{1}={q}_{1}$, and we divide both sides of the following equations so that we now have:

$n/{p}_{1}={p}_{2}...{p}_{k}$ and $n/{q}_{1}={q}_{2}...{q}_{m}$

By continuing this process with the new number $n/{p}_{1}$ and $n/{q}_{1}$ we will be able to match each of ${p}_{i}$ to the ${p}_{j}$.

6.7.3 The Teaching Sequence for Number Theory as per California Common Core Standards

Below is a grade-by-grade overview (starting at Grade 4) of the California Common Core State Standards for Mathematics as they relate to number theory topics. The summary is based on the August 2013 version of the standards published by the California Department of Education. Please note that while traditional number theory concepts (e.g., prime factorization, divisibility tests, and algorithms such as the Euclidean Algorithm) are useful for understanding and mastering various arithmetic skills, they are sometimes only implied in the standards rather than explicitly named.

Grade 4

In Grade 4, 4.OA.B.4 introduces foundational number theory concepts by having students find all factor pairs of numbers from 1 to 100 and determine whether each number in that range is prime or composite. This standard helps them understand the structure of whole numbers and sets the stage for later work with factors and multiples.

Grade 5

In Grade 5, 5.NBT.B.6 focuses on building proficiency with whole-number division, requiring students to compute quotients of four-digit dividends by two-digit divisors. While this reinforces important arithmetic skills, no additional number-theory-specific standards (such as prime factorization or greatest common factor) are introduced at this level.

Grade 6

In Grade 6, 6.NS.B.4 expands students’ number theory knowledge by guiding them to find the greatest common factor (GCF) of two whole numbers (up to 100) and the least common multiple (LCM) of two whole numbers (up to 12). This often involves prime factorization strategies and underscores the importance of understanding how numbers break down into products of primes.

6.8 Exercises

Find the Greatest Common Factor of the following pairs of numbers using the listing method:
1. 42, and 70
2. 60, and 64
Find the Greatest Common Factor of the following pairs of numbers using the common primes method:
1. 94, and 60
2. 144, and 90
3. 1000, and 1440
4. 32, and 81
5. 25, and 49
6. ${2}^{3}\cdot {3}^{4}\cdot 5\cdot {7}^{3}$, and ${2}^{4}\cdot 3\cdot {5}^{2}\cdot 11\cdot 1{3}^{2}$
Find the Least Common Multiples of the following pairs of numbers using the listing method:
1. 9, and 12
2. 8, and 12
Find the GCF, and LCM of the following pairs of numbers using the common primes method:
1. 32, and 48
2. 144, and 160
3. 125, and 75
4. 16, and 27
5. $2\cdot {3}^{3}\cdot {7}^{2}\cdot 11$ and ${2}^{4}\cdot 3\cdot {7}^{2}\cdot 13$
6. 1,007,001 and 1,007,010 (For this, and the subsequent problem be sure to show work on solving this problem by hand aside from the actual multiplication, and division operations. Be sure to show how you would do it completely by hand if you had to.)
7. 1,062,347 and 1,062,336
How can teachers use students’ initial understanding of prime and composite numbers in Grade 4 (4.OA.B.4) to deepen their reasoning about finding the greatest common factor (GCF) and least common multiple (LCM) in Grade 6 (6.NS.B.4)?
In what ways might the ability to factor numbers and identify primes in earlier grades influence students’ problem-solving strategies when they tackle more complex arithmetic and algebraic concepts in later grades?

A multiset differs from a set in that it allows for repetitions of elements. Thus, {1,2,2} is a multiset, but a set would normally not permit the repeated copy of the 2, and would just state {1,2}.↩︎

$60 =$	\(2\ \cdot\)	2 $ $	3 $$	5
$84 =$	2 $ $	2 $ $	3 \(\cdot\)		7
LCM =	2	2	3	5	7