Introduction to Number Theory and Divisibility

Math 205: Number Theory

Contents
1 Course Overview and Textbook 2
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Course Syllabus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Course Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Divisibility Theory in the Integers 2

2.1 Definition of Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Examples and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Example Problem: Triangular Numbers 3

3.1 Definition of Triangular Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Properties of Triangular Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3 Proof of Property 2 (Relation to Perfect Squares) . . . . . . . . . . . . . . . . . . . . 4
3.4 Proof of Property 3 (Sum of Consecutive Triangular Numbers) . . . . . . . . . . . . 6

4 Triangular Numbers and Binomial Coefficients 6

4.1 The Relationship . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2 Review of Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 Proof of the Binomial Relationship . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

5 Example Problem: Pentagonal Numbers 7

5.1 Definition of Pentagonal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.2 Relations Between Number Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1
Math 205: Number Theory Introduction to Number Theory and Divisibility

1 Course Overview and Textbook

1.1 Introduction
The lecture begins an outline of the course structure. The primary textbook for this course is
”Elementary Number Theory” by David M. Burton. This text is particularly relevant as it includes
chapters on the applications of number theory in modern fields like cryptography.

1.2 Course Syllabus

The main topics to be covered in this course include:

• Divisibility and Euclidean Algorithms

• Diophantine Equations

• Prime Numbers, including the Fundamental Theorem of Arithmetic, the Sieve of Eratos‐
thenes

• Congruencies

• Key theorems: Chinese Remainder Theorem, Fermat’s Little Theorem, Wilson’s Theorem,
and Euler’s Totient Theorem

• Number‐Theoretic Functions

1.3 Course Preliminaries

Chapter 1 of the textbook, which covers preliminaries, will not be formally taught in this lecture
series. Students are expected to be familiar with these topics from previous courses (e.g., Math
104). Key concepts to review include:

• Mathematical Induction

• The Binomial Theorem

The course will officially begin with the material from Chapter 2.

2 Divisibility Theory in the Integers

This section introduces the core concept of divisibility, which is the foundation for much of num‐
ber theory. As the mathematician H. Minkowski stated, ”Integral numbers are the fountainhead of
all mathematics.”

2.1 Definition of Divisibility

The concept of divisibility describes the relationship between two integers when one can be
evenly divided by the other without leaving a remainder.

Definition: Divisibility

An integer b is said to be divisible by an integer a ̸= 0 if there exists some integer c such

that b = ac.

2
Math 205: Number Theory Introduction to Number Theory and Divisibility

Notation: We write
a|b
to indicate that a divides b.
Terminology:

• a is a divisor or factor of b.

• b is a multiple of a.

2.2 Examples and Notation

It is crucial to distinguish between the active statement (”divides”) and the passive statement (”is
divisible by”).

Examples: Divisibility Notation

• Example 1: We say ”2 divides 6” because there is an integer (3) such that 6 = 2 × 3.

The notation for this is:
2|6

• Example 2: We can also say ”6 is divisible by 2”.

• Non‐Example: ”4 does not divide 6” because there is no integer c for which 6 = 4c.
The notation for non‐divisibility is:

4∤6

3 Example Problem: Triangular Numbers

This section explores a special class of numbers, known as triangular numbers, which are defined
by summing consecutive integers. This serves as an initial exercise in applying number theory
concepts.

3.1 Definition of Triangular Numbers

The ancient Greeks identified numbers that could be represented as dots arranged in an equilat‐
eral triangle.

Definition: Triangular Number

A triangular number is a number obtained by adding all positive integers up to a given

integer n. It is the sum of a consecutive arithmetic progression starting from 1.
The sequence of triangular numbers begins:
• T1 = 1
• T2 = 1 + 2 = 3
• T3 = 1 + 2 + 3 = 6
• T4 = 1 + 2 + 3 + 4 = 10

3
Math 205: Number Theory Introduction to Number Theory and Divisibility

• ...and so on.

T4 = 10
T3 = 6
T2 = 3
T1 = 1

Figure 1: Visual representation of the first four triangular numbers.

3.2 Properties of Triangular Numbers

The problem presented several properties related to triangular numbers, which can be proven
using methods like mathematical induction.

Properties of Triangular Numbers

• The General Formula:

Formula
A number is a triangular number if and only if it is of the form:

n(n + 1)
Tn =
2
for some integer n ≥ 1. This is the well‐known formula for the sum of the
first n positive integers.

• Relation to Perfect Squares: A perfect square is an integer that is the square of

another integer (e.g., 1, 4, 9, 16, …). A key problem is to determine the relation‐
ship between triangular numbers and perfect squares. For instance, an integer n is
triangular if and only if 8n + 1 is a perfect square.

• Sum of Consecutive Triangular Numbers: The sum of any two consecutive trian‐
gular numbers is a perfect square.
– Example: T2 + T3 = 3 + 6 = 9 = 32
– Example: T3 + T4 = 6 + 10 = 16 = 42

3.3 Proof of Property 2 (Relation to Perfect Squares)

Proof: Triangular Numbers and Perfect Squares

This section provides a proof for the statement: ”The integer n is a triangular number if
and only if 8n + 1 is a perfect square.”

1. Forward Direction (⇒):

• Assume: n is a triangular number.
• By definition, this means that for some integer k ≥ 1, n can be written as the

4
Math 205: Number Theory Introduction to Number Theory and Divisibility

sum of the first k integers:

k(k + 1)
n = Tk = 1 + 2 + · · · + k =
2
• Goal: Show that 8n + 1 is a perfect square.
• Substitute the expression for n:
( )
k(k + 1)
8n + 1 = 8 +1
2

• Simplify the expression:

8n + 1 = 4k(k + 1) + 1
= 4k 2 + 4k + 1

• This is a perfect square trinomial, which factors to:

8n + 1 = (2k + 1)2

• Since k is an integer, 2k + 1 is also an integer. Therefore, 8n + 1 is a perfect

square.
2. Converse Direction (⇐):
• Assume: 8n + 1 is a perfect square. Let’s call it m2 for some integer m ≥ 0.
8n + 1 = m2

• Goal: Show that n must be a triangular number.

• Observation: Note that 8n is an even number. Therefore, 8n + 1 must be an
odd number.
• Since m2 is an odd perfect square, its square root m must also be an odd inte‐
ger.
• Because m is an odd integer, it can be written in the form 2k + 1 for some
integer k ≥ 0.
• Substitute this back into our assumption:
8n + 1 = (2k + 1)2

• Now, we solve this equation for n:

8n + 1 = 4k 2 + 4k + 1
8n = 4k 2 + 4k
4k 2 + 4k k2 + k
n= =
8 2
• Factoring the numerator gives:
k(k + 1)
n=
2
• This is precisely the formula for the k‐th triangular number. Thus, n is a trian‐
gular number.

5
Math 205: Number Theory Introduction to Number Theory and Divisibility

3.4 Proof of Property 3 (Sum of Consecutive Triangular Numbers)

Proof: Sum of Consecutive Triangular Numbers

We can prove this identity directly using the formula for triangular numbers:

(k − 1)k k(k + 1)
tk−1 + tk = +
2 2
Factoring out the common term k2 :

k
tk−1 + tk = [(k − 1) + (k + 1)]
2
k
= (2k)
2
= k2

This confirms the identity.

4 Triangular Numbers and Binomial Coefficients

This section introduces another property of triangular numbers, connecting them to binomial
coefficients (combinations).

4.1 The Relationship

The problem states that the n‐th triangular number, denoted as tn , can be expressed in terms of
binomial coefficients.

Formula: Triangular Numbers as Binomial Coefficients

The n‐th triangular number is given by the binomial coefficient:

( )
n+1
tn =
2

4.2 Review of Binomial Coefficients

( )
The notation nr is read as ”n choose r” and is also written as nCr or C(n,r). It represents the
number of ways to choose r items from a set of n distinct items.

Definition: Binomial Coefficient

The value of the binomial coefficient is calculated as:

( )
n n!
= n Cr =
r r!(n − r)!

These coefficients are famously arranged in Pascal’s Triangle. Some fundamental properties
include:
( )
• n0 = 1

6
Math 205: Number Theory Introduction to Number Theory and Divisibility

(n )
• n =1
(n ) ( n
)
• Symmetry: r = n−r

4.3 Proof of the Binomial Relationship

Proof: tn

To prove this relationship, we evaluate the binomial coefficient on the right‐hand side
and show that it equals the formula for the n‐th triangular number.

• Start with the binomial coefficient:

( )
n+1
2

• Apply the definition:

(n + 1)! (n + 1)!
= =
2!((n + 1) − 2)! 2!(n − 1)!

• Expand the factorial in the numerator: The term (n + 1)! can be written as (n + 1) ·
n · (n − 1)!.
(n + 1) · n · (n − 1)!
=
2 · (n − 1)!

• Cancel the (n − 1)! terms:

n(n + 1)
=
2
• This result is the exact formula for the n‐th triangular number, Tn . The proof is
complete.

5 Example Problem: Pentagonal Numbers

Similar to triangular and square numbers, the ancient Greeks also defined pentagonal numbers
based on geometric arrangements of dots.

5.1 Definition of Pentagonal Numbers

Definition: Pentagonal Numbers

These numbers represent the total number of dots in a pattern of nested pentagons. The
sequence of pentagonal numbers, denoted pn , is:

1, 5, 12, 22, . . .

This sequence is generated by summing the terms of an arithmetic progression where

the common difference is 3:

• p1 = 1

• p2 = 1 + 4 = 5

7
Math 205: Number Theory Introduction to Number Theory and Divisibility

• p3 = 1 + 4 + 7 = 12

• p4 = 1 + 4 + 7 + 10 = 22

The general formula for the n‐th pentagonal number is:

n(3n − 1)
pn =
2
It can also be defined recursively:

pn = pn−1 + (3n − 2) for n ≥ 2, with p1 = 1

5.2 Relations Between Number Types

The lecture concludes by presenting relationships between pentagonal, square, and triangular
numbers, which are left as exercises for the student to verify.

Relations with Other Number Types

(a) pn = tn−1 + n2

(b) pn = 3tn−1 + n = 2tn−1 + tn

These relationships highlight the interconnectedness of different classes of numbers and serve
as good practice for applying the formulas and definitions covered.