Number Theory

Divisibility
Definition:
If a and b are integers with a ̸= 0, we say that a divides b if there
is an integer c such that b = ac, or equivalently, if ba is an integer.
When a divides b we say that a is a factor or divisor of b, and
that b is a multiple of a.
The notation a|b denotes that a divides b. We write a ̸ |b when a
does not divide b.
We can express a|b using quantifiers as ∃c(ac = b).

Example: 3 | −9 but 5 ∤ 7.
Example: Let n and d be positive integers. The number of positive
integers not exceeding n are divisible by d, is ⌊ dn ⌋.
Theorem: Let a, b, and c be integers, where a ̸= 0. Then
(i ) if a|b and a|c, then a|(b + c);
(ii ) if a|b, then a|bc for all integers c;
(iii ) if a|b and b|c, then a|c.
Proof:

Corollary: If a, b, and c are integers, where a ̸= 0, such that a|b and

a|c, then a|(mb + nc) whenever m and n are integers.
Proof:
 Division Algorithm
Theorem: [The Division Algorithm] Let a be an integer and d a
positive integer. Then there are unique integers q and r , with
0 ≤ r < d, such that a = dq + r .
Proof: Let S be the set of nonnegative integers of the form a − dq,
where q is an integer. This set is nonempty because −dq can be
made as large as possible. By the well-ordering property, S has a
least element r = a − dq0 , for some integer q0 . Clearly, r ≥ 0. If
r ≥ d, then a − dq0 − d ≥ 0. Since a − dq0 − d = a − (q0 + 1)d,
a − dq0 − d ∈ S. Also, a − d(q0 + 1) = r − d. Therefore r − d ∈ S,
which is a contradiction as r is the least element in S. Consequently,
0 ≤ r < d.
Let us consider therere exist integers q1 , r1 and q2 , r2 , with 0 ≤ r1 < d
and 0 ≤ r2 < d such that a = dq1 + r1 = dq2 + r2 . Without loss of
generality we can assume that r2 ≥ r1 . As 0 ≤ r2 − r1 < d and
r2 − r1 = d(q1 − q2 ) is a multiple of d, therefore d(q1 − q2 ) = 0.
Hence q1 = q2 as d > 0. Consequently, r1 = r2 . Thus there are
unique integers q and r , with 0 ≤ r < d, such that a = dq + r .
Definition: In the division algorithm, d is called the divisor, a is called
the dividend, q is called the quotient, and r is called the remainder.
Example: What are the quotient and remainder when 107 is divided
by 17?
Solution: 107 = 17 × 6 + 5. Hence the quotient is 6 and the
remainder is 5.
Example: What are the quotient and remainder when −53 is divided
by 7?
Solution: −53 = 7 × (−8) + 3. Hence the quotient is −8 and the
remainder is 3.
 Modular Arithmetic

Definition:
If a and b are integers and n is a positive integer, then a is con-
gruent to b modulo n if they have the same remainder on divi-
sion by n.
We use the notation a ≡ b (mod n) to indicate that a is congruent
to b modulo n. If a and b are not congruent modulo n, we write
a ̸≡ b (mod n).

Example: 7 ≡ 3 (mod 4) but 10 ̸≡ 3 (mod 4).

Theorem: Let a and b be integers, and let n be a positive integer.
Then a ≡ b (mod n) if and only if n | a − b.

Corollary: Let a, b, c be integers and n be a positive integer.

(i ) a ≡ a (mod n);
(ii ) if a ≡ b (mod n), then b ≡ a (mod n);
(iii ) if a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).
Theorem: Let n be a positive integer. The integers a and b are
congruent modulo n if and only if there is an integer k such that
a = b + kn.

Theorem: Let n be a positive integer. If a ≡ b (mod n) and c ≡ d

(mod n), then a + c ≡ b + d (mod n) and ac ≡ bd (mod n).

Corollary: Let n be a positive integer and m be any integer. If a ≡ b

(mod n), then ma ≡ mb (mod n).

Corollary: Let n be a positive integer. If a ≡ b (mod n), then ak ≡ bk

(mod n) for any nonnegative integer k .
 Primes
Definition: An integer p greater than 1 is called prime if the only
positive factors of p are 1 and p. A positive integer that is greater than
1 and is not prime is called composite.
Remark: The integer n is composite if and only if there exists an
integer a such that a|n and 1 < a < n.
Example: 11 is a prime number and 15 is a composite number.
Theorem: Every integer greater than 1 can be written uniquely as a
prime or as the product of two or more primes.
Proof: Let P(n) be the statement n > 1 can be written as a prime or
product of primes. Then the statement is true for n = 2 as 2 is prime.
Let us assume that P(2), P(3), . . . , P(k ) are true. That is, t can be
written as a prime or product of primes for all 2 ≤ t ≤ k . If k + 1 is
prime then P(k + 1) is true. If k + 1 is composite then there exist
positive integers 2 ≤ a, b ≤ k such that k + 1 = ab. By inductive
hypothesis both a and b can be written as a prime or product of
primes. Hence k + 1 can be written as a product of primes. Therefore
every integer n > 1 can be written as a prime or product of primes.
Theorem: If n is√a composite integer, then n has a prime divisor less
than or equal to n.
Proof:

Example: Show that 113 is prime.

Example: Find the prime factorization of 3244.

Theorem: There are infinitely many primes.

Proof: Let us assume that there are only finitely many primes,
p1 , p2 , . . . , pn . Take R = p1 p2 · · · pn + 1. We now that, R is prime or it
can be written as the product of two or more primes. However, none
of the primes pi divides R, for all 1 ≤ i ≤ n. Therefore R is a prime
and clearly R ̸= pi for all 1 ≤ i ≤ n, which is a contradiction as
{p1 , p2 , . . . , pn } is the set of all primes. Consequently, there are
infinitely many primes.
 Conjectures about Primes
Example: The statement “f (n) = n2 − n + 41 is prime for all positive
integers n" is not true as it is not true for n = 41.
Theorem: For every polynomial f (x) with integer coefficients, there is
a positive integer n such that f (n) is composite.
Goldbach’s Conjecture: Every even integer bigger than 2, is the
sum of two primes.
Remark: The conjecture is true for all integers less than 4 × 1018 .
The Twin Prime Conjecture: Twin primes are pairs of primes that
differ by 2, such as 3 and 5, 17 and 19. The twin prime conjecture is
“there are infinitely many twin primes".
Conjecture: There are infinitely many primes of the form n2 + 1,
where n is a positive integer.
Remark: The best known result is that there are infinitely many
positive integers n such that n2 + 1 is prime or product of at most two
primes.
 Greatest Common Divisor and Least Common Multiple
Definition: Let a and b be integers, not both zero. The largest integer
d such that d|a and d|b is called the greatest common divisor of a
and b. The greatest common divisor of a and b is denoted by
gcd(a, b).
Definition: The integers a and b are relatively prime or co-prime if
their greatest common divisor is 1.
Definition: The integers a1 , a2 , ..., an are pairwise relatively prime if
gcd(ai , aj ) = 1, for all i, j ∈ {1, 2, . . . , n}.
Definition: The least common multiple of the positive integers a and
b is the smallest positive integer that is divisible by both a and b. The
least common multiple of a and b is denoted by lcm(a, b).
Example: Greatest common divisor of 15 and 35 is 7. Least common
multiple of 15 and 35 is 105.
Example: 19 and 24 are co-prime integers as gcd(19, 24) = 1.
7, 15, 44 are pairwise co-prime integers.
 gcd and lcm using Prime Factorization
Suppose that the prime factorizations of the positive integers a and b
are
a = p1a1 p2a2 p3a3 · · · pnan and b = p1b1 p2b2 p3b3 · · · pnbn ,
where pi ’s are distinct primes ai ’s are nonnegative integers for all
1 ≤ i ≤ n. Then
max(a1 ,b1 ) max(a2 ,b2 ) max(a3 ,b3 ) max(an ,bn )
lcm(a, b) = p1 p2 p3 · · · pn
and
min(a1 ,b1 ) min(a2 ,b2 ) min(a3 ,b3 ) min(an ,bn )
gcd(a, b) = p1 p2 p3 · · · pn .
Example: Find gcd and lcm of 360 and 500.

Theorem: Let a and b be positive integers. Then

ab = gcd(a, b) × lcm(a, b).
 Euclidean Algorithm
Lemma: Let a = bq + r , where a, b, q, and r are integers. Then
gcd(a, b) = gcd(b, r ).

Note: By the previous lemma, we use successive divisions to reduce

the problem of finding the greatest common divisor of two positive
integers to the same problem with smaller integers, until one of the
integers becomes zero.
Example: Find the greatest common divisor of 35 and 75 using the
Euclidean algorithm.
Solution:
75 = 35 × 2 + 5
∴ gcd(75, 35) = gcd(35, 5).
35 = 5 × 7 + 0
∴ gcd(35, 5) = gcd(5, 0).
Hence gcd(75, 35) = gcd(35, 5) = gcd(5, 0) = 5.
 gcd as Linear Combination
Theorem: If a and b are positive integers, then there exist integers s
and t such that gcd(a, b) = sa + tb.
Example: Express gcd(102, 202) = 2 as a linear combination of 102
and 202.
Solution:
202 = 102 × 1 + 100.
102 = 100 × 1 + 2.
100 = 2 × 50 + 0.
Hence gcd(202, 102) = gcd(102, 100) = gcd(100, 2) = 2.
We have
2 = 102 − 100.
∴ 2 = 102 − (202 − 102) = (2 × 102) + ((−1) × 202),
which is an integer linear combination of 102 and 202.
 The Fundamental Theorem of Arithmetic
Lemma: If a, b, and c are positive integers such that gcd(a, b) = 1
and a | bc, then a | c.

Lemma: If p is a prime and p | a1 a2 · · · an , where each ai is an

integer, then p | ai for some i.

Theorem: [The Fundamental Theorem of Arithmetic] Every integer

greater than 1 can be written uniquely as a prime or as the product of
two or more primes where the prime factors are written in
nondecreasing order.
 Inverse Modulo Positive Integer
Lemma: Let n be a positive integer and let a, b, and c be integers. If
ac ≡ bc (mod n) and gcd(c, n) = 1, then a ≡ b (mod n).
Definition: b is said to be an inverse of a modulo n if ab ≡ 1 (mod n).
Theorem: If a and n are relatively prime integers with n > 1, then an
inverse of a modulo n exists. Furthermore, this inverse is unique
modulo n.
Proof: Since gcd(a, n) = 1, there exist integers s, t such that
sa + tn = 1.
This implies
sa + tn ≡ 1(mod n) ⇒ sa ≡ 1(mod n).

Consequently, s is an inverse of a modulo n.

Suppose that s1 and s2 are inverses of a modulo n. That is, as1 ≡ 1
(mod n) and as2 ≡ 1 (mod n). Therefore as1 ≡ as2 (mod n). Since
gcd(a, n) = 1, we have s1 ≡ s2 (mod n) by previous lemma. Hence
inverse of a is unique modulo n.
 Linear Congruence
Example: Find an inverse of 5 modulo 7.
Solution: we know that gcd(5, 7) = 1.
7=5×1+2

5 = 2 × 2 + 1.
Now
1 = 5 − (2 × 2) = 5 − 2(7 − 5) = (3 × 5) + ((−2) × 7).

From last equation, we see that 3 is an inverse of 5 modulo 7.

Example: What are the solutions of the linear congruence 5x ≡ 2
(mod 7)?
Solution: In previous example, we see that 3 is an inverse of 5
modulo 7. We multiply 3 to the both sides of given congruence.
Hence
5x ≡ 2(mod 7) ⇒ (3 × 5)x ≡ (3 × 2)(mod 7) ⇒ x ≡ 6(mod 7).
 The Chinese Remainder Theorem
Theorem:[The Chinese Remainder Theorem] Let n1 , n2 , . . . , nk be
pairwise relatively prime positive integers greater than 1 and
a1 , a2 , . . . , ak be arbitrary integers. Then the system of k
congruences x ≡ a1 (mod n1 ), x ≡ a2 (mod n2 ),. . ., x ≡ ak (mod nk )
has a unique solution modulo n = n1 n2 · · · nk .
Note: Define N1 = n/n1 , N2 = n/n2 , . . . , Nk = n/nk in the statement
of the Chinese remainder theorem. Take
a = a1 N1 y1 + a2 N2 y2 + · · · + ak Nk yk ,
where yi is an inverse of ai modulo Ni for all 1 ≤ i ≤ k . Then x ≡ a
(mod n) is the solution to the given k congruences.
Example: Solve system of congruences x ≡ 1 (mod 3), x ≡ 2 (mod
4), x ≡ 3 (mod 5).
 Fermat’s Little Theorem
Theorem:[Fermat’s Little Theorem] If p is prime and p ∤ a, where a is
an integer, then
ap−1 ≡ 1(mod p).
Example: Find the remainder when 7242 is divided by 13.

Theorem:[Euler’s Theorem] Let a, n be integers with n > 0. Then

aϕ(n) ≡ 1(mod n),

where ϕ(n) is the number of positive integers less than n and
co-prime to n.
Note: If n is prime, say p in Euler’s theorem, then we have Fermat’s
little theorem. Hence Fermat’s little theorem is a special case of
Euler’s theorem.
 Representations of Integers

In general we use decimal notation to express integers.

For example, 365 is used to denote 3 × 102 + 6 × 10 + 5.
However, it is often convenient to use bases other than 10.
In particular, computers usually use binary representation (base
2), octal representation (base 8) and hexadecimal representation
(base 16).
In fact, we can use any integer greater than 1 as the base when
expressing integers.
Theorem: Let b be an integer greater than 1. Then if n is a positive
integer, it can be expressed uniquely in the form
n = ak bk + ak −1 bk −1 + · · · + a1 b + a0 ,
where k is a nonnegative integer, a0 , a1 , · · · , ak are nonnegative
integers less than b, and ak ̸= 0.
 The representation of n given in the previous theorem is called
the base b expansion of n.
The base b expansion of n is denoted by (ak ak −1 ...a1 a0 )b . For
instance, (245)8 represents 2 × 82 + 4 × 8 + 5 = 165.
Typically, the subscript 10 is omitted for base 10 expansions of
integers because base 10, or decimal expansions, are commonly
used to represent integers.
Binary expansions: Choosing 2 as the base gives binary
expansions of integers. In binary notation each digit is either 0 or 1.
Octal expansions: Base 8 expansions are called octal expansions.
Here digits are 0,1,2,3,4,5,6,7.
Hexadecimal expansions: Base 16 expansions are hexadecimal
expansions. The hexadecimal digits used are 0, 1, 2, 3, 4, 5, 6, 7, 8,
9, A, B, C, D, E, and F, where the letters A through F represent the
digits corresponding to the numbers 10 through 15 (in decimal
notation).
 Binary, Octal, Hexadecimal Expansions to Decimal Expansion
Example: What is the decimal expansion of the integer that has
(1 0101 1001)2 as its binary expansion?

Example: What is the decimal expansion of the number with octal

expansion (2022)8 ?

Example: What is the decimal expansion of the number with

hexadecimal expansion (2AC0D)16 ?
 Decimal Expansion to Binary, Octal, Hexadecimal expansions
Example: Find the octal expansion of (123456)10 .

Example: Find the hexadecimal expansion of (157330)10 .

Example: Find the binary expansion of (1022)10 .