Number Theory Lecture Note

(Math 3092)

By
Biruk Getachew

Arba Minch University

College of natural Sciences
Department of Mathematics

March 11, 2019

Contents

1 Basic Properties of Integers 1

1.1 Algebraic Structure of Integers . . . . . . . . . . . . . . . . . . 1
1.1.1 Some Basic Axioms for Z . . . . . . . . . . . . . . . . 3
1.1.2 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 Rings and Fields . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 Integral Domains . . . . . . . . . . . . . . . . . . . . . 6
1.2 The Well Ordering Axiom(WOA) and
Mathematical Induction . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Well Ordering Axiom . . . . . . . . . . . . . . . . . . . 8
1.2.2 The Principle of Mathematical Induction(PMI) . . . . 11
1.3 Divisibility In The Ring of Integers . . . . . . . . . . . . . . . 14
1.3.1 Basic Properties of Divisibility . . . . . . . . . . . . . . 14
1.3.2 Prime Numbers . . . . . . . . . . . . . . . . . . . . . . 15
1.3.3 The Sieve of Eratosthenes . . . . . . . . . . . . . . . . 16
1.3.4 The Greatest Common Divisor . . . . . . . . . . . . . 20
1.3.5 The Fundamental Theorem of Arithmetic and Unique
Factorization . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.6 The Division Algorithm . . . . . . . . . . . . . . . . . 24
1.3.7 The Euclidean Algorithm . . . . . . . . . . . . . . . . 26
1.3.8 Representation of Integers . . . . . . . . . . . . . . . . 31

2 Diophantine Equations 35
2.1 Linear Diophantine Equations . . . . . . . . . . . . . . . . . . 35
2.2 Solutions to Linear Diophantine Equations . . . . . . . . . . . 37
2.3 The Method of Euler in Linear Equations . . . . . . . . . . . . 44
2.4 Some General Notions of Diophantine
Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3 Theory of Congruence 49
3.1 Introduction to Congruences . . . . . . . . . . . . . . . . . . . 49
3.1.1 Congruence Modulo n . . . . . . . . . . . . . . . . . . 49

i
Number Theory Lecture Note ii

3.2 The Notion of Congruence and Residue Classes . . . . . . . . 50

3.2.1 Congruence and Divisibility . . . . . . . . . . . . . . . 50
3.2.2 Congruence and Equality . . . . . . . . . . . . . . . . . 51
3.2.3 Residue classes . . . . . . . . . . . . . . . . . . . . . . 51
3.3 Operations on Congruence Classes and Basic Properties . . . . 52
3.3.1 Congruence and Arithmetic . . . . . . . . . . . . . . . 52
3.3.2 Arithmetic of Residue Classes . . . . . . . . . . . . . . 54
3.3.3 Integers Modulo m, Zm . . . . . . . . . . . . . . . . . . 54
3.3.4 Cancellation Laws for Congruences . . . . . . . . . . . 55
3.4 Basic Facts From Group Theory In The Notion of Congruence 57
3.5 Solving Congruences . . . . . . . . . . . . . . . . . . . . . . . 59
3.5.1 Linear Congruences . . . . . . . . . . . . . . . . . . . . 59
3.5.2 Chinese Remainder Theorem(CRT) . . . . . . . . . . . 62

4 Euler-Fermat Theorem 67
4.1 The Notion of Complete System of Residues . . . . . . . . . . 67
4.2 Euler-quotient Function, φ(m) . . . . . . . . . . . . . . . . . . 68
4.3 Euler-Fermat Theorem . . . . . . . . . . . . . . . . . . . . . . 72
4.4 Congruences of Higher Order . . . . . . . . . . . . . . . . . . 75
4.4.1 Application of The Euler-Fermat Theorem . . . . . . . 75
4.4.2 Polynomial Congruences . . . . . . . . . . . . . . . . . 76

5 Decimal Expansion of Rational Numbers 83

5.1 Decimal Representation . . . . . . . . . . . . . . . . . . . . . 83
5.2 Types of Decimal Representations . . . . . . . . . . . . . . . . 87
5.3 Characterizing The Rational Using
Decimal Representation . . . . . . . . . . . . . . . . . . . . . 88

6 Other Topics In Number Theory 93

6.1 The Set of Algebraic Numbers . . . . . . . . . . . . . . . . . . 93
6.1.1 Polynomials Over Rings . . . . . . . . . . . . . . . . . 93
6.1.2 Field Extensions And Algebraic Numbers . . . . . . . . 98
6.2 Continued Fractions In Real Numbers . . . . . . . . . . . . . . 103

c 2018 Biruk G. AMU

Chapter 1

Basic Properties of Integers

1.1 Algebraic Structure of Integers

God has made the integers, all the rest is the work of man.
—Leopold Kronecker.
The original quotation in German was Die ganze Zahl schuf der liebe Gott,
alles Übrige ist Menschenwerk. More literally, the translation is “The whole
number, created the dear God, everything else is man’s work.” Note in par-
ticular that Zahl is German for number. This is the reason that today we
use Z for the set of integers(Quotation by Leopold Kronecker)

Number theory is the study of the properties of integers. The great math-
ematician Carl Friedrich Gauss called this subject arithmetic and of it he said:

”Mathematics is the queen of Sciences and arithmetic is the queen of

mathematics” —Carl Friedrich Gauss.

Why we study number theory? few reasons:

♦ In some ways the most basic piece of mathematics, for you can build
everything else from natural numbers.
√
negation division real analysis −1
N −−−−−→ Z −−−−→ Q −−−−−−−→ R −−→ C
from there you can get to calculus, topology, etc · · ·
♦ Number uses techniques from algebra, analysis, geometry, and topol-
ogy, logic, and computer science and often drives developments in these
fields.

1
Number Theory Lecture Note 2

Figure 1.1: Carl Friedreich Gauss

♦ Has some great applications. For example:- RSA Public Key Cryptog-
raphy, Coding theory, etc...

♦ It’s a great place to learn how to read and write proofs.

♦ It’s a rich source of conjecture which are easy to state and very hard
to prove. For instance:- Diophantine Equations: Given some equation,
look for integer solutions.

Example 1.1. The Pythagorean Theorem.

a2 + b 2 = c 2

results in triples (3,4,5), (5,12,13), (7,24,25), (8,15,17), etc ...

This can be generalized to Fermat’s Last Theorem,

an + bn = cn , with integers a,b,c.

Since number theory is concerned with properties of the integers, we begin by

setting up some notation and reviewing some basic properties of the integers
that will be needed later:

N= {1, 2, 3, ...}(the natural numbers or positive integers)

c 2018 Biruk G. AMU

Number Theory Lecture Note 3

Z= {... − 3, −2, −1, 0, 1, 2, 3, ...} (the integers)

Q= { m
n
|m, n ∈ Z} (the rational numbers)
R= the real numbers.

At first blush one might think that of all areas of mathematics certainly
arithmetic should be the simplest, but it is a surprisingly deep subject.

Here are some examples of outstanding unsolved problems in number

theory. A solution to any one of these problems would make you quite famous
(at least among mathematicians). Many of these problems concern prime
numbers. A prime number is an integer greater than 1 whose only positive
factors are 1 and the integer itself.

1) (Goldbach’s Conjecture) Every even integer n ≥ 2 is the sum of two

primes.

2) (Twin Prime Conjecture) There are infinitely many twin primes. [If p
and p + 2 are primes we say that p and p + 2 are twin primes.]

4) Are there infinitely many primes whose digits in base 10 are all ones?
Numbers whose digits are all ones are called repunits.

5) Are there infinitely many perfect numbers? [An integer is perfect if it

is the sum of its proper divisors.]

6) Is there a fast algorithm for factoring large integers? [A truly fast algo-
rithm for factoring would have important implications for cryptography
and data security.]

1.1.1 Some Basic Axioms for Z

1. If a, b ∈ Z, then a + b, a − b, ab ∈ Z
Z is closed under addition, subtraction, and multiplication.

2. If a ∈ Z, then there is no x ∈ Z such that a < x < a + 1.

3. If a, b ∈ Z and ab = 1, then either a = b = 1 or a = b = −1.

4. Laws of Exponents: For n, m in N and a, b in R we have

(a) (an )m = anm

(b) (ab)n = an bn
(c) an am = an+m

c 2018 Biruk G. AMU

Number Theory Lecture Note 4

The rules hold for all n, m ∈ Z if a and b are not zero.

5. Properties of Inequalities: For a, b, c ∈ R the following hold:
(a) Transitivity: If a < b and b < c, then a < c
(b) If a < b and 0 < c then ac < bc
(c) If a < b then a + c < b + c
(d) If a < b and c < 0 then bc < ac
(e) Trichotomy: Given a and b, one and only one of the following
holds: a = b, a < b, b < a.

1.1.2 Groups
A Binary Operation on a set E is a function from E× E to E.
Let 4: E× E → E be a binary operation on E; then
i) 4(x, y) = x 4 y ∈ E (Closed under 4)
ii) 4 assigns exactly one element to each (x, y) ∈ E×E (Well-defined)
Example 1.2. Let N= The set of natural numbers. Then (+) and (.) are
binary operations on N, but (-) and (÷) are not binary operations on N.
Definition 1.1. The ordered pair (G,∗); G6= ∅ and a binary operation ∗ on
G is a group if:
i) Axiom 1: a, b ∈ G → a ∗ b ∈ G (Closure)
ii) Axiom 2: ∀a, b, c ∈ G, (a ∗ b) ∗ c = a ∗ (b ∗ c) (Associativity)
iii) Axiom 3: ∃e ∈ G such that ∀a ∈ G, a ∗ e = a = e ∗ a (Existence of
identity)
iv Axiom 4: ∀a ∈ G, ∃a ∈ G such that a ∗ a = e = a ∗ a (Existence of
inverse)
Definition 1.2. (G,∗) is abelian(or commutative) group if
Axiom 5: ∀a, b ∈ G, a ∗ b = b ∗ a (Commutativity)
Example 1.3. (Z, +) is a group, but (Z, .) is not a group(Axiom 4 fails).
Example 1.4. The group of 2×2 matrices over Z. The set of n × n in-
vertible matrices over R forms a group under matrix multiplication, denoted
by GL(n,R) called the general linear group. Similarly for invertible matrices
over Q or C.

c 2018 Biruk G. AMU

Number Theory Lecture Note 5

Example 1.5. The group of Integers Modulo n.

Let Z = The set of integers and n be a fixed positive integer. We define a
relation ≡ on Z as follows:

∀a, b ∈ Z, a ≡ b (mod n) if a − b is a multiple of n.

The relation ≡ is an equivalence relation on Z(show!)

Notation: For m ∈ Z, let [m] denote the equivalence class of m.

Let Zn = [1], [2], [3], ..., [n − 1], then every element of Z belongs to exactly
one of the equivalence classes in Zn . Zn is a group.(proof: exercise)

1.1.3 Rings and Fields

R 6= ∅ with two binary operations (R, +, .) is said to be a ring if:

i) (R, +) is an abelian group.

ii) Multiplicative binary operation is associative on R.
iii) The multiplicative binary operation is both left and right distributive
over the additive binary operation (+).
Example 1.6. Let (+) and (.) be the usual addition and multiplication.
Then (Z,+,.), (Q,+,.), (R,+,.) are rings.
Definition 1.3. Let (R,+,.) be a ring. We say:
i) (R,+,.) is a commutative ring if a.b=b.a for all a,b∈ R.
ii) If ∃u ∈ R such that a.u=a=u.a for all a∈ R, then it is easy to show
that u is unique. u is called a unity element of R and often denoted
by 1 and (R,+,.) is called a ring with unity.
iii) (R,+,.) is called division ring if it is a ring with unity and for each
non-zero a∈ R, ∃ an element b∈R such that a.b=b.a=1.
iv) (R,+,.) is called a field if it is a commutative division ring. (a ring is
called a field if the non-zero elements of R form an abelian group under
(.) multiplication)
Example 1.7. i) (Z,+,.) is a commutative ring with unity. The ba-
sic commutative rings in mathematics are the integers Z, the rational
numbers Q, the real numbers R, and the complex numbers C.

c 2018 Biruk G. AMU

Number Theory Lecture Note 6

ii) (Q,+,.) and (R,+,.) are fields.

1.1.4 Integral Domains

One of the most important algebraic properties of our usual number system
is the fact that if the product of two numbers is zero, then at least one of the
two numbers is zero. This ia the basis for solving quadratic equations. For
example, to solve the equation x2 − 5x + 6 = 0 in the real number system, we
need only observe that x2 − 5x + 6 = (x − 2)(x − 3). Then, by the property
of the real number system, it follows that either x − 2 = 0 or x − 3 = 0, and
hence x = 2 or x = 3.

On the other hand, in Z12 , (2)(6)=0, although 2 6= 0 and 6 6= 0, showing

that Z12 does not possess the property of the real number system.
Definition 1.4. Let R be a ring. Let a,b ∈ R\{0}. If ab=0, then a and b
are called zero-divisors(or divisors of zero). In particular, a is called a left
divisor of zero and b is a right divisors of zero.
In commutative ring, there is no distinction between left and right divisors
of zero.
Example 1.8. The rings Z, Q and R do not contain zero divisors. 2,3,4,6,8,9,
and 10 are zero divisors in Z12 .
Definition 1.5. An integral domain is a commutative ring with unity
containing no divisors of zero.
Remark 1.1. A commutative ring R is an integral domain if the product of
any two non-zero elements of R is non-zero. But for convenience in stating
various results, we will always assume that an integral domain always contain
a unity. That is an integral domain is a commutative ring with unity having
no zero divisor.
Example 1.9. i) The rings Z, Q, R are integral domains. The ring Z12
is not an integral domain, although it is a commutative ring with unity.
ii) The ring Zn is not an integral domain, if n is not a prime number.
To see this, let m ∈ Zn where m 6= 0 and gcd(m, n) 6= 1. Let d=gcd(m, n).

Then m( nd ) = 0 in Zn , since m( nd ) = ( md )n, a multiple n, while neither

m nor nd is 0.

Hence, m is a divisor of zero in Zn .

c 2018 Biruk G. AMU

 Number Theory Lecture Note 7

iii) Every field is an integral domain. To see this, let F be a field. Suppose
ab=0 for a,b∈F, a6=0.

Then, b=1b=( a1 .a)b= a1 (ab)=( a1 )0=0.

Thus, there are no zero divisors of zero in F.

Consider the system of integers, which is a non-empty se Z, two binary op-

erations(i.e addition ’+’ and multiplication ’.’):

Axiom 1: (Z,+) is Abelian group.

Axiom 2: (Z,+,.) is an integral domain. That is it is a commutative ring with
unity having no zero divisor.
Definition 1.6. 0 denote the addition identity while 1 denotes the mul-
tiplicative identity of Z.

Axiom 3: (Order Axiom) Z has a non-empty subset, denoted by P, such that

3.1) P is closed under ’+’ and ’.’
3.2) For each x ∈ Z, exactly one of the three conditions x ∈ P or
−x ∈ P or x = 0 holds.
Definition 1.7. A ring R satisfying the above three axioms is called an
ordered integral domain.
The subset P of R whose existence is guaranteed by the order axiom is called
the set of positive elements of R.

If R is an ordered integral domain with P as the set of positive elements

of R, we can introduce order on R as follows:

For x, y ∈ R we say that x > y if and only if x + −y ∈ P .

Example 1.10. Consider the set of rational numbers Q under addition and
multiplication. Q under ’+’ and ’.’ is an integral domain. And the positive
elements are P=Q+ ={x ∈ Q | x > 0}.
Example 1.11. Consider the set of rational numbers R under addition and
multiplication. Q under ’+’ and ’.’ is an integral domain. And the positive
elements are P=R+ ={x ∈ R | x > 0}.

c 2018 Biruk G. AMU

Number Theory Lecture Note 8

√
Example 1.12. Let Z[√2] = {a + b 2 | a, b ∈ Z}. Then Z[√2] is an integral
domain under the operations:
√ √ √
(a + b 2) + (c + d 2) = (a + c) + (b + d) 2
and √ √ √
(a + b 2)(c + d 2) = (ac + 2bd) + (ad + bc) 2
√ √
Consider P1 = {a + b 2 | a, b ∈ Z and a + b 2 is a positive real number }
as a set of positive elements of Z[√2] .

It is clear that Z[√2] is an ordered integral domain with P1 the set of

positive elements.

Notation: From this point forward let P denote a subset of Z satisfying the
conditions in the order axiom. That is P is the set of positive elements of Z
whose existence guaranteed by Axiom 3.

1.2 The Well Ordering Axiom(WOA) and

Mathematical Induction
1.2.1 Well Ordering Axiom
Axiom 4: (Well Ordering Axiom) Every non-empty subset of P(positive ele-
ments of a ring R) has a least element.

Example 1.13. Show that for any x ∈ Z \ {0}, x2 ∈ P (i.e x2 is a positive

element).

For x ∈ Z \ {0}, by Axiom 3 either x ∈ P or −x ∈ P . (Notice x 6= 0)

If x ∈ P , then x.x = x2 ∈ P . Since by Axiom 3 P is closed under multipli-
cation.

Else −x ∈ P , then −x. − x = (−x)2 ∈ P . Since by Axiom 3 P is closed

under multiplication.

Thus we get x2 = (−x)2 ∈ P . Therefore, in either case we showed that

2
x ∈ P.

Example 1.14. Show that 1 is the least element of P.

c 2018 Biruk G. AMU

Number Theory Lecture Note 9

Solution: Since 1 ∈ Z by example 1 above we see that 1 = 12 ∈ P . Hence

1 ∈ P.

On the other hand since P ⊆ P by WOA P has a least element,say e.

We want to show e = 1.

Suppose e 6= 1. Then since e is the least element of P, e is less than every

element of P.

Thus e < 1 which implies that 1 + −e ∈ P . And we know that e ∈ P .

Hence it follows that e(1 + −e) ∈ P since by Axiom 3 P is closed under

multiplication.

=⇒ e − e2 ∈ P
=⇒ e2 < e

And e2 ∈ P , since e ∈ P and example 1 above. This contradicts that e is

the least element of P.
Example 1.15. Show that there is no integer between a and a+1.

Solution: Suppose there is an integer b between a and a+1.

Then since (a + 1) + −b ∈ P .

(a + 1) + −b = (a + 1 + −a) + (−b + a) ∈ P

=⇒ (a + 1 + −a) + (−b + a) > 0.

=⇒ b + −a < (a + 1) + −a = 1
=⇒ b + −a < 1.

but b + −a is also a positive integer.

=⇒ 1 is not the least element of P. This contradicts to example 2.

Therefore, there is no integer between a and a + 1 for any integer a.

Theorem 1.1. P = {1, 2, 3, . . . }

c 2018 Biruk G. AMU

Number Theory Lecture Note 10

Proof: Since 1 ∈ P and P is closed under addition it follows that

1 + 1 = 2 ∈ P.

Then by induction it follows that

{1, 1 + 1, 1 + 1 + 1, . . . } = {1, 2, 3, . . . } ⊆ P ...(∗)

Next we show that P ⊆ {1, 2, 3, . . . }

Assume that P is not a subset of {1, 2, 3, . . . }. Then there exists x ∈ P

which does not belong to the set {1, 2, 3, . . . }. That is to say the set

S = {x ∈ P | x ∈
/ {1, 2, 3, . . . }} is non-empty subset of P .

Then by WOA it follows that S has a least element, say x0 .

Since 1 ∈ {1, 2, 3, . . . }, 1 ∈
/S

So the least element x0 > 1 and x0 − 1 ∈ {1, 2, 3, . . . }

But, then (x0 − 1) + 1 ∈ {1, 2, 3, . . . }

=⇒ x0 ∈ {1, 2, 3, . . . } as x0 = (x0 − 1) + 1
=⇒ x0 ∈
/S

This contradicts to the fact that x0 is the least element of S. Notice that
a least element of S is an element of S which is the least of all. Hence our
assumption is wrong.

Therefore, we conclude that P ⊆ {1, 2, 3, . . . } ...(∗∗)

Hence from (∗) and (∗∗) we have our result P = {1, 2, 3, . . . }

Corollary 1.1. Z = {· · · − 3, −2, −1, 0, 1, 2, 3, . . . }.

Proof: Clearly {· · · − 3, −2, −1, 0, 1, 2, 3, . . . } ⊆ Z ...(∗)

Suppose x ∈ Z. Then either x ∈ P , or −x ∈ P , or x = 0.

c 2018 Biruk G. AMU

Number Theory Lecture Note 11

Then by Theorem 1, x ∈ {1, 2, 3, . . . } or −x ∈ {1, 2, 3, . . . }, or x = 0.

i.e x ∈ {1, 2, 3, . . . } or x ∈ {· · · − 3, −2, −1} or x = 0.

which implies that x ∈ {· · · − 3, −2, −1, 0, 1, 2, 3, . . . } ...(∗∗)

Hence by (∗) and (∗∗) we have our result

Z = {· · · − 3, −2, −1, 0, 1, 2, 3, . . . }.

1.2.2 The Principle of Mathematical Induction(PMI)

We now present a valuable tool for proving results about integers. This tool
is the principle of mathematical induction. The Principle of Mathematical
Induction(PMI) is one of the most powerful techniques of proving assertions
or solving problems that involve integers.

Theorem 1.2. First Principle of Finite Induction....(i)

If S is a subset of P(P−→the set of positive integers) such that

i) 1∈S

ii) k∈S =⇒ k+1∈S,

then S=P(S is the set of all positive integers)

Proof: Let T be the set of all positive integers not in S, and assume that T
is non-empty.

The WOA tells us that T possesses a least element, which we denote by

a. Because 1 is in S, certainly a > 1, and so 0 < a − 1 < a.

The choice of a as the smallest positive integer in T implies that a-1 is

not a member of T, or equivalently that a-1 belongs to S. By hypothesis, S
must also contain (a-1)+1=a, which contradicts the fact that a lies in T.

We conclude that the set T is empty and in consequence that S contains

all the positive integers.

The Principle of Mathematical Induction ...(ii)

If S(n) is an open statement on the set of positive integers such that

c 2018 Biruk G. AMU

Number Theory Lecture Note 12

i) S(1) is true.

ii) S(k)=⇒S(k+1)

then S(n) is true for every positive integer(for every natural number).

Example 1.16. Use mathematical induction to show that ∀n ∈ N

n
X n(n + 1)
i=
i=1
2
First note that
1
X 1.2
i=
i=1
2
and thus the the statement is true for n = 1. ForPnthe remaining inductive
n(n+1)
step, suppose that the formula holds for n, that i=1 i = 2 . We show
that
n+1
X (n + 1)(n + 2)
i=
i=1
2
to complete the proof by induction. Indeed
n+1 n
X X n(n + 1) (n + 1)(n + 2)
= +(n + 1) = = .
i=1 i=1
2 2

Example 1.17. Use mathematical induction to prove that n! ≤ nn for all

positive integers n.

Note that 1! = 1 ≤ 11 = 1. We now present the inductive step. Suppose

that

k! ≤ k k

for some k, we prove that (k + 1)! ≤ (k + 1)k+1 . Note that

(k + 1)! = (k + 1)k! ≤ (k + 1).k k < (k + 1)(k + 1)k = (k + 1)k+1 .

This completes the proof.

Example 1.18. Prove using induction the proposition:

c 2018 Biruk G. AMU

Number Theory Lecture Note 13

Proposition: If n≥5, then 2n > 5n.

Proof: We let P(n): 2n > 5n. We could write simply:

P(n): 2n > 5n and n0 = 5.

Part (i): If n=5, P(n) is true.

Part (ii): Assume P(k) is true for k≥5.

That is we assume 2k > 5k for k ≥ 5 . . . (∗)

The assumption (∗) is called the induction hypothesis. We want to use it

to prove that P(k+1) holds true.

By (∗) we have 2k > 5k. Multiplying both sides by two we get

2k+1 > 10k . . . (∗∗)

Note that we are trying to prove 2k+1 > 5(k + 1) = P (k + 1).

Now S(k+1)=5k+5, so if we can show 10k≥5k+5, we can use (∗∗) to

complete the proof.

Now 10k=5k+5k and since kgeq5 by (∗) we see that kgeq1 and hence
5k≥5.

Therefore, 10k=5k+5k ≥ 5k+5=5(k+1).

Thus 2k+1 > 5(k + 1) . . . (∗ ∗ ∗)

That is, P(k+1) is true.

So by the PMI we conclude that P(n) holds true for all n≥5.

That is, 2n > 5n holds for n≥5.

c 2018 Biruk G. AMU

Number Theory Lecture Note 14

1.3 Divisibility In The Ring of Integers

This section introduces basic concepts of elementary number theory such
as divisibility, greatest common divisor, and prime and composite numbers.
We also define prime factorization and the Euclidean Algorithm with its
application to greatest common factor.

1.3.1 Basic Properties of Divisibility

Let us discuss divisibility on arbitrary commutative ring R, latter we will
concentrate on ring of integers Z. When dividing an integer by a second
non-zero integer, the quotient may or may not be an integer. For example
12 divided by 3 is 4, but 9 divided by 4 is 2.25, which is not an integer.
Definition 1.8. Suppose m and n are any two elements of R. We say that
n is a divisor (factor) of m in R if and only if for some q∈R m=nq. If n
divides m, then m is called a multiple of n while q is called a quotient of
m by n and we write n | m. Else if n does not divide m, then we write n . m.
Example 1.19. Let 3Z = {· · · − 9, −6, −3, 0, 3, 6, 9, . . . } . Then (3Z,+,.) is
a ring.

In this space 3|9 since 9 = 3×3 and 3|-27 since -27 = 3×-9.

But 3 . 6 since for every q∈3Z 66=3q, also

3 . 15 since for every q∈3Z 156=3q.

Definition 1.9. Suppose that R is a commutative ring with unity. An ele-
ment u∈R is called a unit if there exists v∈R such that uv = 1.
Notation: The set of units of R is denoted by R∗ .

Exercise: Prove that R∗ is a group under multiplication.

Theorem 1.3. Let R be a commutative ring with unity. Then the following
properties holds true.
a) x|x for any x∈R. If a|b and a|c, then a|(b+C).

b) If u is a unit of R, then for any x∈R, u|x.

c) If x|y and y|z, then x|z for any x,y,z∈R.

c 2018 Biruk G. AMU

Number Theory Lecture Note 15

d) If for x,y,z∈R z|x and z|y then z|(rx + ty) ∀r,t∈R.

e) If R is an integral domain, x,y∈R\{0} such that x|y and y|x,

then x=yu for some unit u∈R.

Definition 1.10. If x, y ∈ R\{0} such that x | y and y | x, then x and y are

called associates in R.

Remark: x and y in an integral domain R are said to be associates if and

only if

x = yu for some unit u ∈ R.

In general for any x ∈ R it is easier to find the multiples of x rather than

its factors in R. Indeed the set of multiples of x in R is {nx | n ∈ R}.

1.3.2 Prime Numbers

Concerning the factors, it is clear that x and any unit u ∈ R are factors
of x. Such factors are called trivial factors of x and factors other than
these trivial factors are called non-trivial factors. Factorization is one of the
challenging tasks in Mathematics. The question of finding all the non-trivial
factors is quite difficult to answer even in Z.

In the ring of integers, since x|y if and only if ±x | ±y, when discussing
the notion of factor, multiple, prime number, it suffices to work with positive
integers. This convention shall be used with no further specification.

Definition 1.11. An element p∈ Z is called a prime if and only if it has

exactly four (two positive) divisors in Z. An integer in Z is said to be com-
posite number if and only if it is not prime and not equal to ±1 and 0.

In particular, a positive integer P > 1 is called prime if and only if the

only positive factors of P are 1 and P. A positive integer that is greater than
one and is not prime is called composite.

An integer n is composite if and only if there exists an integer a such that

a|n and 1 < a < n.

c 2018 Biruk G. AMU

Number Theory Lecture Note 16

Example 1.20. The prime natural numbers less than 100 are: 2, 3, 5, 7,
11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
and 97

Composite numbers are: 4, 6, 8, 9, 10, 12, 14, 15, etc . . .

Prime numbers, the building blocks of integers, have been studied ex-
tensively over the centuries. Being able to present an integer uniquely as
product of primes is the main reason behind the whole theory of numbers
and behind the interesting results in this theory. Many interesting theorems,
applications and conjectures have been formulated based on the properties
of prime numbers.

In this section, we present methods to determine whether a number is

prime or composite using an ancient Greek method invented by Eratos-
thenes. We also show that there are infinitely many prime numbers. We
then proceed to show that every integer can be written uniquely as a product
of primes.

1.3.3 The Sieve of Eratosthenes

Figure 1.2: Eratosthenes

We now present the sieve of Eratosthenes. The Sieve of Eratosthenes is

an ancient method of finding prime numbers up to a specified integer. This
method was invented by the ancient Greek mathematician Eratosthenes.
There are several other methods used to determine whether a number is
prime or composite. We first present a lemma that will be needed in the
proof of several theorems.

c 2018 Biruk G. AMU

Number Theory Lecture Note 17

Lemma 1.1. Every integer greater than one has a prime divisor.

Proof: We present the proof of this Lemma by contradiction. Suppose

that there is an integer greater than one that has no prime divisors. Since
the set of integers with elements greater than one with no prime divisors is
nonempty, then by the well ordering axiom there is a least positive integer n
greater than one that has no prime divisors.

Thus n is composite since n divides n. Hence

n = ab with 1 < a < n and 1 < b < n.

Notice that a < n and as a result since n is minimal, a must have a prime
divisor which will also be a divisor of n.

Theorem√1.4. If n is a composite integer, then n has a prime factor not

exceeding n.

Proof: Since n is composite, then n√= ab, where a and b are integers with
1 < a ≤ b < n. Suppose now that a > n, then
√
n < a ≤ b and as a result
√ √
n = ab > n n = n.
√
Therefore a ≤ n. Also, by Lemma 1.3.1, a must have a prime divisor
a1 which
√ is also a prime divisor of n and thus this divisor is less than a1 <
a ≤ n.

The Algorithm of the Sieve of Eratosthenes

1. Write a list of numbers from 2 to the largest number n you want to

test. Note that every
√ composite integer less than n must have a prime
factor less than n. Hence√ you need to strike off the multiples of the
primes that are less than n.

2. Strike off all multiples of 2 greater than 2 from the list. The first
remaining number in the list is a prime number.

3. Strike off all multiples of this number from the list.

c 2018 Biruk G. AMU

Number Theory Lecture Note 18

4. Repeat the above steps until

√ no more multiples are found of the prime
integers that are less than n.

Primes have fascinated people ever since ancient times. Their sequence seems
very irregular, yet on closer inspection it seems to carry a lot of hidden struc-
ture. The ancient Greeks already knew that there are infinitely many such
numbers. (Not only did they know this; they proved it!)

The first 500 primes:-

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557,
563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647,
653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757,
761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063,
1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259,
1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361,
1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549,
1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621,
1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847,
1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,
1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039,
2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137,
2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251,
2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347,
2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671,
2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843,
2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957,
2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067,

c 2018 Biruk G. AMU

Number Theory Lecture Note 19

3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191,
3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307,
3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517,
3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571

In the following discussions we will see that finding factors of a given

integer is highly related with prime factorization in Z. Thus one is interested
to know whether

i) the number of primes in Z is finite or infinite.

ii) if pn denotes the nth positive prime, is there an explicit formula for pn ?

How large is dn = pn+1 − pn ?

iii) given any natural number k, are there primes pn+1 and pn such that
dn = pn+1 − pn = 2k If so, how many such primes are there?

As to the first question raised above it has been known since the time of
Euclid that there are infinite primes. But there is no explicit formula for pn .

Definition 1.12. Two primes are called twin primes if and only if their
difference is equal to 2.

It follows that 3 and 5, 5 and 7, 11 and 13 are twin primes. Thus twin
primes are such pn+1 − pn = 2k with k = 1. The question whether there are
infinity of twin primes is one of the oldest questions in mathematics. Though
there is some information about the distribution of twin primes, the question
is still unanswered.

Theorem 1.5. There are infinitely many primes.

Proof: We present the proof by contradiction. Suppose there are finitely

many primes p1 , p2 , . . . , pn , where n is a positive integer. Consider the inte-
ger Q such that

Q = p1 p2 . . . pn + 1.

By Lemma 1.3.1, Q has at least a prime divisor, say q. If we prove that

q is not one of the primes listed then we obtain a contradiction.

c 2018 Biruk G. AMU

Number Theory Lecture Note 20

Suppose now that q = pi for 1 ≤ i ≤ n. Thus q divides Q = p1 p2 . . . pn + 1

and as a result q divides Q − p1 p2 . . . pn . Therefore q divides 1. But this is
impossible since there is no prime that divides 1 and as a result q is not one
of the primes listed.

1.3.4 The Greatest Common Divisor

In this section we define the greatest common divisor (gcd) of two integers
and discuss its properties. We also prove that the greatest common divisor
of two integers is a linear combination of these integers.

Two integers a and b, not both 0, can have only finitely many divisors,
and thus can have only finitely many common divisors. In this section, we are
interested in the greatest common divisor of a and b. Note that the divisors
of a and that of | a | are the same.
Definition 1.13. The greatest common divisor of two integers a and b is the
greatest integer that divides both a and b. We denote the greatest common
divisor of two integers a and b by gcd(a, b). We also define gcd(0, 0) = 0.
Example 1.21. Note that the greatest common divisor of 24 and 18 is 6. In
other words gcd(24,18) = 6.
There are couples of integers (e.g. 3 and 4, etc. . . ) whose greatest common
divisor is 1 so we call such integers relatively prime integers.
Definition 1.14. Two integers a and b are relatively prime if
gcd(a,b) = 1.
Example 1.22. The greatest common divisor of 9 and 16 is 1, thus they are
relatively prime.
Theorem 1.6. If gcd(a,b) = d then gcd(a/d,b/d) = 1.

Proof: We will show that a/d and b/d have no common positive divisors
other than 1. Assume that k is a positive common divisor such that k | a/d
and k | b/d. As a result, there are two positive integers m and n such that

a/d = km and b/d = kn

Thus we get that
a = kmd and b = knd.

c 2018 Biruk G. AMU

Number Theory Lecture Note 21

Hence kd is a common divisor of both a and b. Also, kd ≥ d. However, d is

the greatest common divisor of a and b. As a result, we get that k = 1.
Definition 1.15. Let a1 , a2 , ..., an be integers,not all 0. The greatest com-
mon divisor of these integers is the largest integer that divides all of the
integers in the set. The greatest common divisor of a1 , a2 , ..., an is denoted
by gcd(a1 , a2 , ..., an ).
Theorem 1.7. If a1 , a2 , ..., an are integers, not all 0, then
gcd(a1 , a2 , ..., an ) = gcd(a1 , a2 , ..., gcd(an−1 , an )).
Proof: ex.
Example 1.23. Find the gcd of 256,342,578,1000 and 3472.

Solution: By prime factorization;

256 = 28
= 342 = 2.32 .19
= 578 = 2.172
= 1000 = 23 .53
= 3472 = 24 .7.31

gcd(256, 342, 578, 1000, 3472) = gcd(256, 342, 578, gcd(1000, 3472))
= gcd(256, 342, 578, 8)
= gcd(256, 342, gcd(578, 8))
= gcd(256, 342, 2)
= gcd(256, gcd(342, 2))
= gcd(256, 2)
= 2.
Definition 1.16. The integers a1 , a2 , ..., an are said to be mutually rela-
tively prime if gcd(a1 , a2 , ..., an ) = 1.
Example 1.24. The integers 3,6,7 are mutually relatively prime since gcd(3, 6, 7) =
1 although gcd(3, 6) = 3.
Definition 1.17. The integers a1 , a2 , ..., an are called pairwise prime if
for each i 6= j, we have gcd(ai , aj ) = 1.
Example 1.25. The integers 3,14,25 are pairwise relatively prime. Notice
also that these integers are mutually relatively prime.

Notice that if a1 , a2 , ..., an are pairwise relatively prime then they are mu-
tually relatively prime.

c 2018 Biruk G. AMU

Number Theory Lecture Note 22

1.3.5 The Fundamental Theorem of Arithmetic and

Unique Factorization
The Fundamental Theorem of Arithmetic is one of the most important re-
sults in this section. It simply says that every positive integer can be written
uniquely as a product of primes. The unique factorization is needed to estab-
lish much of what comes later. There are systems where unique factorization
fails to hold. Many of these examples come from algebraic number theory.
We can actually list an easy example where unique factorization fails.

Consider the class C of positive even integers. Note that C is closed un-
der multiplication, which means that the product of any two elements in C
is again in C. Suppose now that the only number we know are the members
of C. Then we have 12 = 2.6 is composite where as 14 is prime since it is
not the product of two numbers in C. Now notice that 60 = 2.30 = 6.10 and
thus the factorization is not unique.

We now give examples of the unique factorization of integers.

Example 1.26. 99 = 3·3·11 = 32 .11, 32 = 2·2·2·2·2 = 25

Proposition 1.1. Prime Factorization

Let a and b be positive integers and let p1 , p2 . . . , pn be all the primes that
appear in the prime factorization of a or b, so that

a = pa11 .pa22 . . . pann , b = pb11 .pb22 . . . pbnn ,

where each ai , bi ≥ 0 for 1 ≤ i ≤ n. Then

min(a1 ,b1 ) min(a2 ,b2 ) min(an ,bn )

gcd(a, b) = p1 .p2 . . . pn .
1 1 2 2min(a ,b ) min(a ,b )
n n min(a ,b )
Proof: First note that the integer d = p1 p2 . . . pn di-
vides a and b, since the power of each prime pi does not exceed the power of
pi appearing in the factorization of each of these numbers.

Second, the exponents of pi in d can not be increased, otherwise it would

not divide one of a or b, and no other prime can be included.

Example 1.27. 120=23 .3.5 500 = 22 .53 .

so gcd(120, 50) = 2min(3,2) .3min(1,0) .5min(1,3) = 22 .30 .51 = 20.

c 2018 Biruk G. AMU

Number Theory Lecture Note 23

Example 1.28. Find gcd(1029,1911,9177) i.e. find the greatest common

divisor of 1029,1911 and 9177.
Solution:

1029 = 3 × 5 × 73
1911 = 3 × 72 × 13
9177 = 3 × 7 × 19 × 23

Hence gcd(1029, 1911, 9177) = 3 × 7 = 21.

Exercise: Find the greatest common divisor: gcd(70,98,108)=?.

We can use prime factorization to find the smallest common multiple of

two positive integers.

Definition 1.18. The least common multiple of the positive integers a

and b is the smallest positive integer that is divisible by both a and b, denoted
by lcm(a,b).

Example 1.29. lcm(2,10)=10, lcm(5,7)=35, lcm(4,6)=12

Proposition 1.2. Let a and b be positive integers and let p1 , p2 . . . , pn be all

the primes that appear in the prime factorization of a or b, so that

a = pa11 .pa22 . . . pann , b = pb11 .pb22 . . . pbnn ,

where each ai , bi ≥ 0 for 1 ≤ i ≤ n. Then

max(a1 ,b1 ) max(a2 ,b2 ) max(an ,bn )

lcm(a, b) = p1 .p2 . . . pn .

Proof: Similar to the previous proposition.

Exercise:

1. Find the least common multiple of 14 and 15.

2. Find the least common multiple of 240 and 610.

Theorem 1.8. let a and b be positive integers. Then,

c 2018 Biruk G. AMU

Number Theory Lecture Note 24

ab=gcd(a,b)lcm(a,b)

Proof: Write a and b as in the previous propositions.

a = pa11 .pa22 . . . pann , b = pb11 .pb22 . . . pbnn ,

By these Propositions, we have

min(a1 ,b1 ) min(a2 ,b2 ) max(a1 ,b1 ) max(a2 ,b2 )

gcd(a, b)lcm(a, b) = (p1 .p2 . . . pmin(a
n
n ,bn )
)(p1 .p2 . . . pmax(a
n
n ,bn )
)
max(a1 ,b1 )+min(a1 ,b1 ) max(a2 ,b2 )+min(a2 ,b2 )
= p1 .p2 . . . pmax(a
n
n ,bn )+min(an ,bn )

Now note that max(ai , bi )+min(ai , bi )=ai + bi . Thus,

gcd(a, b)lcm(a, b) = pa11 +b1 .pa22 +b2 . . . pann +bn

= pa11 .pa22 . . . pann .pb11 .pb22 . . . pbnn
= ab.

1.3.6 The Division Algorithm

Theorem 1.9. Suppose a and b are integers, b 6= 0 . Then there exist unique,
q, r ∈ Z
such that

a = bq + r with 0 ≤ r < b.

Proof:

Consider the set S = {· · · a − 2b, a − b, a, a + b, a + 2b . . . }

= {a − nb | n ∈ Z}

Let S + be the set of non-negative elements of S. Clearly S + is non-empty

and hence has a least element, call it r. It then follows that a = bq + r for
some q ∈ Z. We show that 0 ≤ r < b Since 0 ≤ r, by choice, it suffices to
show that r < b.

proof by contradiction: Assume that r ≥ b.

c 2018 Biruk G. AMU

Number Theory Lecture Note 25

since r ≥ b =⇒ r − b ≥ 0, consequently r − b ∈ S + and

r − b = (a − bq) − b, since a = bq + r, r = a − bq
= a − qb − b
= a − (q + 1)b

And since b > 0 ⇔ −b < 0, adding r on both sides we have r − b < r.

r − b is then an element of S + which is less than r.

But this is a contradiction to the fact above that r is the least element of
S +.

Corollary 1.2. If a and b are integers, with b 6= 0, then there exist unique
integers q and r such that

a = bq + r with 0 ≤ r <| b |

Example 1.30. Let us take b= -7. Then for the choices of a=1,-2,61 and
-59, we obtain the expressions

1 = 0(−7) + 1
−2 = 1(−7) + 5
61 = (−8)(−7) + 5
−59 = 9(−7) + 4

Example 1.31. With b=2, the remainders are r=0 and r=1.

when r=0, a=2q and is called even.

when r=1, a=2q+1 and is called odd.

Now b2 = (2q)2 = 4k or b2 = (2q + 1)2 = 4(q 2 + q) + 1 = 4k + 1.

Therefore, the square of an integer leaves the remainder 0 or 1 up on

division by 4.

c 2018 Biruk G. AMU

Number Theory Lecture Note 26

1.3.7 The Euclidean Algorithm

In this section we describe a systematic method that determines the greatest
common divisor of two integers. This method is called the Euclidean algo-
rithm. This method was invented by Euclid, a famous mathematician living
during 325-265 B.C.

Figure 1.3: Euclid

The method used to calculate gcd(a,b) via the prime factorization of a

and b is not sufficient. For instance, we do not know how to efficiently fac-
tor a number; that is, there is no polynomial time algorithm known that
does this job. Since that method requires factoring a and b, we would need
to use algorithms that do not run in polynomial time(exponential or sub-
exponential time).

Example 1.32. Find gcd(91,287)=?

Solution: Applying the division algorithm to 287 and 91, we get

287 = 91.3 + 14

Any common divisor d of 287 and 91 must also be a divisor of 14, because
d| 287 and d| 91 implies d| (287 − 91.3) = 14

Also, any common divisor of 91 and 14 must also be a divisor of 287. So,
gcd(287,91)=gcd(91,14).

Continue the process by dividing 91 by 14:

c 2018 Biruk G. AMU

Number Theory Lecture Note 27

91=14.6+7

Again, we conclude that gcd(91,14)=gcd(14,7), and divide by 7:

14=7.2+0

Because 7 divides 14 we know gcd(14,7)=7. Therefore, gcd(287,91)=gcd(91,14)=gcd(14,7)=7.

The Euclidean algorithm is based on the following lemma.

Lemma 1.2. Let a = bq + r where a,b,q and r are integers.

then gcd(a,b) = gcd(b,r).

Proof: Suppose d | a and d | b. Then d | a − bq = r. So any common divisor

of a and b is also a common divisor of b and r. Suppose d | b and d | r. Then
d | bq + r = a. So, any common divisor of b and r is a common divisor of a
and b.

Therefore, gcd(a,b)=gcd(b,r).

The Euclidean Algorithm may be described as follows:

Let a and b be two integers whose GCD is desired.

Because gcd(| a |, | b |) = gcd(a, b), there is no harm in assuming that

a ≥ b > 0.

The first step is to apply the Division Algorithm to a and b to get

a = q1 b + r1 0 ≤ r1 < b (1.1)

If it happens that r1 = 0, then b | a and gcd(a, b) = b. When r1 6= 0, divide

b by r1 to produce integers q2 and r2 satisfying

b=q2 r1 + r2 0 ≤ r2 < r1

If r2 = 0, then we stop; otherwise, proceed as before to obtain

r1 = q3 r2 + r3 0 ≤ r3 < r2

c 2018 Biruk G. AMU

Number Theory Lecture Note 28

This division process continues until some zero remainder appears, say, at the
(n + 1)th stage where rn−1 is divided by rn (a zero remainder occurs sooner or
later because the decreasing sequence b > r1 > r2 > · · · ≥ 0 can not contain
more than b integers).

The result is the following system of equations:


a = q1 b + r1 0 < r1 < b 


b = q2 r1 + r2 0 < r2 < r1





r1 = q3 r2 + r3 0 < r2 < r1 

.. (1.2)
. 



rn−2 = qn rn−1 + rn 0 < rn < rn−1 




rn−1 = qn+1 rn + 0.


We argue that rn , the last nonzero remainder that appears in this manner,
is equal to gcd(a, b)(i.e rn = gcd(a, b))
Example 1.33. Applying Euclidean Algorithm to find gcd(123, 277):

277 = 123.2 + 31
123 = 31.3 + 30
31 = 30.1 + 1
30 = 1.30 + 0

Thus gcd(123, 277) = 1.

Exercise: Find gcd(12378, 3054) Ans:- 6.

Useful Result
Definition 1.19. If a and b integers, the linear combination of a and b is a
sum of the form ax + by, where x and y are integers.
Theorem 1.10. If a and b are positive integers, then there exists s and t
such that gcd(a, b) = sa + tb.

Proof: Claim: d = gcd(a, b) = sa + tb

Let x be the smallest positive integer that can be written as sa + tb for

some integers s and t, and let c be a common divisor a and b.

c 2018 Biruk G. AMU

Number Theory Lecture Note 29

Since c | a and c | b =⇒ c | x, so c ≤ x.

If we can show that x is a common divisor of a and b, it will then be the

greatest common divisor of a and b.

a = qx + r with 0 ≤ r < x. Solving for r, we have

r = a − qx = a − q(sa + tb) = a − qsa − qtb

= (1 − qs)a + (−qt)b.

If r is not zero, then since r < x and r is the sum of a multiple of a and a
multiple of b, we will have a contradiction to the fact that x is the smallest
positive number that is the sum of multiples of a and b. Thus r must be 0
and x | a.

In the same way we can show that x | b, and this completes the proof.

J
Let a,b and d be in Z. The integers d is the greatest common fac-
tor(divisor) of a and b if and only if

i) d|a and d|b.

ii) whenever c|a and c|b, then c|d.

J
The integers s and t can be found as follows:

Solve the next-to-last in (2) for rn :

rn = rn−2 − qn rn−1 (1.3)

Now solve the second-to-last equation in (1.2) for rn−1 :

rn−3 = qn−1 rn−2 + rn−1 =⇒ rn−1 = rn−3 − qn−1 rn−2

and substituting this expression in (1.3):

rn = rn−2 − qn [rn−3 − qn−1 rn−2 ]

Continue to work up through the equations in (1.2) and (1.1) replacing ri

by an expression involving ri−1 and ri−2 , and finally arriving at an expression
involving only a and b.

c 2018 Biruk G. AMU

Number Theory Lecture Note 30

Example 1.34. Consider the steps of the Euclidean Algorithm for gcd(252,198):

252 = 1.198 + 54
198 = 3.54 + 36
54 = 1.36 + 18
36 = 2.18 + 0

Isolate the non-zero remainders in the above equations, substituting back-

wards:

gcd(252, 198) = 18 = 54 − 1.36,

= 54 − 1.(198 − 3.54),
= 4.54 − 1.198,
= 4(252 − 1.198) − 1.198,
= 4.254 − 5.198

Therefore, gcd(252,198)=18=4.252-5.198.

(i.e a=252, b=198, s=4 and t=-5).

Example 1.35. Express 29 as a linear combination of 4147 and 10672:

Solution:

29 = 551 − 9.58,
= 551 − 9(609 − 551.1),
= 10.551 − 9.609,
= 10.(1769 − 609.2) − 9.609,
= 10.1769 − 29.609,
= 10.1769 − 29(2378 − 1769.1),
= 39.1769 − 29.2378,
= 39(4147 − 2378) − 29.2378,
= 39.4147 − 68.2378,
= 39.4147 − 68(10672 − 4147.2),
= 175.4147 − 68.10672,

As a result, we see that 29=175.4147-68.10672.

c 2018 Biruk G. AMU

Number Theory Lecture Note 31

Exercise:

1. Use the Euclidean algorithm to find the greatest common divisor of 780
and 150 and express it in terms of the two integers.

2. Find gcd(143,227), gcd(306,657) and gcd(272,1479)

J
The French mathematician Gabriel Lame(1795-1870) proved that the
number of steps required in the Euclidean Algorithm is at most five times
the the number of digits in the smaller integer.

Theorem 1.11. If k > 0, then gcd(ka,kb)=k.gcd(a,b).

Proof: If each of the equations appearing in the Euclidean Algorithm for

a and b is multiplied by k, we obtain

ak = q1 (bk) + r1 k 0 < r1 k < bk

bk = q2 (r1 k) + r2 k 0 < r2 k < r1 k
..
.
rn−2 k = qn (rn−1 k) + rn k 0 < rn k < rn−1 k
rn−1 k = qn+1 (rn k) + 0

=⇒ gcd(ka,kb)=rn k=kgcd(a,b).

Corollary 1.3. For any integer k 6= 0, gcd(ka, kb) = |k|gcd(a, b).

Proof: It suffices to consider the case in which k < 0. Then −k = |k| > 0
and by the above theorem,

gcd(ak, bk) = gcd(−ak, −bk)

= gcd(a|k|, b|k|)
= |k|gcd(a, b)

Example 1.36. gcd(12,30)=3gcd(4,10)=3.2gcd(2,5)=6.1=6.

1.3.8 Representation of Integers

The decimal representation of an integer is so familiar that we sometimes
regard it as the symbol, or name for that integer.

Example 1.37. n = 3264 = 3 × 103 + 2 × 102 + 6 × 101 + 4 × 100 .

c 2018 Biruk G. AMU

Number Theory Lecture Note 32

We say n = 3264 is the base 10 expansion of n or the decimal expansion

of n; 10 is called the base of this expansion.
The bases 2,8, and 16 are frequently used in Computer Science, and the
base 26 is sometimes used in Cryptology(it is the Science of producing and
deciphering secret codes).

Theorem 1.12. If b > 1 is an integer, then every positive integer n can be

uniquely expressed in the form

n = dk bk + dk−1 bk−1 + · · · + d1 b + d0 , . . . (∗)

where 0 ≤ di < b, i = 0, 1, 2, . . . k, and dk 6= 0.

The sequence dk dk−1 . . . d1 d0 is called the base b expansion of n. If

we need to explicitly indicate the base b, we will write the above sequence as
(dk dk−1 . . . d1 d0 )b .

Proof: Suppose that k is the largest non-negative integer so that bk ≤ n(k

could be 0). We can uniquely write

n = qbk + r, where 0 ≤ r < bk .

Let dk = q. If k = 0, then r = 0 and we are done(n = d0 ). Otherwise we

have

n = dk bk + r.

Repeat this process, using r in place of n. Let s be the largest non-negative

integer so that bs ≤ r, write

r = qbs + r1 , where 0 ≤ r1 < bs , and define ds to be q.

If s < k, define ds+1 , . . . dk−1 to be 0. Then

n = dk bk + dk−1 bk−1 + · · · + ds bs + r1 .

Continuing this process using r1 , r2 , . . . , we will eventually arrive at (∗).

Now that we know that the base b expansion exists, we can find the
digits dk , dk−1 , . . . d1 , d0 by a more direct method, easily implemented on a
computer. Note that

c 2018 Biruk G. AMU

Number Theory Lecture Note 33

n = (dk bk−1 + dk−1 bk−2 + · · · + d1 )b + d0

So that d0 is the remainder after dividing n by b, and the quotient is dk bk−1 +
dk−1 bk−2 + · · · + d1 . Similarly, if this quotient is divided by b, the remainder
is d1 .

By repeating dividing the quotients by b and saving the remainders, we

produce the digits of the base b representation of n from right to left.
Example 1.38. Find the base 4 representation of 158.

Solution: We repeatedly divide by 4 and save the remainder.

Remainders(from right to left):- 2,1,3,2. Thus 158 = (2132)4 .

No matter what base is used to represent integers, the elementary rules
of addition and multiplication are still valid. Only the appearance of the
numbers changes.
Example 1.39. Let m = (313)4 and n = (322)4 . Find the base four expan-
sion of m + n.

Solution: Adding the integers in the last column, we have 3 + 2 = (11)4 ,

so we record a 1 and carry a 1 to the next column.

Adding the digits in the second column, we have 1 + 1 + 2 = (10)4 , so we

record a 0 and carry the 1.

Finally, adding the digits in the first column, we obtain 3 + 3 + 1 = (13)4 ,

so the answer is (1301)4 .
The most common expansion used in computer work is the base 2 or
binary expansion. Since the only remainders of division by 2 are 0 and 1,
the binary expansion of every number needs only the digits 0 and 1 and
so is easily implemented and manipulated by the on-off digital circuits of a
computer.
Example 1.40. To use 26 as a base, we can use the letters A,B, ...,Z of the
English alphabet to represent the digits 0,1,2, ...,25.
In this way we can interpret ”T W O” as the base 26 representation of

(T ×262 )+(W ×261 )+(O×260 ) = (19×676)+(22×26)+(14×1) = 13430

Exercise:

c 2018 Biruk G. AMU

Number Theory Lecture Note 34

1. (144)5 = (?)10

2. (732)10 = (?)7

3. (39)10 = (?)2

4. (110101)2 = (?)10

5. (632)7 + (450)7 = (?)7

6. (32)4 × (22)4 = (?)4

c 2018 Biruk G. AMU

Chapter 2

Diophantine Equations

2.1 Linear Diophantine Equations

HISTORY: An algebraic equation is one that involves only polynomial ex-
pressions in one or more variables. What makes the equation ’Diophantine’ is
that the coefficients of the polynomials should be rational numbers(or often
integers) and also solutions must be only rational(or integer).

The study of problems that require integer solutions is often referred to

as Diophantine analysis. Although the practical applications of Diophantine
analysis have been somewhat limited in the past, this kind of analysis has
become much more important in the digital age. Diophantine analysis is very
important in the study of public-key cryptography.

Figure 2.1: Diophantus of Alexandria(about A.D 250)

Because little is known on the life of Diophantus, historians have approx-

imated his birth to be at about 200 AD in Alexandria, Egypt and his death

35
Number Theory Lecture Note 36

at 284 AD in Alexandria as well. Diophantus married at the age of 33 and

had a son who later died at 42, only 4 years before Diophantus’ death at
84. He is best known for his work, Arithmetica, which is the earliest known
book on algebra, which contains 13 books ”consisting of 130 problems giving
numerical solutions to determinate equations (those with a unique solution)
and indeterminate equations”.

The method he formulated for solving later became known as Diophan-

tine analysis. From his book, Arithmetica, only 6 of the 13 books have
survived. Scholars who studied his works concluded that ”Diophantus was
always satisfied with a rational number and did not require a whole number”.
He did not deal with negative solutions and only required one solution to a
quadratic equation, which was what most of the Arithmetica problems led to.

Brahmagupta(598-670) was the first to give the general solution of the

linear Diophantine equation ax + by = c. Diophantus did not use sophisti-
cated algebraic notation. He did, however, introduce an algebraic symbolism
that used an abbreviation for the unknown he was solving for. He also gained
fame from another book called On Polygonal Numbers. Diophantus’ meth-
ods of solving problems have had both lasting effects and great benefits for
the studies of algebra and number theory.

Two well known results from beginning number theory are examples of
diophantine equations which predate Diophantus. Both of these problems
were known by the Babylonians. These are;
1. Linear equations of two variables, ax + by = c
2. The quadratic equation of three variables, x2 + y 2 = z 2 .
Solutions to the second are often known as Pythagorean triangles, or Pythagorean
triples, since a geometric interpretation of this is lengths of the sides of a right
triangle, and the expression is, of course, the Pythagorean Theorem. Fer-
mat’s Last Theorem, that xn + y n = z n has no solution for n > 2, is a
generalization of this.

Diophantus of Alexandria(about A.D 250) was the first writer to make a

systematic study of the solution of equations in integers. Discrete mathemat-
ics deals with whole numbers of things. So when we want to solve equations,
we usually are looking for integer solutions.
Definition 2.1. An equation in two or more variables is called a Diophan-
tine equation if only integer solutions are of interest.

c 2018 Biruk G. AMU

Number Theory Lecture Note 37

A linear Diophantine equation takes the form

a1 x1 + a2 x2 + · · · + an xn = b for constants a1 , a2 , · · · , an , b.

A solution to a Diophantine equation is a solution to the equation consisting

only of integers.

Example 2.1. x3 + y 3 = z 3 has many solutions over the reals; for example,
√
x = 1, ,y = 1, z = 3 2.

However, this equation has no nonzero integer solutions.

Example 2.2. Since gcd(9, 100) = 1, there are integers x and y such that
9x + 100y = 1. For example, 9.(−11) + 100.1 = 1, and 9.89 + 100.(−8) = 1.
That is, the Diophantine equation 9x + 100y = 1 has solutions - in fact,
infinitely many solutions.

The purpose of any Diophantine equation is to solve for all the unknowns
in the problem.

2.2 Solutions to Linear Diophantine Equations

Lemma 2.1. Euclid’s Lemma: If a | bc, with gcd(a, b) = 1, then a | c.

Theorem 2.1. Let a, b, c ∈ Z. Consider the Diophantine equation

ax + by = c

(a) If gcd(a, b) = d - c, there are no solutions.

(b) If gcd(a, b) = d | c, there are infinitely many solutions of the form

x = x0 + ( db )t, y = y0 − ( ad )t

Here {x0 , y0 } is a particular solution, and t ∈ Z.

Proof: Let us suppose that a solution x0 , y0 of the given equation is known.

0 0
If x , y is any other solution, then
0 0
ax0 + by0 = c = ax + by

which is equivalent to

c 2018 Biruk G. AMU

Number Theory Lecture Note 38

0 0
a(x − x0 ) = b(y0 − y )
By the theorem 1.6, there exist relatively prime integers r and s such that
a=dr, b=ds. Substituting these values in to the last-written equation and
canceling the common factor d, we find that
0 0
r(x − x0 ) = s(y0 − y )
The situation is now this:
0
r | s(y0 − y ), with gcd(r,s)=1.
Using Euclid’s Lemma, it must be the case that
0
r | (y0 − y );
0
or, in other words, y0 − y = rt for some integer t.
Substituting, we obtain
0
x − x0 = st
This leads to the formulas
0
x = x0 + st = x0 + ( db )t
0
y = y0 − rt = y0 − ( ad )t
These values satisfy the Diophantine equations, regardless of the choice
of the integer t; for
0 0 b a
ax + by = a[x0 + ( )t] + b[y0 − ( )t]
d d
ab ab
= (ax0 + by0 ) + ( − )t
d d
= ax0 + by0 + 0.t
=c

Thus, there are an infinite number of solutions of the given equations, one
for each value of t.
Example 2.3. Solve 6x + 9y = 21.

Solution: Since gcd(6,9) = 3 |21, there are infinitely many solutions. By

trial and error, x = -7, y = 7, is a particular solution. Hence, the general
solution is
x = 3k-7, y = -2k + 7.

c 2018 Biruk G. AMU

Number Theory Lecture Note 39

For example, setting t = 5 produces the solution x = 8, y = -3.

Example 2.4. Solve 6x + 9y = 5.

Solution: Since gcd(6,9) = 3 - 5, the equation has no solutions.

Example 2.5. Consider the linear Diophantine equation
172x + 20y = 1000
To evaluate gcd(172,20), apply the Euclidean’s Algorithm.

172 = 8.20 + 12
20 = 1.12 + 8
12 = 1.8 + 4
8 = 2.4 + 0

Because 4 | 1000, a solution to this equation exists.

To obtain the integer 4 as a linear combination of 172 and 20, we work

backward through the previous calculations, as follows:

4 = 12 − 8
= 12 − (20 − 12)
= 2.12 − 20
= 2(172 − 8.20) − 20
= 2.172 + (−17)20

Upon multiplying this relation by 250, we arrive at

1000 = 250.4 = 250[2.172 + (−17)20]

= 500.172 + (−4250)20

So that x=500 and y = -4250 provide one solution to the Diophantine equa-
tion in question. All other solutions are expressed by
20 172
x = 500 + ( )t = 500 + 5ty = −4250 − ( )t = −4250 − 43t
4 4
for some integer t.

To produce the solutions in the positive integers, if any happens to exist.

For this, t must be chosen to satisfy simultaneously the inequalities

c 2018 Biruk G. AMU

Number Theory Lecture Note 40

5t + 500 > 0 − 43t − 4250 > 0

or what amounts to the same thing,

36
−98 > t > −100
43
Because t ∈ Z, we conclude that t= -99.

Thus, our Diophantine equation has a unique positive solution x=5, y=7
corresponding to the value t=-99.

Corollary 2.1. If gcd(a,b)=1 and if x0 , y0 is a particular solution of the

linear Diophantine equation ax + by = c, then all solutions are given by

x = x0 + bt , y = y0 − at

for integral values of t.

Example 2.6. The equation 5x+22y=18 has x0 = 8, y0 = −1 as one solu-

tion. From the corollary, a complete solution is given by x=8+22t, y=-1-5t
for arbitrary t.

Diophantine equations used to solve word problems.

Example 2.7. A customer bought a dozen pieces of fruit, apples, and or-
anges, for 1.32 birr. If an apple costs 3 cents more than an orange and
more apples than oranges were purchased, how many pieces of each kind
were bought?

Solution: To set up this problem as a Diophantine equation, let x be the

number of apples and y be the number of oranges purchased; in addition, let z
represent the cost(in cents) of an orange. Then the conditions of the problem
lead to

(z+3)x+zy=132

or equivalently

3x+(x+y)z=132

Because x+y, the previous equation may be replaced by 3x+12z = 132 which
intern, simplifies to x + 4z = 44.

c 2018 Biruk G. AMU

Number Theory Lecture Note 41

The object is to find integers x and z satisfying the Diophantine equation

x + 4z = 44 (2.1)
gcd(1,4)= 1 is a divisor of 44, there is a solution to this equation. Upon
multiplying the relation
1 = 1(-3) + 4.1 by 44 to get
44 = 1(-132) + 4.44
it follows that x0 = −132, z0 = 44 serves as one solution.

All other solutions of (2.1) are of the form

x = -132 + 4t z = 44 - t
where t is an integer.

Not all of the choices for t furnish solutions to the original problem. Only
values for t that ensure 12 ≥ x > 6 should be considered.

This requires obtaining those values of t such that

12 ≥ −132 + 4t > 6
Now, 12 > −132 + 4t ⇒ t ≤ 36, whereas −132 + 4t > 6
1
gives t ≥ 34
2
The only integral values of t to satisfy both inequalities are t = 35 and
t = 36. Thus, there are two possible purchases: a dozen apples costing 11
cents a piece(the case where t = 36), or the case where t = 35: 8 app;es at
12 cents each and 4 oranges at 9 cents each.
Example 2.8. The problem of the ”hundred fowls”

The problem states: If a cock is worth 5 coins, a hen 3 coins, and three
chicks together 1 coin, how many cocks, hens, and chicks, totaling 100, can
be bought for 100 coins?

Solution: In terms of equations:

Let x = the number of cocks
y = the number of hens
z = the number of chicks :

c 2018 Biruk G. AMU

Number Theory Lecture Note 42

5x + 3y + 13 z = 100 x + y + z = 100

Eliminating one of the unknowns, we are left with a linear Diophan-

tine equation in the two other unknowns. Specifically, because the quantity
1
z = 100 − x − y, we have 5x + 3y + (100 − x − y) = 100, or 7x + 4y = 100.
3
This equation has the general solution x = 4t, y = 25 − 7t, so that
z = 75 + 3t, where t is arbitrary integer.

To get all solutions in the positive integers, t must be chosen to satisfy

simultaneously the inequalities:

4t > 0 25 − 7t > 0 75 + 3t > 0

The last two of these are equivalent to the requirement

4
−25 < t < 3 because t ∈ Z+ , t = 1, 2, 3.
7
Example 2.9. Solve 126x - 204y = 4.

Solution: First find gcd(126,204) using Euclidean Algorithm.

204 = 1.126 + 78
126 = 1.78 + 48
78 = 1.48 + 30
48 = 1.30 + 18
30 = 1.18 + 12
18 = 1.12 + 6
12 = 2.6 + 0.

Hence gcd(204,126) = 6. But 6 - 4(i.e 6 is not the factor of 4).

∴ the Diophantine equation 126x − 204y = 4 does not have a solution.

Example 2.10. Find the complete solution of 60x + 25y = 10.

Solution: Since gcd(60,25) = 5 and 5 is a factor of 10, the Diophantine

equation 60x + 25y = 10 has a solution.

c 2018 Biruk G. AMU

Number Theory Lecture Note 43

First we express 5 = gcd(60,25) as linear combination of 60 and 25.

F rom 60 = 2.25 + 10
25 = 2.10 + 5

We get 5 = 25 − 2.10
= 25 − 2.(60 − 2.25)
= 5.25 + (−2)60

Hence x = -4, y = 10 is a particular solution of the Diophantine equation

60x + 25y = 10. Therefore, the relation is multiplied by 2 to arrive at

10 = 2.5 = 2[5.25 + (−2)60]

= −4.60 + 10.25

∴ the complete solution is given by

(x,y) = (-4 + 5t, 10 - 12t), t ∈ Z.
Example 2.11. Find a solution to the Diophantine equation
20x + 30y75z = 100
Solution: Since gcd(20,30,75) = 5 and 5 | 100, the Diophantine equation has
a solution.

Express gcd(20,30) as a linear combination of 20 and 30.

30 = 1.20 + 10
20 = 2.10 + 0

Hence gcd(20,30) = 10 = -1.20 + 1.30

Then we express gcd(20,30,75) = gcd(gcd(20,30),75) = gcd(10,75) as a

linear combination of 10 and 75.
But

75 = 7.10 + 5
10 = 2.5 + 0

Hence 5 = -7.10 + 1.75

c 2018 Biruk G. AMU

Number Theory Lecture Note 44

Substituting the above value of 10(i.e 10 = -1.20 + 1.30),

we obtain

5 = −7.10 + 1.75
= −7(−1.20 + 1.30) + 1.75
= 7.20 + (−7)30 + 1.75

Then

100 = 20.5
= 20(7.20 + (−7)30 + 1.75)
= 140.20 + (−140)30 + 20.75

∴ x = 140, y = -140, z = 20 or (140,-140,20) is a particular solution of the

Diophantine equation 20x + 30y + 75z = 100.

2.3 The Method of Euler in Linear Equations

If the number of variables in a linear Diophantine equation is greater than
two, then there is a more efficient method of solving the equation than the
above method discussed. This method is called the Euler’s Method.

Let us demonstrate this method by considering the examples below.

Example 2.12. Find the complete solution of the Diophantine equation

20x + 30y + 75z = 100

Solution: 20x + 30y + 75z = 100 if and only if 4x + 6y + 15z = 20

Solving for the variable with the least coefficient, we get

6y + 15z 2y + 5z
x=5- ⇔ x = 5 - 3( )
4 4
Since x is an integer, it follows that 2y + 5z is a multiple of 4.

Hence, 2y + 5z = 4t for some integer t. Then solving for y, We get

5z
y = 2t -
2
Thus z = 2k for some integer k, consequently

c 2018 Biruk G. AMU

Number Theory Lecture Note 45

(x,y,z) = (5-3t,2t-5k,2k) where t,k ∈ Z

gives the complete solution of the Diophantine equation 20x + 30y + 75z =
100.

Example 2.13. Find the infinite solutions of the Diophantine equation

16x + 8y + 10z + 4w = 6

Solution: Since gcd(16,8,10,4) = 2 and 2 | 6, the Diophantine equation as a

solution.

Now solving for w we obtain

3 − 5z
w = -4x - 2y +
2
It follows that 3 - 5z = 2t for some integer t.

Consequently, z must be an odd integer(why?)

3 − 5z = 2t ←→ 3 − 2t = 5z
(1 + 2) − 2t = 5z
1 + 2(1 − t) = 5z
1 + 2k = 5z, for some k∈Z

⇒ 5z is odd and z is odd,(can not be even, if z is even 5z is even, and this is

a contradiction with the equation 5z = 1 + 2k.)

Hence the complete solution of the Diophantine equation is given by

3 − 5z
(x,y,w,z) = (x,y,z,-4x - 2y + ) where x,y,z are integers and z is odd.
2

2.4 Some General Notions of Diophantine

Equations
Suppose that f (x1 , x2 , . . . , xn ) ∈ Z[x1 ,x2 ,...,xn ] . Then the equation

f (x1 , x2 , . . . , xn ) = 0 in Z (2.2)

is called a Diophantine equation.

c 2018 Biruk G. AMU

Number Theory Lecture Note 46

· If deg(f ) = 1, then f (x1 , x2 , . . . , xn ) = 0 is called a linear Diophantine

equation.

· If deg(f ) ≥ 2, then the above equation is called a Diophantine equation

of higher order.
Example 2.14. 3x + 4y + 3z = 0, where x, y, z ∈ Z is called a linear
Diophantine equation.
x2 − 2y 2 − 3z 2 = 0 where x, y, z ∈ Z is a higher order Diophantine equation.

When we study about Diophantine equations we want to answer the fol-

lowing questions:
1. Existential question: Does the Diophantine equation have a solution?
2. Size of the solution set: The number of the solutions of the Diophantine
equation finite or infinite?
3. Is it possible to find all the (integral) solutions?
Case 1: Polynomials with one variable.

Suppose f (x) = an xn + an−1 xn−1 + · · · a1 x + a0 with an , a0 6= 0 is a

polynomial with coefficients in Z. Then f (x) = 0 has at most n solutions in
Z.
Lemma 2.2. If b ∈ Z is a solution of the Diophantine equation
an xn + an−1 xn−1 + · · · a1 x + a0 = 0, then b is a factor of a0 .
Proof: Let b ∈ Z be a solution of f (x) = an xn + an−1 xn−1 + · · · a1 x + a0

then f (b) = 0 ⇐⇒ an bn + an−1 bn−1 + · · · a1 b + a0 = 0

=⇒ b(an bn−1 + an−1 bn−2 + · · · a1 ) = −a0

=⇒ b is a factor of a0 .
From the above lemma, the solutions of f (x) = 0 are among the factors
of a0 , which are finite.
Example 2.15. (x + 2)2 = x2 + 4x + 4 = 0

Factors(divisors) of 4: ±1, ±2, ±4.

Therefore, solution: x = −2.

c 2018 Biruk G. AMU

Number Theory Lecture Note 47

Case 2: Polynomials with more than one variables.

f (x1 , x2 , . . . , xn ) ∈ Z[x1 ,x2 ,...,xn ] , then the equation f (x1 , x2 , . . . , xn ) = 0

may or may not have integral solutions. There is no a single criterion or
method for solving the different types of Diophantine equations.
Example 2.16. It is known that
x3 + y 3 + z 3 = 3
has four solutions, but it is not yet known whether (1,1,1), (4,4,-5), (4,-5,4)
and (-5,4,4) are only solutions.

 The Diophantine equation x3 +y 3 +z 3 = 2 has infinitely many solutions.

Indeed, for each natural number n,

(x, y, z) = (1 + 6n3 , 1 − 6n3 , −6n2 )
is a solution of the Diophantine equation. However we still don’t know
whether these are the only solutions of the Diophantine equation.

 It is conjectured that x = t = 3, y = s = 2 are the only solutions of

xs − y t = 1
with x, y, s, t each greater than 1.
In short, the question of finding solutions of a Diophantine equation with
more than one variable is quite complex.

The equation x2 + y 2 = z 2 , suggests that we consider its extension involv-

ing higher powers, such that x3 + y 3 = z 3 , and so on.

Fermat Conjectured that

xn + y n = z n
has no solutions in positive integers for n > 2, and even claimed he had a
proof. Due to lack of a proof for more than 350 years, this conjecture was
always called ”Fermat’s Last Theorem”. This famous conjecture was finally
shown to be correct by Andrew Wiles, whose proof appeared in his paper
”Modular elliptic curves and Fermat’s Last Theorem”. published in Annals
of Mathematics in 1995.

c 2018 Biruk G. AMU

Number Theory Lecture Note 48

Figure 2.2: Andrew Wiles

c 2018 Biruk G. AMU

Chapter 3

Theory of Congruence

3.1 Introduction to Congruences

A congruence is nothing more than a statement about divisibility. The theory
of congruences was introduced by Carl Friedreich Gauss (at the beginning of
the nineteenth century). Gauss contributed to the basic ideas of congruences
and proved several theorems related to this theory. We start by introducing
congruences and their properties.

Recall : (Division Algorithm) Given any two integers a and b, we can

always find an integer q such that

a = qm + r

where r is an integer satisfying 0 ≤ r < |m|. The division algorithm tells

us there are only m possible remainders when divided by m. If we fix this
divisor, we can group integers by the remainder. Each group is called a re-
mainder class modulo m(or sometimes residue class).

3.1.1 Congruence Modulo n

We say a is congruent to b modulo m, and write,

a ≡ b (mod m)

provided a and b have the same remainder when divided by m.(provided a

and b belong to the same remainder class modulo m.)

49
Number Theory Lecture Note 50

Example 3.1. If m = 27, since 35≡ 8(mod 27), 35 and 8 are congruent
modulo m.
Example 3.2. 19 ≡ 5 (mod 7). Similarly 2k + 1 ≡ 1 (mod 2) which means
every odd number is congruent to 1 modulo 2.
Exercise: Check if the following are true.
a. -64 and 40 are congruent modulo 140.
b. 25 and 60 are congruent modulo 50.
There are many common properties between equations and congruences.
Some properties are listed in the following theorem.
Theorem 3.1. Let a,b,c and d denote integers. Let m be a positive integers.
Then:
1. If a ≡ b (mod m), then b ≡ a (mod m).
2. If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).
3. If a ≡ b (mod m), then a + c ≡ b + c (mod m).
4. If a ≡ b (mod m), then ac ≡ bc (mod m).
5. If a ≡ b (mod m), then ac ≡ bc (mod m)c, for c > 0.
6. If a ≡ b (mod m) and c ≡ d (mod m) then a + c ≡ (b + d) (mod m).
7. If a ≡ b (mod m) and c ≡ d (mod m) then ac ≡ bd (mod m).

3.2 The Notion of Congruence and Residue

Classes
3.2.1 Congruence and Divisibility
For any integers a, b, and m, we have
a ≡ b (mod m)
if and only if m | a − b.
Example 3.3. a. 67 ≡ 1 (mod 6), since 6 | 67 − 1 = 66.
b. 72 ≡ −5 (mod 7), since 7 | 72 − (−5) = 77.
c. 27 6= 8 (mod 9), since 9 - 27 − 8 = 19.

c 2018 Biruk G. AMU

Number Theory Lecture Note 51

3.2.2 Congruence and Equality

For any integers a, b, and m, we have

a ≡ b (mod m)

if and only if a = b + km for some integer k.

3.2.3 Residue classes

Theorem 3.2. If m is an integer, then the relation

Rm = {(a, b)|a ≡ b(mod m), a, b ∈ Z}

is an equivalence relation on Z.
Proof:(exercise)

Since congruence modulo m is an equivalence relation, it partitions the

set Z of integers in to disjoint equivalence classes called the residue classes
modulo m. Residue class consists of all those integers with the same re-
mainder when divided by m.

The notation [x]m , or simply [x] is used to denote the residue class (modulo
m) containing an integer x, that is, those integers which are congruent to x.
In other words,
[x]m = {a ∈ Z|a ≡ x(mod m)}

Accordingly, the residue classes can be denoted by

[0], [1], [2], [3], [4], ....., [m − 1]

Example 3.4. : Describe the remainder classes modulo 5. Solution: We

want to classify numbers by what their remainders would be when divided by
5. From the division algorithm, we know there will be exactly 5 remainder
classes (since 0 ≤ r < 5)
First we consider r = 0
a = 5q + 0
(therefore we are looking for the multiples of 5). We get the infinite set:

{..., −15, −10, −15, 0, 5, 10, 15, 20, ...} = [0]5

c 2018 Biruk G. AMU

Number Theory Lecture Note 52

Next we consider r = 1. Which integers are, when divided by 5, have remain-

der 1? We get the remainder class

{..., −14, −9, −4, 1, 6, 11, 16, 21, ...} = [1]5

remainder classes for 2, 3, and 4 are, respectively

{..., −13, −8, −3, 2, 7, 12, 17, 22, ...} = [2]5

{..., −12, −7, −2, 3, 8, 13, 18, 23, ...} = [3]5
{..., −11, −6, −1, 4, 9, 14, 19, 24, ...} = [4]5
If two numbers belong to the same remainder class, then in some way, they
are the same. We want to say that 8 and 23 are basically the same, even
though they are not equal. It would be wrong to say 8=23. Instead we write
8 ≡ 23. But this is not always true. It works if we are thinking division by
5. What we actually write is this:

8 ≡ 23 (mod 5)

.
which is read, ”8 is congruent to 23 modulo 5” (or just”mod 5 ”)
Ofcourse then we could observe that

8 6= 23 (mod 7)

3.3 Operations on Congruence Classes and

Basic Properties
3.3.1 Congruence and Arithmetic
Suppose a ≡ b (mod m) and c ≡ d (mod m). Then the following hold:
1. a + c ≡ b + d (mod m)

2. a − c ≡ b − d (mod m)

3. ac ≡ bd (mod m)

c 2018 Biruk G. AMU

Number Theory Lecture Note 53

Example 3.5. Observe that 2 ≡ 8 (mod 6) and 5 ≡ 41 (mod 6). Then:

2 + 5 ≡ 8 + 41 or 7 ≡ 49 (mod 6)

2.5 ≡ 8.41 (mod 6) or 10 ≡ 328 (mod 6).

Remark 3.1. Suppose p(x) is a polynomial with integral coefficients.

If s ≡ t (mod m), then

p(s) ≡ p(t) (mod m)

Example 3.6. Suppose p(x) = 3x2 − 7x + 5. Then p(2) = 3 and p(8) = 141.

Hence 3 ≡ 141 (mod 6).

Note: We can basically replace any number in a congruence with any other
number it is congruent to.

Example 3.7. Find the remainder of 3491 divided by 9.

Solution: We want to find x such that x ≡ 3491 (mod 9)

Now 3491 = 3000 + 400 + 90 + 1. Ofcourse 90 ≡ 0 (mod 9), so we can

replace the 90 in the sum with 0. Why is this okay? we are actually subtract-
ing the ”same” thing from both sides:

x ≡ 3000 + 400 + 90 + 1 (mod 9)

−0 ≡ 90 (mod 9)

x ≡ 3000 + 400 + 0 + 1 (mod 9)

Next, note that 400 = 4 × 100, and 100 ≡ 1 (mod 9)(since 9|99). So we can
replace the 400 with simply a 4.

We know 100 ≡ 1 (mod 9), so if we multiply both sides by 4, we get

400 ≡ 4 (mod 9).

c 2018 Biruk G. AMU

Number Theory Lecture Note 54

Similarly we can replace 3000 with 3, since 1000 = 1 + 999 ≡ 1 (mod 9).
So our original congruence becomes

x ≡ 3 + 4 + 0 + 1 (mod 9)
x ≡ 8 (mod 9)

∴ 3491 divided by 9 has remainder 8.

Example 3.8. Find the remainder when 3123 is divided by 7.
Solution: We want to find the smallest positive x such that x ≡ 3123 (mod 7)

Now we write 3123 = (33 )41 . We have 3123 = 2741 ≡ 641 (mod 7) (since
27 ≡ 6 (mod 7)).

Notice 62 = 36 ≡ 1 (mod 7). Thus, 641 = 6.(62 )20 ≡ 6.120 (mod 7). But
120 = 1, so we are done: 3123 ≡ 6 (mod 7).

3.3.2 Arithmetic of Residue Classes

0
+0 and 0 .0 are defined for our residue classes modulo m:

[a]m + [b]m = [a + b]m

and
[a]m .[b]m = [a.b]m
.

Example 3.9. Consider the residue classes modulo m = 6; that is,

[0], [1], [2], [3], [4], [5]

Then, [2] + [3] = [5], [4] + [5] = [9] = [3]

and
[2].[2] = [4], [2].[5] = [10] = [4]
[2].[5] = [10] = [4].

3.3.3 Integers Modulo m, Zm

The integers modulo m, denoted by Zm , refers to the set

Zm = {0, 1, 2, 3, . . . m − 1}

c 2018 Biruk G. AMU

Number Theory Lecture Note 55

Where addition and multiplication are defined by the arithmetic modulo m

or, in other words, the corresponding operations for the residue classes. This
means there is no essential difference between Zm and the arithmetic of the
residue classes modulo m, and so they will be used interchangeably.

3.3.4 Cancellation Laws for Congruences

Recall that Z satisfy (Cancellation Law): If ab = ac, and a 6= 0, then b = c.
(ordinary arithmetic)

The above cancellation law is not true for congruences. For example,
3.1 ≡ 3.5 (mod 6) but 1 6= 5 (mod 6). That is, we can not cancel the 3 even
though 3 6= 0 (mod 6) ... (arithmetic modulo m)

Theorem 3.3. (Modified Cancellation Law): Suppose

ab ≡ ac (mod m)

and gcd(a, m) = 1
Then
b ≡ c (mod m)

Proof: If a | bc and gcd(a, b) = 1, then a | c → (Euclid’s Lemma)

⇒ m | ab − ac = a(b − c) and gcd(a, m) = 1, then m | b − c ⇒ b − c = mt,

for some t.

⇒ b ≡ c (mod m).

Theorem 3.4. Suppose ab ≡ ac (mod m) and d = gcd(a, m). Then

m
b ≡ c (mod )
d

Proof: Let m = dm1 and a = da1 with gcd(a1 , m1 )=1.

c 2018 Biruk G. AMU

Number Theory Lecture Note 56

ab ≡ ac (mod m) ⇒ a(b − c) = mq, for someq ∈ Z

⇒ da1 (b − c) = dm1 q
⇒ a1 (b − c) = m1 q
a1 (b − c)
⇒q=
m1

a1 (b − c)
As gcd(a1 , m1 ) = 1, we have = q ⇒ a1 q1 = q and we see that
m1
(b − c)
= q1 ∈ Z i.e. b − c = m1 q1 for some integer q1 .
m1
⇒ b ≡ c (mod m1 )
m m
Thus, since m1 = , we get b ≡ c (mod ) as desired.
d d

In particular, if gcd(a, m) = 1, then we get

m
ab ≡ ac (mod m) ⇒ b ≡ c (mod ) ≡ c (mod m).
1
Example 3.10. Simplify the following congruences using division.

(a) 24 ≡ 39 (mod 5) and (b) 24 ≡ 39 (mod 15)

Solution:
(a) Both 24 and 39 are divisible by 3, and gcd(3, 5) = 1. So we get 8 ≡ 13
(mod 5).
15
(b) We can divide both sides by 3; we get 8 ≡ 13 (mod ) ⇒ 8 ≡ 13
gcd(24, 15)
(mod 5).

Example 3.11. Consider the following Congruence:

6 ≡ 36 (mod 10) (3.1)

Since gcd(3, 10) = 1, but gcd(6, 10) 6= 1, we can divide both sides of (1)
by 3 but not by 6. That is

2 ≡ 12 (mod 10)

c 2018 Biruk G. AMU

Number Theory Lecture Note 57

but 1 6= 6 (mod 10).

However, by Theorem 3.2.2, we can divide both sides of (3.1) by 6 if we

also divide the modulus by 2 = gcd(6, 10).

Remark: Suppose p is a prime. Then the integer 1 through p − 1 are rel-

atively prime to p. Thus the usual cancellation law does hold when the
modulus is a prime p. That is :

If ab ≡ ac (mod p) and a 6= 0 (mod p), then

b ≡ c (mod p)
Thus Zp , the integers modulo a prime p, plays a very special role in number
theory.

3.4 Basic Facts From Group Theory In The

Notion of Congruence
Let Z be the set of integers, and let n be a fixed positive integer. We define
a relation ≡ on Z as follows:

∀a, b ∈ Z, a ≡ b (mod n) if a − b is a multiple of n.

It is an easy exercise to show that ≡ is an equivalence relation on Z.

Notation: For x ∈ Z, let [x] denote the equivalence class of x. Let

Zn = {[0], [1], ..., [n − 1]}.

Claim 1: Every element of Z belongs to exactly one of the equivalence

classes in Zn .

Recall: The Division Algorithm

If a, b ∈ Z with b > 0, there exists unique integers q and r such that

a = q.b + r, 0 ≤ r < b.

Proof of claim 1: Let k ∈ Z. By division algorithm, ∃q, r ∈ Z such that

k = q.n + r and 0 ≤ r < n. Then k − r = qn and so k ≡ r (mod n).

c 2018 Biruk G. AMU

Number Theory Lecture Note 58

Thus k ∈ [r]. Since 0 ≤ r < n, [r] ∈ Zn . Hence k belongs to one the

elements of Zn . Since the elements of Zn are distinct equivalence classes,
they have no elements in common. This proves our claim.

We next define an addition on Zn as follows:

For [m], [k] ∈ Zn , set [m] + [k] = [m + k].

0 0
Claim 2: The above addition is well defined, i.e., if m ∈ [m] and k ∈ [k],
0 0
then [m + k] = [m + k ].
0 0
Proof: We have m ≡ m (mod n) and k ≡ k (mod n).
0 0
Hence, m = m + qn and k = k + pn for some integers p, q.

Then,
0 0
m + k = m + k + (p + q)n

and so
0 0
m + k ≡ m + k (mod n)

Therefore,
0 0
[m + k] = [m + k ]

Claim 3: Zn is a group with the addition defined above.

Proof:

(1) Closure: Let [m],[k]∈ Zn , then [m] + [k] = [m + k]∈ Zn .

(2) Associativity: Let [m],[k],[p]∈ Zn , then

([m] + [k]) + [p] = [m + k] + [p]

= [(m + k) + p]
= [m + (k + p)]
= [m] + [k + p]
= [m] + ([k] + [p]).

(3) Existence of identity: [0]∈ Zn is the identity of Zn .

c 2018 Biruk G. AMU

Number Theory Lecture Note 59

(4) Existence of inverse: For [m]∈ Zn , [n − m]∈ Zn and

[m] + [n − m] = [n] = [0] and [n − m] + [m] = [n] = [0].

Hence, [n − m] is the inverse of [m].

Thus [m] is invertible.

Notation: We shall denote elements of the group Zn by 0,1,2, ... , n−1 instead
of denoting by [0],[1], ... ,[n − 1], where there is no danger of ambiguity.

3.5 Solving Congruences

3.5.1 Linear Congruences
Because congruences are analogous to equations, it is natural to ask about
solutions of linear equations. In this section,we will be discussing linear
congruences of one variable and their solutions. We start by defining linear
congruences.
Example 3.12. Is there a value of x that satisfies
3x + 2 ≡ 4 (mod 5)
simply compute 3x + 2 for values of x ∈ {0, 1, 2, 3, 4}. This gives 2,5,8,11,
and 14 respectively, for which only 14 is congruent to 4.

Using our rules for the algebra of congruences. Subtracting 2 from both
sides we get
3x ≡ 2 (mod 5)
Then to divide both sides by 3, we first add 0 to both sides. (10 really is 0
since they are congruent modulo 5). This gives
3x ≡ 12 (mod 5)
Now divide both sides by 3. Since gcd(3,5) = 1, we do not need to change
the modulus:
x ≡ 4 (mod 5) (general solution) or

x = 4 + 5k for any integer k.

c 2018 Biruk G. AMU

Number Theory Lecture Note 60

Definition 3.1. A congruence of the form ax ≡ b (mod m) where x is an

unknown integer is called a linear congruence in one variable.

It is important to know that if x0 is a solution for a linear congruence,

then all integers xi such that xi ≡ x0 (mod m) are solutions of the linear
congruence. Notice also that ax ≡ b (mod m) is equivalent to a linear Dio-
phantine equation i.e. there exists y such that ax − my = b. We now prove
theorems about the solutions of linear congruences.

Theorem 3.5. Let a, b and m be integers such that m > 0 and let d =
gcd(a, m). If d does not divide b, then the congruence ax ≡ b (mod m)
has no solutions. If d | b, then ax ≡ b (mod m) has exactly d incongruent
solutions modulo m.

Proof: exercise.

Corollary 3.1. If gcd(a,m) = 1, then the linear congruence ax ≡ b (mod m)

has a unique solution modulo m.

Given relatively prime integers a and m, the congruence ax ≡ 1 (mod m)

has a unique solution. This solution is sometimes called the (multiplicative)
inverse of a modulo m.

Example 3.13. Consider the linear congruence 18x ≡ 30 (mod 42).

gcd(18,42) = 6 and 6 | 30. This implies ∃ exactly six solutions, which are
incongruent modulo 42.
42
One solution is x = 4(by inspection). x ≡ 4 + ( )t ≡ 4 + 7t (mod 42)
6
t = 0, 1, 2, 3, 4, 5 or

x ≡ 4, 11, 18, 25, 32, 39 (mod 42).

Example 3.14. Solve the following congruences for x.

(1) 7x ≡ 12 (mod 13).

All we need to do here is divide both sides by 7. We add 13 to the right

hand side repeatedly until we get a multiple of 7(adding 13 is the same

c 2018 Biruk G. AMU

Number Theory Lecture Note 61

as adding 0, so this is legal). We get 25,38,51,64,77 - got it. So we

have

7x ≡ 12 (mod 13)
7x ≡ 77 (mod 13)
x ≡ 11 (mod 13)

(2) 84x − 38 ≡ 79 (mod 15).

Here, since we have numbers larger than the modulus, we can reduce
them prior to applying any algebra. We have 84 ≡ 9, 38 ≡ 8, 74 ≡ 4.
Thus,

84x − 38 ≡ 79 (mod 15)

9x − 8 ≡ 4 (mod 15)
9x ≡ 12 (mod 15)
9x ≡ 72 (mod 15)

We got the 72 by adding 0 ≡ 60 (mod 15) to both sides of the congru-

ence. Now divide both sides by 9. However since gcd(9,15)=3, we must
divide the modulus by 3 as well:

x ≡ 8 (mod 5).

So the solutions are those values which are congruent to 8, or equiva-

lently 3, modulus 5. This means that in some sense there are 3 solutions
modulo 15: 3,8, and 13. We can write the solution:

x ≡ 3 (mod 15); x ≡ 8 (mod 15); x ≡ 13 (mod 15).

(3) 20x ≡ 23 (mod 14)

First, reduce modulo 14:

20x ≡ 23 (mod 14)

6x ≡ 9 (mod 14)

We could now divide both sides by 3, or try to increase 9 by a multiple

of 14 to get a multiple of 6. If we divide by 3, we get,

c 2018 Biruk G. AMU

Number Theory Lecture Note 62

2x ≡ 3 (mod 14)

Now try adding multiple of 14 to 3, in hopes of getting a number we

can divide by 2. This will not work! Every time we add 14 to the right
side, the result will still be odd. We will never get an even number, so
we will never be able to divide by 2. Thus there are no solutions to the
congruence.
In general, given the congruence
ax ≡ b (mod n),
if a and n are divisible by a number which b is not divisible by, then there
will be no solutions. In fact, we really only need to check one divisor of a
and n: the greatest common divisor. Thus, a more compact way to say this is:

If gcd(a, n)- b, then ax ≡ b (mod n) has no solution.

3.5.2 Chinese Remainder Theorem(CRT)

Theorem 3.6. Chinese Remainder Theorem. Let n1 , n2 , · · · , nr be positive
integers such that gcd(ni , nj ) = 1 for i 6= j. Then the system of linear
congruences

x ≡ a1 (mod n1 )
x ≡ a2 (mod n1 )
..
.
x ≡ ar (mod n1 )

has a simultaneous solution, which is unique modulo the integer n1 n2 · · · nr .

Proof: Let n = n1 n2 · · · nr . For each k = 1, 2, · · · , r.

n
Let Nk = = n1 n2 · · · nk−1 nk+1 · · · nr (factor nk is omitted)
nk
ni are relatively prime in pairs, so that gcd(Nk , nk ) = 1. We can solve
Nk x ≡ 1 (mod nk ). Let xk be the unique solution.

Claim: r
X
x= ai Ni xi
i=1

c 2018 Biruk G. AMU

Number Theory Lecture Note 63

is a simultaneous solution of the given system.

Existence: First, observe that Ni ≡ 0 (mod nk ) for i 6= k, because nk | Ni in

this case. The result is
x = ri=1 ai Ni xi ≡ ak Nk xk (mod nk )
P

But the integer xk was chosen to satisfy the congruence Nk x ≡ 1 (mod nk ),

which forces x ≡ ak .1 ≡ ak (mod nk ). This shows that the solution to the
given system of congruences exists.

0
Uniqueness: Suppose that x is any other integer that satisfies these congru-
0 0
ences. Then x ≡ ak ≡ x (mod nk ) for k = 1, 2, · · · , r and so nk | x − x for
0
each value of k. Because gcd(ni , nj ) = 1 implies n1 n2 · · · nr | x − x .
0
Hence, x ≡ x (mod n).
Example 3.15. Solve the following simultaneous congruences
x≡2 (mod 3)
x≡3 (mod 5)
x≡2 (mod 7)
n 105 n
Solution: We have n = 3.5.7 = 105 and N1 = = = 35, N2 = = 21,
3 3 5
n
N3 = = 15.
7
Now the linear congruences
35x ≡ 1 (mod 3), 21x ≡ 1 (mod 5), 15x ≡ 1 (mod 7).
are satisfied by x1 = 2, x2 = 1, x3 = 1, respectively. Thus, a solution of the
system is given by
x = 2.35.2 + 3.21.1 + 2.15.1 = 233.
We get the unique solution x = 233 ≡ 23 (mod 105).
Example 3.16. Solve the system of congruence
x≡1 (mod 3)
x≡4 (mod 5)
x≡6 (mod 7)

c 2018 Biruk G. AMU

Number Theory Lecture Note 64

Solution: Begin with the congruence with the largest modulus:

x ≡ 6 (mod 7) ⇒ x = 7j + 6 for some integer j.

x ≡ 4 (mod 5) ⇒ 7j +6 ≡ 4 (mod 5) and solving for j we get j = 5k +4,

for some integer k.

x = 7j + 6 = 7(5k + 4) + 6 = 35k + 34 ⇒ 35k + 34 ≡ 1 (mod 3). Solving

for k we get k ≡ 0 (mod 3).

k ≡ 0 (mod 3) ⇒ k = 3l, for some integer l.

Therefore, x = 35k + 34 ⇒ x = 35(3l) + 34 = 105l + 34

⇒ x ≡ 34 (mod 105).
Example 3.17. Solve the linear congruence
17x ≡ 9 (mod 276)
Solution: Because 276 = 3.4.23, this is equivalent to finding a solution for
the system of congruences
17x ≡ 9 (mod 3)
17x ≡ 9 (mod 4)
17x ≡ 9 (mod 2)3
or
x≡0 (mod 3)
x≡1 (mod 4)
17x ≡ 9 (mod 2)3
Note that if x ≡ 0 (mod 3), then x = 3k for any integer k. We substitute in
to the second congruence of the system and obtain
3k ≡ 1 (mod 4)
Multiplication of both sides of this congruence by 3 gives us
k ≡ 9k ≡ 3 (mod 4)
so that k = 3 + 4j, where j is an integer. Then, x = 3(3 + 4j) = 9 + 12j.
For x to satisfy the last congruence, we must have 17(9 + 12j) ≡ 9 (mod 23)
or 204j ≡ −144 (mod 23) which reduces to

c 2018 Biruk G. AMU

Number Theory Lecture Note 65

3j ≡ 6 (mod 23);
in consequence, j ≡ 2 (mod 23). This yields j = 2 + 23t, with t an integer,
whence
x = 9 + 12(2 + 23t) = 33 + 276t
All in all, x ≡ 33 (mod 276) provides a solution to the system of congruences
and, in turn, a solution to 17x ≡ 9 (mod 276).
Theorem 3.7. The system of linear congruences
ax + by ≡ r (mod n)
cx + dy ≡ s (mod n)
has a unique solution modulo n whenever gcd(ad - bc,n) = 1.

Proof: Let us multiply the first congruence of the system by d, the sec-
ond congruence by b, and subtract the lower result from the upper. These
calculations yield
(ad − bc)x ≡ dr − bs (mod n) (3.2)
The assumption gcd(ad-bc) = 1 ensures that the congruence
(ad − bc)z ≡ 1 (mod n)
possesses a unique solution; denote the solution by t. When congruence (3.2)
is multiplied by t, we obtain
x ≡ t(dr − bs) (mod n)
A value for y is found by a similar elimination process. That is multiply the
first congruence of the system by c, the second one by a, and subtract to end
up with
(ad − bc)y ≡ as − cr (mod n) (3.3)
multiplication of this congruence by t leads to
y ≡ t(as − cr) (mod n)
A solution of the system is now established.
Example 3.18. Consider the system
7x + 3y ≡ 10 (mod 16)
2x + 5y ≡ 9 (mod 16)
Because gcd(7.5 − 2.3, 16) = gcd(29, 16) = 1, a solution exists. Multiplying
the first congruence by 5, the second one by 3, and subtracting, we arrive at

c 2018 Biruk G. AMU

Number Theory Lecture Note 66

29x ≡ (5.10 − 3.9) ≡ 23 (mod 16)

or

13x ≡ 7 (mod 16)

Multiplication of this congruence by 5(noting that 5.13 ≡ 1 (mod 16)) pro-

duces x ≡ 35 ≡ 3 (mod 16). When variable x is eliminated from the system
of congruences in a like manner, it is found that

29y ≡ 7.9 − 2.10 ≡ 43 (mod 16)

But then 13y ≡ 11 (mod 16), which upon multiplication by 5, results in

y ≡ 55 ≡ 7 (mod 16). The unique solution of our system turns out to be

x ≡ 3 (mod 16) y ≡ 7 (mod 16).

c 2018 Biruk G. AMU

Chapter 4

Euler-Fermat Theorem

4.1 The Notion of Complete System of Residues

Definition 4.1. Let m ∈ Z. a ≡ b (mod m) if and only if a − b = mq for
some integer q ∈ Z. in this case b is called a residue of a modulo m.

Theorem 4.1. If m is an integer, then the relation

Rm = {(a, b) | a ≡ b (mod m), a, b ∈ Z

is an equivalence relation on Z. 

We are usually interested when m ≥ 1. The equivalence relation Rm par-

titions Z in to equivalence classes. Let us denote [x] as the equivalence class
containing x, and then there are m distinct equivalence classes.

Given any integer a, by Division Algorithm we can write a as

a = mq + r with unique q, r ∈ Z and 0 ≤ r ≤ m − 1

Hence a ∈ [r] for some r = 0, 1, 2, ..., m − 1

Thus there are m equivalence classes namely

[0] = {mx | x ∈ Z}
[1] = {1 + mx | x ∈ Z}
..
.
[m − 1] = {(m − 1) + mx | x ∈ Z}

67
Number Theory Lecture Note 68

Definition 4.2. A subset S of the set of integers is called a complete system

of residues modulo m if and only if for any integer b there exists r ∈ S such
that b ≡ r (mod m) and any two elements of S are incongruent modulo m.

{a, a + 1, a + 2, ..., a + m − 1} is complete set of residue classes modulo m

for any a ∈ Z.

In particular, for a = 0, {0, 1, 2, ..., m − 1} is the minimal nonnegative

complete set of residue classes.

Example 4.1. Consider the set S = {0, 1, 2, ..., m−1. Since for every integer
b there exists r ∈ S such that b = mq + r(by Division Algorithm) we see that
b ≡ r (mod m). Hence S is a complete system of residue class representatives
modulo m. In fact S is the least complete residue class representatives modulo
m.

Notation: The set of equivalent classes modulo m, {[0], [1], [2], ..., [m−1]},
is denoted by Zm or Z/mZ.

4.2 Euler-quotient Function, φ(m)

Theorem 4.2. [a] in Zm is invertible if and only if gcd(a, m) = 1.

Proof:(⇐) If gcd(a, m) = 1, then there exists x and y such that

ax + my = 1.

It follows that

[1] = [ax + my]

= [ax] + [my]
= [a][x](because [my] = [0])

(⇒) exercise. 

We note that a is coprime to m if and only if every element in the residue

class [a] is coprime to m. Thus we can speak of a residue class being coprime
to m.

Remark: The number of residue classes relatively prime to m or, equivalently,

the number of integers between 1 and m(inclusive) which are relatively prime

c 2018 Biruk G. AMU

Number Theory Lecture Note 69

to m is denoted by φ(m). (Let Z∗m denote the set of invertible elements of

the ring Zm . The number of elements of Z∗m is denoted by φ(m)).

The function φ(m) is called the Euler Phi function. The list of numbers
between 1 and m which are coprime to m or, more generally, any list of φ(m)
incongruent integers which are coprime to m, is called a reduced residue
system modulo m.

Example 4.2. (a) For m = 12: Complete = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
and Reduced = {1, 5, 7, 11}.

(b) Consider the modulus m = 15. Integers between 1 and 15 which are
coprime to 15: 1,2,4,7,8,11,13,14. Thus φ(15) = 8 and the above eight
integers form a reduced residue system modulo 15.

(c) Consider any prime p. All the numbers 1,2, ...,p-1 are coprime to p;
hence φ(p) = p − 1.

A function f with domain the positive integer N is said to be multiplicative

if, whenever a and b are relatively prime,

f (ab) = f (a)f (b)

Theorem 4.3. Euler’s phi function multiplicative. That is, if a and b are
relatively prime, then

φ(ab) = φ(a).φ(b)

Proof: exercise. 

Example 4.3. φ(4.5) = φ(20) = 8 and φ(4).φ(5) = 2.4 = 8.

Recall: φ(m) is the number of elements in Z∗m , it is the number of natural

numbers less than m and relatively prime to m.

In this section we will develop a technique that will enable us to obtain

φ(m) from the prime factorization of m.

Definition 4.3. A subset T of integers is called a complete reduced residue

system modulo m if and only if

i) no two elements of T are congruent (mod m)

c 2018 Biruk G. AMU

Number Theory Lecture Note 70

ii) for every integer b relatively prime to m, there exists r ∈ T such that
b ≡ r (mod m)

iii) every element of T is relatively prime to m.

Example 4.4. The set T = {1, 2, 4, 5, 7, 8} is a complete reduced residue
system (mod 9).

In general, if L is the set of natural numbers less than m and relatively prime
to m, then it is easy to see that L forms a complete least reduced residue
system (mod m). Notice that | L |= φ(m).
Theorem 4.4. Let m be a natural number greater than 1. T is a complete
reduced residue system (mod m) if and only if T contains φ(m) elements,
each relatively prime to m and are congruenct (mod m).

Proof: exercise. 
Corollary 4.1. If T = {r1 , r2 , · · · , rφ(m) } is a complete reduced system
(mod m) and gcd(a,m) = 1, then S = {ar1 , ar2 , · · · , arφ(m) } is also a com-
plete reduced residue system (mod m).
m
Proof: ari ≡ arj (mod m) if and only if ri ≡ rj (mod ) where
d
d = gcd(a,m).

Thus if gcd(a,m) = 1, then no two elements of S are congruent (mod m).

Evidently for each i = 1, 2, · · · , φ(m) ari is relatively prime to m and pairwise
incongruent (mod m). 
Theorem 4.5. If p is prime and n is a natural number, then
φ(pn ) = pn−1 (p − 1)
Proof: The number of natural numbers less than pn is pn−1 . Among these,
those that are not relatively prime to pn are multiples of p and they are of
the form kp for k = 1,2,3, · · · , pn−1 − 1.

Thus the number of natural numbers less than pn and relatively prime to
n
p are
pn − 1 − (pn−1 − 1) = pn−1 (p − 1).
∴ φ(pn ) = pn−1 (p − 1). 

c 2018 Biruk G. AMU

Number Theory Lecture Note 71

Corollary 4.2. p1 , p2 , · · · , pn are the distinct prime factors of the natural

number m, then
Qn 1 1 1 1
φ(m) = m i=1 (1 − ) = m(1 − )(1 − ) · · · (1 − ).
pi p1 p2 pn
Proof: Let m = pα1 1 .pα2 2 · · · pαnn be the prime factorization of m.

φ(m) = φ(pα1 1 )φ(pα2 2 ) · · · φ(pαnn ).

using the above theorem, we get that

φ(m) = pα1 1 −1 (p1 − 1).pα2 2 −1 (p2 − 1) · · · pαnn −1 (pn − 1)

n
Y 1
= m (1 − )
i=1
pi

Example 4.5. Calculate the value φ(360):

The Prime power decomposition of 360 is 23 .32 .51 .

1 1 1
φ(360) = 360(1 − )(1 − )(1 − )
2 3 5
1 2 4
= 360. . .
2 3 5
= 96.

Theorem 4.6. For n > 2, φ(n) is an even integer.

Proof: First, assume that n is a power of 2, let us say that n = 2k , with

k ≥ 2.
1
φ(n) = φ(2k ) = 2k (1 − ) = 2k−1 (an even integer)
2
If n does not happen to be a power of 2, then it is divisible by an odd
prime p. We may write n as n = pk m, where k ≥ and gcd(pk , m) = 1.

φ(n) = φ(pk )φ(m) = pk−1 (p − 1)φ(m).

which again is even because 2 | p − 1. 

c 2018 Biruk G. AMU

Number Theory Lecture Note 72

4.3 Euler-Fermat Theorem

Theorem 4.7. Fermat’s Theorem: Let p be a prime and suppose that
p - a. Then

ap−1 ≡ 1 (mod p)

Proof: Consider the first p − 1 positive multiples of a; that is, the integers
a, 2a, 3a, · · · , (p − 1)a. None of these numbers is congruent modulo p to any
other, nor is any congruent to zero. Indeed, if it happened that

ra ≡ sa (mod p) 1≤r <s≤p−1

then a could be canceled to give r ≡ s (mod p), which is impossible. Therefore

the previous set of integers must be congruent modulo p to 1,2,3, · · · ,p − 1,
taken in some order. Multiplying all these congruences together, we find that

a.2a.3a. · · · (p − 1)a ≡ 1.2.3 · · · (p − 1) (mod p).

whence

ap−1 (p − 1)! ≡ (p − 1)! (mod p)

⇒ ap−1 ≡ 1 (mod p) 

Example 4.6. Let a = 57 and b = 29: 5728 ≡ 1 (mod 29).

Corollary 4.3. If p is a prime, then ap ≡ a (mod p) for any integer a.

Proof: When p | a, then ap ≡ 0 ≡ a (mod p)

If p - a, then according to Fermat’s theorem, we have ap−1 ≡ 1 (mod p).

Multiplying both sides of the congruence by a, we get

ap ≡ a (mod p)

∗ Some applications of Fermat’s Theorem:

1. To verify a given congruence holds.

c 2018 Biruk G. AMU

Number Theory Lecture Note 73

Example 4.7. Verify that 538 ≡ 4 (mod 11).

510 ≡ 1 (mod 11) · · · Fermat’s Theorem.

538 = 510.3+8 = (510 )3 .(52 )4

≡ 13 .34
≡ 81 (mod 11)
≡ 4 (mod 11)

2. To test the primality of a given integer n.

If it could be shown that the congruence

an ≡ a (mod n)

fails to hold for some choice of a, then n is necessarily composite.

Example 4.8. When n = 117, let a = 2.

2117 = 27.16+5 = (27 )16 .25

≡ 1116 .25 (i.e27 = 128 ≡ 11 (mod 117))
≡ (121)8 .25
≡ 48 .25
≡ 221 (mod 117)
≡ (27 )3 (mod 117)
≡ 113 (mod 117)
≡ 121.11 (mod 117)
≡ 4.11 (mod 117)
≡ 44 (mod 117)

Combining these congruences, we finally obtain

2117 ≡ 44 6≡ 2 (mod 117)

so that 117 must be composite; actually 117 = 13.9

c 2018 Biruk G. AMU

Number Theory Lecture Note 74

∗ The converse of Fermat’s Theorem may not hold:

i.e if an−1 ≡ 1 (mod n) for some integer a, then n need not be prime.
Lemma 4.1. If p and q are distinct primes with ap ≡ a (mod q) and aq ≡ a
(mod p), then apq ≡ a (mod pq).

Proof: (aq )p ≡ aq (mod p) → (from the above corollary), whereas aq ≡ a

(mod p) → (by hypothesis).

Combining these congruences, we obtain apq ≡ a (mod p) or in different

terms, p | apq − a. Similarly q | apq − a.

∴ pq | apq − a ⇒ apq ≡ a (mod pq). 

Example 4.9. 2340 ≡ 1 (mod 341), where 341 = 11.31

210 = 1024 = 31.33 + 1. Thus, 211 = 2.210 ≡ 2.1 ≡ 2 (mod 31) and
2 = 2(210 )3 ≡ 2.13 ≡ 2 (mod 11).
31

Exploiting the lemma, 211.31 ≡ 2 (mod 11.31) or 2341 ≡ 2 (mod 341).

After canceling a factor of 2,

2340 ≡ 1 (mod 341)
So that the converse to Fermat’s theorem is false.
Theorem 4.8. Euler-Fermat’s Theorem: If m is a positive integer and
gcd(a,m) = 1, then
aφ(m) ≡ 1 (mod m)
Proof: Let {r1 , r2 , · · · , rφ(m) } be the complete residue system (mod m). Then
{ar1 , ar2 , · · · , arφ(m) } is also complete residue system (mod m). Thus ari
is congruent (mod m) to one and only one elements of {r1 , r2 , · · · , rφ(m) }.
Hence
(ar1 )(ar2 ) · · · (arφ(m) ) ≡ r1 r2 · · · rφ(m) (mod m)
But gcd(r1 r2 · · · rφ(m) , m) = 1. It then follows that m is a factor of aφ(m) − 1
and thus
aφ(m) ≡ 1 (mod m)

c 2018 Biruk G. AMU

Number Theory Lecture Note 75


Example 4.10. Find the remainder of 3164 divided by 68.

Solution: gcd(3,68) = 1 and we are looking for a natural number r less

than 68 such that
3164 ≡ r (mod 68)
Since φ(68) = φ(4 × 17) = φ(4)φ(17) = 2 × 16 = 32, We divide 164 by 32 to
get 164 = 5×32 + 4.
Then

332 ≡ 1 (mod 68)

3164 ≡ (332 )5 .34 (mod 68)
≡ 15 .81 (mod 68)
≡ 13 (mod 68)

That is, 13 the remainder of 3164 by 68.

4.4 Congruences of Higher Order

4.4.1 Application of The Euler-Fermat Theorem
The Euler-Fermat Theorem can also used to solve higher order congruence
f (x) ≡ 0 (mod m)
This is usually done by reducing the congruence to one of lower degree.
Example 4.11. Find the complete solution of the congruence
f (x) = 9x17 + 3x10 + 3x9 − 2x2 + 2 ≡ 0 (mod 15)
Solution: Evidently if x is a solution of the congruence, then gcd(x,15) = 1.

But then φ(15) = φ(3)φ(5) = 2 × 4 = 8, and we have

xφ(15) = x8 ≡ 1 (mod 15)
It follows that 9x17 = 9x(x8 )2 ≡ 9x (mod 15), 3x10 = 3(x2 x8 ) ≡ 3x2
(mod 15), 3x9 = (3x)x8 ≡ 3x (mod 15)

Consequently solving for f (x) ≡ 0 (mod 15) is equivalent to solving for

c 2018 Biruk G. AMU

Number Theory Lecture Note 76

x2 + 12x + 2 ≡ 0 (mod 15)

But x2 + 12x + 2 ≡ x2 + 12x + 32 ≡ 0 (mod 15)(since 32 ≡ 2 (mod 15))

Thus it is equivalent to solving the congruence

(x + 4)(x + 8) = x2 + 12x + 32 ≡ 0 (mod 15)

We finally obtain x ≡ 1, x ≡ 2, x ≡ 7, and x ≡ 11 (mod 15) as solutions of

the congruence.

For a polynomial f (x) with integer coefficients, we shall in the future

subsections develop some techniques that could help to solve the congruence
f (x) ≡ 0 (mod m). Evidently x0 is a solution of the congruence if and only
if for every integer r that is congruent to x0 (mod m), r is also a solution
of the congruence f (x) ≡ 0 (mod m). In view of this it suffice to find the
solution of f (x) ≡ 0 (mod m) from {0, 1, 2, · · · , m − 1}, the complete least
residue system (mod m).

Besides if m = m1 m2 · · · mn are pairwise relatively prime natural num-

bers, then it is easy to see that x0 is a solution of f (x) ≡ 0 (mod m) if and
only if for every i = 1,2,3,...,n it is a solution of f (x) ≡ 0 (mod mi ).

Consequently, solving for f (x) ≡ 0 (mod m) is equivalent to solving the

system f (x) ≡ 0 (mod mi ) for i = 1, 2, · · · , n. One way of solving the system
is to solve each congruence separately and then apply the Chinese Remainder
theorem to obtain a solution to the system.

4.4.2 Polynomial Congruences

Consider the polynomial congruence f (x) ≡ 0 (mod m) where

f (x) = an xn + an−1 xn−1 + · · · a1 x + a0

has integer coefficients ai , i = 0, 1, · · · , n.

To solve: first stage of the process is to consider the prime factorization

of m: say that m = pe11 pe22 · · · pekk .

c 2018 Biruk G. AMU

Number Theory Lecture Note 77

Then observe that, by the CRT(Chinese Remainder Theorem), solving

f (x) ≡ 0 (mod m) is equivalent to solving the system of congruence

f (x) ≡ 0 (mod pe11 )

f (x) ≡ 0 (mod pe22 )
..
.
f (x) ≡ 0 (mod pekk )

That is, by means of the CRT, we can reduce our problem to the case where
the modulus is a prime power.

The second stage of the process, then, is to deal with polynomial congru-
ences of the form f (x) ≡ 0 (mod pe ) where p is prime. For this we use a
powerful result, known as the Lifting Theorem.
Theorem 4.9. The Lifting Theorem: Suppose x ≡ a (mod pe ) is a so-
lution to the polynomial congruence f (x) ≡ 0 (mod pe ). Then, where f 0 (x)
is the derivative of the polynomial, this solution lifts to a solution to the con-
gruence f (x) ≡ 0 (mod pe+1 ) depending on whether p | f 0 (a) and pe+1 | f (a):

0
Case 1: If p - f (a), then f (x) ≡ 0 (mod pe+1 ) has the unique solution x ≡
a + pe t (mod pe+1 ) , where t is the unique solution to the linear congruence
f (a)
f 0 (a)t ≡ − (mod p);
pe
Case 2: If p | f 0 (a) and pe+1 | f ( a), then f (x) ≡ 0 (mod pe+1 ) has p distinct
solutions of the form x ≡ a + pe t (mod pe+1 ) where t = 0, 1 · · · , p − 1.

Case 3: If p | f 0 (a) but pe+1 - f ( a), then f (x) ≡ 0 (mod pe+1 ) has no solu-
tions which reduce to a mod pe .

Proof: exercise. (Desktop-NT-congruences-polycongruences)

Example 4.12. Solve x3 + 3x2 − 4 ≡ 0 (mod 175).

Solution: As 175 = 7.52 , the given congruence is equivalent to the system

x3 + 3x2 − 4 ≡ 0 (mod 7)
x3 + 3x2 − 4 ≡ 0 (mod 52 )

c 2018 Biruk G. AMU

Number Theory Lecture Note 78

To solve the first congruence, we test the values x ≡ 0, 1, 2, 3, 4, 5, 6 (mod 7);

we then find x ≡ 1, 5 (mod 7) are the two solutions.

To solve the second congruence, we first tackle x3 + 3x2 − 4 ≡ 0 (mod 5).

Again we simply test the values x ≡ 0, 1, 2, 3, 4 (mod 5) to find that x ≡ 1, 3
(mod 5) are the two solutions. Next we proceed to lift each of these so-
lutions to a solution mod 52 (nothing that if f (x) = x3 + 3x2 − 4, then
f 0 (x) = 3x2 + 6x):

In the case of x ≡ 1 (mod 5), we have f (1) = 0, f 0 (1) = 9; as 5 - f 0 (1),

f (1)
we can lift to a unique solutions by solving f 0 (1)t ≡ − (mod 5), or
5
9t ≡ 0 (mod 5).

Clearly, t ≡ 0 (mod 5), leading to the solution x ≡ 1 + 5.0 ≡ 1 (mod 52 ).

In case of x ≡ 3 (mod 5), we have f (3) = 50, f 0 (3) = 45; as 5 | f 0 (3)

and 52 | f (3), we can lift to 5 distinct solutions x ≡ 3, 8, 13, 18, 23 (mod 52 ).

Consequently, we have two solutions x ≡ 1, 5 (mod 7) that can each pair

with six solutions x ≡ 1, 3, 8, 13, 18, 23 (mod 52 ) to yield 12 possible solutions
mod 175, each computed via the CRT.

x ≡ 1 (mod 7) x ≡ 5 (mod 7)
x≡1 (mod 25) x ≡ 1.7.18 + 1.25.2 ≡ 1 x ≡ 1.7.18 + 5.25.2 ≡ 26
x≡3 (mod 25) x ≡ 3.7.18 + 1.25.2 ≡ 78 x ≡ 3.7.18 + 5.25.2 ≡ 103
x≡8 (mod 25) x ≡ 8.7.18 + 1.25.2 ≡ 8 x ≡ 8.7.18 + 5.25.2 ≡ 33
x ≡ 13 (mod 25) x ≡ 13.7.18 + 1.25.2 ≡ 113 x ≡ 13.7.18 + 5.25.2 ≡ 138
x ≡ 18 (mod 25) x ≡ 18.7.18 + 1.25.2 ≡ 43 x ≡ 18.7.18 + 5.25.2 ≡ 68
x ≡ 23 (mod 25) x ≡ 23.7.18 + 1.25.2 ≡ 148 x ≡ 23.7.18 + 5.25.2 ≡ 173
Note: The inverse of 7 mod 25 is 18 and the inverse of 25 mod 7 is 2.
Example 4.13. Find the complete solution of f (x) ≡ 0 (mod 200) where
f (x) = x3 − x2 + 7x + 1
Solution: Since 200 = 8×25 = 23 .52 solving the congruence f (x) ≡ 0 (mod 200)
is equivalent to solving the system
f (x) ≡ 0 (mod 8)
f (x) ≡ 0 (mod 25)
We first solve each of the sub congruence above. Since 1 is the only solution
of

c 2018 Biruk G. AMU

Number Theory Lecture Note 79

f (x) ≡ 0 (mod 2)
a solution of f (x) ≡ 0 (mod 4) is of the form 1 + 2t where t is a solution of
f (1)
+ f 0 (1)t ≡ 0 (mod 2)
2
f (1) f (1)
{N ote : + f 0 (1)t ≡ 0 (mod 2) ⇒ f 0 (1)t ≡ − (mod 2)}
2 2
But f (1) = 8 and f 0 (1) = 8. Hence 0 and 1 are possible choices for t.

Thus 1 + 2t = 1 or 3 are solutions of f (x) ≡ 0 (mod 4).

Case 1: Suppose we choose b = 1 as a solution of f (x) ≡ 0 (mod 4).

Then we set x0 = 1 + 4t , where t is a solution of the congruence
f (1)
+ f 0 (1)t ≡ 0 (mod 2).
4
We notice that t = 0 and t = 1 are also possible choices for t.

Hence x0 = 1, 1 + 22 = 5 are solutions of f (x) ≡ 0 (mod 8).

Case 2: Suppose we choose b = 3 as a solution of f (x) ≡ 0 (mod 4).

Then x0 = 3 + 4t with t a solution of
f (3)
+ f 0 (3)t ≡ 0 (mod 2).
4
is a solution of f (x) ≡ 0 (mod 8).

But f (3) = 40 and f 0 (3) = 28. Thus, again, t = 0 and t = 1 are also
possible solutions of the congruence f (x) ≡ 0 (mod 8).

The we conclude that 1, 3, 5 and 7 are the solution of f (x) ≡ 0 (mod 8)

in the complete least residue system (mod 8). Of course, these could have
been obtained by direct substitution.

With regard to the congruence f (x) ≡ 0 (mod 25), we first solve

f (x) ≡ 0 (mod 5).
By substitution, 3 is the only solution of the complete least residue system
(mod 5). Then x0 = 3+5t is a solution of the congruence f (x) ≡ 0 (mod 25)
where t is a solution of the congruence

c 2018 Biruk G. AMU

Number Theory Lecture Note 80

f (3)
+ f 0 (3)t ≡ 0 (mod 5).
5
But f (3) = 40 and f 0 (3) = 28. Hence t is a solution of 28t + 8 ≡ 0 (mod 5).

We notice that t = 4 is the solution of the linear congruence in the com-

plete least residue system (mod 5).

Hence 23 is the only solution of f (x) ≡ 0 (mod 25) in the complete least
residue system (mod 25).

Finally we solve each of the system of congruences

(
x ≡ 1 (mod 8)
x ≡ 23 (mod 25)
(
x ≡ 3 (mod 8)
x ≡ 23 (mod 25)
(
x ≡ 5 (mod 8)
x ≡ 23 (mod 25)
(
x ≡ 7 (mod 8)
x ≡ 23 (mod 25)
Since gcd(8, 25) = 1, each system has a solution and we find that 73, 123,
173 and 23 are the respective solutions of the system in the complete least
residue system (mod 200).

Note: If the degree of the polynomial is greater that the modulus, the fol-
lowing theorem is quite helpful.
Theorem 4.10. If p is a prime and deg f = n ≥ p, then there exists a poly-
nomial r(x) with degree less than p such that x0 is a solution of f (x) ≡ 0
(mod p) if and only if it is a solution of r(x) ≡ 0 (mod p).

Proof: By long division, let f (x) = (xp − x)q(x) + r(x) with deg r(x)≤
p-1 or r(x) = 0. By Fermat’s Little Theorem, for every x = 0,1,2,· · · ,p-1,
xp ≡ x (mod p).
Hence x0 is a solution of f (x) ≡ 0 (mod p) if and only is it is a solution of
r(x) ≡ 0 (mod p). This completes the proof. 

c 2018 Biruk G. AMU

Number Theory Lecture Note 81

Example 4.14. Solve f (x) ≡ 0 (mod 25) where

f (x) = x9 + 2x6 − x5 − x2 + 4x
Solution: We first solve the congruence f (x) ≡ 0 (mod 5).

Since x5 ≡ x (mod 5), solving f (x) ≡ 0 (mod 5) is equivalent to solving

x + 2x2 − x − x2 + 4x ≡ 0 (mod 5).

i.e x2 + 4x ≡ 0 (mod 5).

Hence 0 and 1 are the solutions of f (x) ≡ 0 (mod 5).

Now, using b = 0, we observe that x0 = 5t is a solution of f (x) ≡ 0

(mod 25) where t is a solution of
f (0)
+ f 0 (0)t ≡ 0 (mod 5)
5
But f (0) = 0 and f 0 (0) = 4. Hence t = 0 is the solution in {0, 1, 2, 3, 4} .
Hence 0 is a solution of the congruence f (x) ≡ 0 (mod 25).

And, using b = 1, we observe that x0 = 1 + 5t is a solution of f (x) ≡ 0

(mod 25) where t a solution of
f (1)
+ f 0 (1)t ≡ 0 (mod 5)
5
But f (1) = 5 and f 0 (1) = 18. Hence t = 3 is the solution of the linear
congruence
1 + 3t ≡ 0 (mod 5).
It follows that 1 + 3(5) = 16 is a solution of f (x) ≡ 0 (mod 25).

We, then conclude that 0 and 16 are the solutions of f (x) ≡ 0 (mod 25)
in the complete least residue system (mod 25).
Theorem 4.11. Factor Theorem: b is a solution of the congruence
f (x) ≡ 0 (mod m)
if and only if f (x) ≡ (x − b)g(x) (mod m) for some polynomial g(x) with
integer coefficients and deg. g(x) < deg. f(x).

Proof: By long division, we have

c 2018 Biruk G. AMU

Number Theory Lecture Note 82

f(x) = (x-b)g(x) + r(x),

with integer coefficients; deg. g(x) = deg. f(x) - 1 and r(x) is constant.

b is a solution of f (x) ≡ 0 (mod m) if and only if

f (b) = (b − b)g(b) + r(b) ≡ 0 (mod m)

if and only if f (x) ≡ (x − b)g(x) (mod m).

c 2018 Biruk G. AMU

Chapter 5

Decimal Expansion of Rational

Numbers

5.1 Decimal Representation

Suppose m and g are positive integers with g ≥ 2. Then a successive applica-
tion of the division algorithm guarantees that there exists a unique integers
a0 , a1 , · · · , an with 0 ≤ a0 < g and an 6= 0 such that
m = an g n + an−1 g n−1 + · · · + a1 g + a0 (∗)
The integers an , an−1 , . . . , a1 , a0 are called the digits of m in base g and (∗)
is usually abbreviated by
m = (an an−1 · · · a1 a0 )g (∗∗)
The expression in (∗∗) is called the representation of m in base g.

If m is negative integer, then −m = (an an−1 · · · a1 a0 )g and we define the

representation of the negative integer m in base g by
m = −(an an−1 · · · a1 a0 )g
Conclusion: Every integer has a unique representation in base g.
Definition 5.1. Suppose α is any real number. The unique integer n such
that n ≤ α < n + 1 is called the integer part of α and it is denoted by [α].

Note: α = [α] +  for some , 0 ≤  < 1.

Evidently, there exists a unique non-negative integer a1 < g such that

83
Number Theory Lecture Note 84

a1 a1 + 1
≤< .
g g
Again, there exists a unique non-negative integer a2 < g such that
a2 a1 a2 + 1
≤  − < .
g2 g g2
Suppose we have obtained an−1 . Then there exist a unique non-negative
integer an < g such that
an a1 a2 an−1 an + 1
n
≤− − 2 − · · · − n−1 < .
g g g g gn
For each natural number n, let
Pn ai
qn = [α] + i=1
gi
an+1 + 1 1 Pn ai
Then 0 ≤ α − qn < < . It follows that the series [α] + i=1 i
g n+1 gn g
converges to α.
ai − P ai
n−→
−−→
∞ α or [α] + ∞
Pn
That is [α] + i=1 i=1 i = α.
gi g

Now assume that α > 0. If [α] = bm g m + bm−1 g m−1 · · · + b1 g + b0 , then

P ai
[α] + ∞ i=1 i is often abbreviated by (bm bm−1 · · · b1 b0 .a1 a2 · · · )g and is called
g
the decimal representation of α in base g.
Theorem 5.1. Let g be any positive integer greater than 1. If α is any posi-
tive real number, then there exists unique non-negative integers bm , bm−1 . . . , b1 , b0 , a1 , a2 , . . .
each less than g, such that
α = (bm bm−1 · · · b1 b0 .a1 a2 · · · )g
where (bm bm−1 · · · b1 b0 )g is the representation of [α] in base g.

Proof: ex. 
The representation of any real number in base 10 is simply called the dec-
imal representation(expansion)of the real number while its representation in
base two is called its binary representation.

In the decimal representation of a real number, i.e. representation in the

base ten, usually not explicitly indicated. Thus −(234)ten and (25.324)t en
are by convention simply written as -234 and 25.324 respectively.

c 2018 Biruk G. AMU

Number Theory Lecture Note 85

Example 5.1. Find the representation of 36.47 in base five.

Solution: Since the integer part of 36.47 is 36 let us first represent the
base five representation of 36.

36 = 7 × 5 + 1
7=1×5+2
1=0×5+1

Thus the representation in base five is the list of the remainders in reverse
order i.e 36 = (121)f ive .

Next find the representation of 0.47 in base five.

a1 a2 an
0.47 = (0.a1 a2 · · · )f ive ⇔ 0.47 = + 2 +· · · n +· · · (∗)
5 5 5
with non-negative integers ai each less than five.

Then multiplying (∗) by five on both sides we get

a2 a3 an
5(0.47) = a1 + + 2 + · · · n−1 + · · ·
5 5 5
a2 a3 an
⇒ 2.35 = a1 + + 2 + · · · n−1 + · · ·
5 5 5
a2 a3 an
Thus a1 = 2 and 0.35 = + 2 + · · · n−1 + · · ·
5 5 5
Again multiplying both sides of the last equation we get
a3 a4 an
1.75 = a2 + + 2 + · · · n−2 + · · ·
5 5 5
a3 a4 an
Thus a2 = 1 and 0.75 = + 2 + · · · n−2 + · · ·
5 5 5
Similarly from
a4 a5 an
3.75 = 5(0.75) = a3 ++ 2 + · · · n−3 + · · ·
5 5 5
a4 a5 an
we obtain a3 = 3 and 0.75 = + 2 + · · · n−3 + · · ·
5 5 5
a5 a6 an
Again from 3.75 = 5(0.75) = a4 + + 2 + · · · n−4 + · · · , we obtain
5 5 5
a4 = 3 and

c 2018 Biruk G. AMU

Number Theory Lecture Note 86

a5 a6 an
0.75 = + 2 + · · · n−4 + · · ·
5 5 5
⇒ ai = 3 ∀i ≥ 3. Thus 0.47 = (0.213)5 .

∴ 36.47 = (121.213)f ive .

Example 5.2.√ Find the first digits, after the decimal, of the decimal repre-
sentation of 2.
√
Solution: Evidently 2 = 1.a1 a2 · · · with non-negative integers ai , each
less than ten.
√ a2 a3
But, then ( 2 − 1)10 = a1 + + 2 + · · · gives that
10 10
√ a2 a3
10 2 = 10 + a1 + + 2 + ···
10 10
a2 a3
But, since + 2 + · · · < 1, we see that
10 10
√ a2 a3
10 2 = 10 + a1 + + 2 + · · · < a1 + 11
10 10
Thus we choose a1 ∈ {0, 1, 2, . . . , 9} such that
√
(a1 + 10)2 ≤ (10 2)2 < (a1 + 11)2 ⇔ (a1 + 10)2 ≤ 200 < (a1 + 11)2

Since (14)2 = 196 < 200 < 225 = (15)2 , we notice that a1 = 4.

Substituting the value a1 = 4 we get the relation

√ a2 a3
10 2 = 10 + 4 + + 2 + ···
10 10
√ a2 a3
⇔ (10 2 − 14) = + 2 + ···
10 10
Multiplying both sides we get
√ a3 a4
10(10 2 − 14) = a2 + + 2 + ···
10 10
√ a3 a4
⇔ 100 2 = 140 + a2 + + + ···
10 102
a3 a4
But, since + 2 + · · · < 1, we obtain that
10 10
√ a3 a4
100 2 = 140 + a2 + + 2 + · · · < a2 + 141
10 10
c 2018 Biruk G. AMU
Number Theory Lecture Note 87

Hence we choose a2 ∈ {0, 1, 2 . . . , 9} such that

√
(a2 + 140)2 ≤ (100 2)2 < (a2 + 141)2

⇒ a2 = 1

Again using a2 = 1 and the fact that

√ a4 a5
10(100 2 − 141) = a3 + + 2 + ···
10 10
we choose a3 ∈ {0, 1, 2, . . . , 9} such that
√
(a3 + 1410)2 ≤ (1000 2)2 < (a3 + 1411)2

By considering the possibilities we get a3 = 4.

Using the above algorithm, one can proceed further to determine the conse-
quent digits and see that
√
2 = 1.4142135a8 a9 · · ·

5.2 Types of Decimal Representations

The set of real numbers, R, is nothing but the set of decimal representations
in base g.

Definition 5.2. Let g be any natural number greater than one. Then

D = {α|α = 0 or |α| = (bm bm−1 · · · b1 b0 .a1 a2 · · · )g where bi and aj are

non-negative less than g}

is called the set of all decimal representations in base g.

Consequently D = R. If g = ten, D is simply called the set of decimal

while if g = two, it is called the set of all binary representations(decimals).

Definition 5.3. Consider a decimal representation

(bm bm−1 · · · b1 b0 .a1 a2 · · · )g

(1) The representation is called a terminating representation if and

only if there exists an integer k such that ai = 0 for i > k. The
smallest non-negative k such that ai = 0 for i > k is called the length
of the decimal representation in base g.

c 2018 Biruk G. AMU

Number Theory Lecture Note 88

(2) The representation is called(an eventually) periodic or repeating dec-

imal representation if and only if there exist integer k and t such that
for each i ≥ k, ai+t = ai . The smallest such t is called the length of
the period.

Periodic decimals are frequently denoted by

(bm bm−1 · · · b1 b0 .a1 a2 · · · ak−1 ak ak+1 · · · ak+t−1 )g

(3) The representation is called non-terminating and non-periodic if

and only if it is neither terminating nor periodic.

5.3 Characterizing The Rational Using

Decimal Representation
In this section, we concentrate on terminating or periodic decimals i.e in
base ten numeration. The result to be obtained can easily be modified to
give corresponding result with respect to any base g, g shall be assumed to
be a natural number greater than one.
a
If is positive rational number, then a = bq + r with unique integer
b
r
q and r, 0 ≤ r < b. Thus the decimal representation of q and . As the
b
decimal representation of q can be obtained by successive division by ten, it
r
suffices to find the decimal representation of . Hence we shall only discuss
b
m
the decimal expansion of relatively prime positive integers with m < n.
n
Theorem 5.2. Assume then m and n are relatively prime natural numbers
m
with 1 ≤ m < n. The decimal expansion of terminating if and only if n
n
α β
is of the form 2 5 , with non-negative integers α and β.

Proof: ex.  NT-2008-159.

Theorem 5.3. Generalization Theorem(of Theorem 5.2) Assume that

1 ≤ m < n, m and n are relatively prime integers. The rational number
m
n
has a terminating decimal representation in base g if and only if

c 2018 Biruk G. AMU

Number Theory Lecture Note 89

n = pα1 1 pα2 2 · · · pαk k

with non-negative integer α1 , α2 , . . . , αk , and primes p1 , p2 , . . . , pk each divid-

m
ing g, then the length of the decimal expansion of in base g is equal to the
n
maximum of α1 , α2 , . . . , αk . 

Theorem 5.4. Let m and n be relatively prime natural numbers with 1 ≤

m
m < n. And n is not of the form 2α 5β . Then has a non-terminating but
n
periodic decimal representation.

Proof: ex. 
13
Example 5.3. Decide whether is a terminating or periodic decimal.
17
Solution: 17 6= 2α 5β for any α and β, and 13 and 17 relatively prime
numbers.
13
Hence we conclude that is a non-terminating but periodic decimal.
17
Definition 5.4. A non-terminating periodic decimal bn bn−1 · · · b1 .a1 a2 a3 · · ·
is called a purely periodic decimal if the period begins at a1 .

Example 5.4. 423.4322, 10.4113 and 0.021 are not purely periodic decimals.

Where as 12.3, 101.011, and 0.156 are purely periodic decimals.

Definition 5.5. Suppose g is an integer relatively prime to the natural num-

ber m. The smallest positive integer n such that g n ≡ 1 (mod m) is called
the order(exponent) of g modulo m. We also say that g belongs to the
exponent n (mod m) and n is often denoted by Ordm (g) or simply θ(g).

∗ Note: Ordm (g) = n ≤ φ(m) and Ordm (g) = n is a divisor of φ(m).

Example 5.5. Find the order of 13 in Z29

Solution:
Ord29 (13) = θ(13)|φ(29) ⇔ θ(13)|28.

⇒ θ(13) = 1, or θ(13) = 2, or θ(13) = 4, or θ(13) = 7, or θ(13) = 14 or

θ(13) = 28.

∴ θ(13) = Ord29 (13) = 14. (because 1314 ≡ 1 (mod 29)).

c 2018 Biruk G. AMU

Number Theory Lecture Note 90

Theorem 5.5. If 1 ≤ m < n and m and n are relatively prime natural with
m
gcd(10m,n)=1, then the decimal expansion of is purely periodic and the
n
length of the period is equal to Ordn (10).

Proof: ex  (Num-2008-160)

13
Example 5.6. Find the decimal representation of .
17
13
Solution: Since gcd(130,17)=1, has purely periodic decimal expansion
17
with period length Ord17 (10). Since φ(17) = 16, we know that Ord17 (10) is
one of the factors of 16 and to find out which one is it, we have to check if
10r ≡ 1 (mod 17) for r = 1,2, . . . , 16. One then obtains that r = 16.
13
Thus is purely periodic decimal with period length 16. In fact, succes-
17
sive division gives that

13
= 0.7647058823529411
17
m
Notice that as long as gcd(m,17)=1, has a purely periodic decimal expan-
17
sion with period length 16.

Theorem 5.6. Generalization(of theorem 5.5)

m m
If is a rational number with 1 ≤ m < n, gcd(gm,n)=1, then has a
n n
purely periodic decimal representation in base g with period length equal to
Ordn (g).

The above two theorems, Theorem 5.2 and Theorem 5.5 characterize the
m
decimal expansion of , 1 ≤ m < n, gcd(m, n) = 1. From this the charac-
n
terization of rational numbers by decimal representations shall be deduced.

Lemma 5.1. Let m, n1 and n2 be integers, with n1 > 1, n2 > 1, 1 ≤ m <

n1 n2 and gcd(m, n1 n2 ) = 1 = gcd(n1 , n2 ). Then there exist integers m1 , m2
and q, 1 ≤ mi < ni and gcd(n1 , n2 ) = 1, i = 1, 2, . . . such that
m m1 m2
=q+ +
n1 n2 n1 n2
Proof: ex. NT-2008-163.

c 2018 Biruk G. AMU

Number Theory Lecture Note 91

Theorem 5.7. Suppose that gcd(m,n)=1, 1 ≤ m < n. Write n = 2α 5β n0

m
with gcd(10m,n0 )=1. Then the decimal expansion of is periodic with pe-
n
riod length equal to Ordn0 (10). Moreover the repeated block begins at least at
the γ + 1 digit after the decimal where γ = max{α, β}.

Proof: ex. NT-2008-164

Corollary 5.1. A decimal expansion is terminating or repeating if and only

if it is a rational number.

Proof: (⇒) If the decimal expansion of a real number is terminating or

periodic, then the usual argument gives that it is a representation of a ratio-
nal number.
m
(⇐) To prove the converse, let be any rational number. Without loss
n
of generality, as remarked at the beginning of the section, we can assume that
m
gcd(m,n)=1 and 1 ≤ m < n. Then by Theorem 5.2, has a terminating
n
decimal representation or by Theorem 5.7 a periodic decimal representation.


Note: Corollary 5.1 says that a rational number is a terminating or a repeat-

ing decimal. In other words: The set of terminating or periodic decimals
is the set of rational numbers. Corollary 5.1 gives the characterization of
rational numbers in the set of decimals. Actually each of the above theorems
can be generalized for any base g, g a natural number greater than one, and
hence the set of rational numbers is the set of terminating or periodic decimal
representations in base g.

The set of decimals which are neither terminating nor periodic in base g
is called the set of irrational numbers.

c 2018 Biruk G. AMU

Number Theory Lecture Note 92

c 2018 Biruk G. AMU

Chapter 6

Other Topics In Number

Theory

6.1 The Set of Algebraic Numbers

6.1.1 Polynomials Over Rings
If R is a commutative ring and a0 , a1 , . . . , an ∈R, then an expression of the
form

an xn + an−1 xn−1 + · · · + a2 x2 + a1 x + a0 (∗)

is called a polynomial in x. It is a finite sum of terms, each of which is

some element of R times a non-negative integral power of x. We become
acquainted with such expressions, and how to add and multiply them, in
elementary algebra. Here we want to consider polynomials in the context of
commutative rings.

Definition 6.1. Let R be a Commutative ring. A polynomial in inde-

terminate x over R is an expression of the form (∗) where the coefficients
a0 , a1 , . . . , an are elements of R.

Notation: The set of all polynomials in x over R will be denoted by R[x].

If f(x)∈R[x] and non-zero, then

f (x) = an xn + an−1 xn−1 + · · · + a2 x2 + a1 x + a0

with a0 , a1 , . . . , an ∈R and an 6= 0.

93
Number Theory Lecture Note 94

If an = 1, then f (x) is called a monic polynomial. By definition(if

an 6= 0), n is called the degree of f , written as deg(f ) = n, and an is
called the leading coefficient of f . Hence degree of every non-zero constant
polynomial is 0. The terms linear, quadratic, cubic, are respectively used for
polynomials of degree one, two, three. Notice that if f and g are non-zero
polynomials over R, then
deg(f g) = deg(f ) + deg(g)
while
deg(f ± g) ≤ max{deg(f ), deg(g)}
For convenience, we let -1 to be the degree of zero polynomial.

Note:
(i) Two polynomials in x are equal if and only if the coefficients of like
powers of x are equal.

(ii) The indeterminate x used in constructing R[x] can be any element such
that an expression of the form (∗) equals the zero element of R if and
only if a0 = a1 = · · · = an = 0. This requirement on x is equivalent
to the requirement that two polynomials in x are if and only if the
coefficients of like powers of x are equal.

(iii) If f, g ∈ R[x], we say that g divides f if and only if f (x) = q(x)g(x)

for some q ∈R[x]. If g divides f we write g|f and g is called a fac-
tor(divisor) of f , while f is called a multiple of g.

Evidently, if g|f and deg(f ) < deg(g), then

f = 0 or f is the zero polynomial i.e. f (x) = 0 ∀x ∈ R.

Polynomials are added by adding coefficients of like powers of x. They are

multiplied by assuming that the laws of a commutative ring apply to all
symbols present(the elements of R, the powers of x, the + sign, and the
juxtaposition of the coefficients with powers of x). Before stating the formal
definition that follows from this assumption, let us look at an example.
Example 6.1. In Z[x], (2x + 5x2 ) + (1 − 3x2 − x3 ) = 1 + 2x + 2x2 − x3 and

(2x + 5x2 )(1 − 3x2 − x3 ) = 2x + 5x2 − 6x3 − 17x4 − 5x5 .

c 2018 Biruk G. AMU

Number Theory Lecture Note 95

Definition 6.2. Let p(x) = am xm + am−1 xm−1 + · · · + a2 x2 + a1 x + a0 and

q(x) = bn xn +bn−1 xn−1 +· · ·+b2 x2 +b1 x+b0 be polynomials over a commutative
ring R. Then

p(x)+q(x) = am xm +· · ·+an+1 xn+1 +(an +bn )xn +(an−1 +bn−1 )xn−1 +· · ·+(a1 +b1 )x+(a0 +b0 )
(6.1)
for m ≥ n, with a similar formula if m < n. And

p(x)q(x) = am bn xm+n + · · · + (a0 b1 + a1 b0 )x + a0 b0 (6.2)

the coefficient of xk being

a0 bk + a1 bk−1 + a2 bk−2 · · · + ak b0 .

Example 6.2. In Z4 [x],

(2 + 2x) + (2 + 3x − x2 ) = x + 3x2 and (2 + 2x)(2 + 3x − x2 ) = 2x + 2x3

(Note: −2 ≡ 2 (mod 4))

Theorem 6.1. If R is a commutative ring, then R[x] is a commutative ring

with respect to the operations defined by (6.1) and (6.2). If R is an integral
domain, then R[x] is an integral domain.

Proof: ex.  (Fun.of.Algebra-217)

Theorem 6.2. (Division Algorithm) If f (x) and g(x) are polynomials

over a field F, with g(x) 6= 0, then there exist unique polynomials q(x) and
r(x) over F such that

f (x) = g(x)q(x) + r(x),

with r(x) = 0 or deg(r(x)) < deg(g(x))

The polynomials q(x) and r(x) are called, respectively, the quotient and
remainder in the division of f (x) by g(x).

Proof:  (Fun.of.Algebra-218)

Theorem 6.3. (Remainder Theorem) If f (x) ∈F[x], and c ∈F, then the
remainder in the division of f (x) by x − c is f (c).

Proof: ex.  (Fun.of.Algebra-219)

c 2018 Biruk G. AMU

Number Theory Lecture Note 96

Example 6.3. Divide f (x) = x3 − 2x2 + 2 ∈R[x] by x − 3.

Solution: The quotient is x2 + x + 3 and the remainder is 11. Also

f (3) = 11.

Theorem 6.4. Factor Theorem If f (x) ∈F[x] and c ∈F, then x − c is a

factor of f (x) if and only if f (c) = 0.

Proof: ex. This is an immediate corollary of the Remainder Theorem. 

(Fun.of.Algebra-220)

Definition 6.3. Suppose f and g are polynomials in R[x]. A polynomial d is

called a common divisor of f and g if and only if d divides f as well as g in
R[x].

Definition 6.4. Suppose f and g are polynomials in R[x]. A polynomial d is

called a greatest common divisor of f and g if and only if

i) d|f and d|g in R[x].

ii) Whenever c is any common divisor of f and g in R[x], then c|d in R[x].

Theorem 6.5. If f and g are polynomials over F, not both zero, then f and
g have a greatest common divisor d(x) and d(x) is a polynomial of smallest
degree among the non-zero polynomials of the form

f(x)e(x) + g(x)h(x) with e(x), h(x)∈F[x].

Proof: ex. (NT-2008-218)

Remark 6.1. : In general, a greatest common divisor of f and g over F is

not unique. If d(x) is a GCD of f and g, then for any non-zero constant
polynomial u, ud(x) is also a GCD of f and g.

Definition 6.5. If f and g are polynomial over F such that their GCD is
a non-zero constant polynomial, then f and g are called relatively prime
polynomials.

Definition 6.6. A polynomial p(x) ∈F[x] is irreducible(or prime) over

F if:

i) p(x) has positive degree;

ii) p(x) is not expressible as a product of polynomials of positive degree

over F.

c 2018 Biruk G. AMU

Number Theory Lecture Note 97

(∴ if p = gh with g,h∈F[x] ⇒ either g or h is a constant polynomial).

Example 6.4. The property of being irreducible depends on the field F. For
example, x2 − 2 is irreducible over Q but reducible over R. i.e.
√ √
x2 − 2 = (x + 2)(x − 2).

Note that if f (x) ∈F[x] is irreducible and c 6= 0 is a constant, then cf (x)

is irreducible too.

The following is the analogue of the Fundamental Theorem of Arithmetic,

and it may be proved by induction on the degree of the polynomial.

Theorem 6.6. Any polynomial f∈F[x] of positive degree can be factored as

f (x) = cp1 (x)p2 (x) · · · pn (x)

with irreducible monic polynomials pi (x) and non-zero constant c in F[x].

Moreover such factorization is unique except the order of the factors.

Proof: ex. 

If f (x) and g(x) are polynomials over F such that f is irreducible over F
and f does not divide g(x), then it is clear that f and g are relatively prime.
Specializing to R = Z and F = Q, we also need the following notion and
facts.

Definition 6.7. If f (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 ∈ Z[x] such

that its coefficients are relatively prime integers, then f is called a primitive
polynomial.

Lemma 6.1. if f,g∈ Z[x] are primitive polynomials, then fg is primitive too.

Proof: The proof is immediate by multiplying f and g and by applying the

definition. 

Theorem 6.7. (Gauss’ Lemma) If a monic polynomial f(x) with integer

coefficients is reducible over Q, then f(x) is reducible over Z

Proof: ex.  (NT-2008-220)

c 2018 Biruk G. AMU

Number Theory Lecture Note 98

Example 6.5. Show that a polynomial f(x)∈R[x] of degree 2 or 3 is reducible

over F if and only if f (x) = 0 has a solution in F.

Solution: Evidently every linear polynomial over F has a root in F. Let

f(x)∈R[x] be a polynomial of degree 2 or 3. Then f(x) is reducible over F if
and only if there exist polynomials g(x) and h(x) with positive degrees over F
such that

f(x)=g(x)h(x).

But then either g(x) or h(x) is linear, the linear factor has a root and hence
f(x) has a root in F. Therefore, for a polynomial f(x) with degree 2 and 3, f
is reducible over F if and only f (x) = 0 has a solution in F.

Example 6.6. Find the factorization of x2 + 4 over Q into monic irreducible

polynomials.

Solution: x2 +4 = (x2 −2x+2)(x2 +2x+2). Hence x2 +4 is reducible over

Q. It is easy to see that neither x2 − 2x + 2 nor x2 + 2x + 2 has a root in Q.
Hence, by Example 6.5,both x2 − 2x + 2 and (x2 + 2x + 2) are irreducible in Q.

Therefore, x2 + 4 = (x2 − 2x + 2)(x2 + 2x + 2) is the factorization of x2 + 4

into monic irreducible polynomials over Q.

Eisenstein Criterion: If f (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 ∈ Z[x]

such that for some prime p, p - an , p | an−1 , . . . , p | a1 , p | a0 and p2 - a0 then
f (x) is irreducible over Q.

6.1.2 Field Extensions And Algebraic Numbers

Fields(i.e. a commutative division ring) are most conveniently analyzed by
studying how they are built up from smaller subfields.

If E is a field, any subset F of E that is a field under the operation of

E restricted to F is called a subfield of E. If F is a subfield of E, E is also
called a field extension of F. For instance, Q is a subfield of R, and C is
an extension of both Q and R.

Definition 6.8. Suppose E is a field extension of F. An element α ∈E is

called algebraic over F if and only if there exists a non-zero polynomial f (x)
over F such that f (α) = 0. Otherwise α is called transcendental over F.

c 2018 Biruk G. AMU

Number Theory Lecture Note 99

Note:

i) Every rational number α is a root of x − α and x − α ∈ Q[x]. Thus

every rational number is algebraic over Q.

ii) Complex numbers that are algebraic over Q are simply called algebraic
numbers.

Let

A = {α ∈ C|α is algebraic over Q}

A is called the set of algebraic numbers.(show that A is a subfield of C)

√ √
Example 6.7. i) The complex numbers 2 and −1 are algebraic over
Q because they are roots of the polynomials x2 − 2 and x2 + 1, respec-
tively, the polynomials are over Q.

ii) π and e and hence aπ and ae, for any a∈ Q\{0} are transcendental
numbers(not algebraic) over Q.

Consequently these numbers are examples of transcendental numbers of A

that are roots of monic polynomials over Z and are called algebraic integers
or simply integers. Note that every element of Z is an algebraic integer. To
distinguish them from the others, elements of Z are called rational integers.

√
Example 6.8. a + b −1 = a + bi, where a, b ∈ Z, with b 6= 0 is an algebraic
integer of degree 2 since it is a root of x2 − 2ax + a2 + b2 but not a root of a
linear, integral, monic polynomial since b 6= 0.

∗ If E is an extension of F, then E can be considered as a vector space over

F. Indeed E is an Abelian group under addition and the function

f : F × E −→ E given by f (a, e) = ae for any a ∈ F and e ∈ E.

satisfies the rest of the axioms of a vector space. If dimension of E over F

is finite, then E is called a finite extension of F; otherwise it is called an
infinite extension of F.

Notation: The dimension of E as a vector space over F is called the

degree of extension of E over F and is denoted by [E:F]. We say the field
extension is finite or infinite accordingly as [E:F] is finite or infinite.

c 2018 Biruk G. AMU

Number Theory Lecture Note 100

Definition 6.9. A field extension E of F is called an algebraic extension

of F if and only if every element of E is algebraic over F.
Theorem 6.8. Let E be an extension field of F. If E is a finite field extension
of F, then E is an algebraic extension of F.

Proof: ex.  (NT-2008-223, Fun.of.Algebra-223)

The Fundamental Theorem of Algebra states that every polynomial over
C with positive degree has a root in C. Consequently, every polynomial of
positive degree over Q has a root in A. It is not difficult to see that last
assertion is equivalent to saying every positive degree polynomial over Q is
a product of linear polynomials with coefficients in A. In particular, every
Diophantine equation is completely solvable in A. This is one of the main
reasons why algebraic numbers are of interest to number theorists.

In the following theorem we will show that for a given non-zero algebraic
number α, the existence and uniqueness of a monic irreducible polynomial
where α is the root of the polynomial.
Theorem 6.9. If α is a non-zero algebraic number, there exists a unique
monic irreducible polynomial p(x) such that P (α) = 0.

Proof: ex.  (NT-2008-224)

Definition 6.10. For an algebraic number α 6= 0, the monic irreducible poly-
nomial p(x) ∈ Q[x] such that P (α) = 0 is called the minimal(irreducible)
polynomial of α over Q. It is often denoted by Irr(α, Q)

The degree of P (x) is called the degree of α over Q.

Note: Let E be an extension field of a field F; for convenience assume
F⊂E. Also let S be a subset of E. There is at least one subfield of E contain-
ing both F and S, namely, E itself. The intersection of all the subfields of E
that contains both F and S is a subfield of E; it will be denoted by F(S). If
S⊂F, then F(S)=F.

If S = {a1 , a2 , . . . , an }, then F(S) will be denoted by F(a1 , a2 , . . . , an ).

For example, R(i) = C

The field F(S) consists of all the elements of E that can be obtained
from F and S by repeated applications of the operations of E, i.e. addition,

c 2018 Biruk G. AMU

Number Theory Lecture Note 101

multiplication, and taking additive and multiplicative inverses. If E=F(a)

for some a∈E, then E is said to be a simple extension of F. For instance,
C is a simple extension of R.

Theorem 6.10. Suppose α is an algebraic number of degree n. The smallest

subfield of C containing Q and α, denoted by Q(α), is equal to

T = {β|β = a0 + a1 α + a2 α2 + · · · + an−1 αn−1 , ai ∈ Q, i = 0, 1, 2, . . . , n − 1}

(i.e. Q(α) = T ) Proof: ex.  (NT-2008-225)

Theorem 6.11. A, the set of algebraic numbers, is a field under addition

and multiplication of complex numbers.

Proof: ex.

Example 6.9. Show that A is an infinite extension of Q.

Solution: By Eisenstein’s Criterion for each natural number n

fn (x) = xn − 2
√
n
is irreducible over Q.
√ By Theorem 6.10, the dimension of Q( 2) over Q is
equal to n. But Q( n 2) ⊂ A. Thus
√
dimQ Q( n 2) ≤ dimQ A

⇒ n ≤ dimQ A ∴ dimQ A ≥ n.

As n is arbitrary, the dimension of A over Q is infinite. Therefore A is

an infinite extension of Q.

Remark 6.2. Though A is an infinite extension of Q, it can be proved that

A is countably infinite. As R is uncountably infinite and the algebraic real
numbers are countable, it follows that the set of transcendental real numbers
(i.e. real numbers which are not algebraic over Q) is uncountably infinite.
There is an extensive work on transcendental numbers.

In general,A is quite large for particular considerations. Often it suffices

to work on finite extensions of Q. Such field extensions of Q are called
(algebraic) number fields. Algebraic Number Theory is concerned with
the study of number fields.

c 2018 Biruk G. AMU

Number Theory Lecture Note 102

Theorem 6.12. Let E be an extension field of a field F. Let α ∈E be alge-

braic over F. Let n = degIrr(α ,F). Then F(α) is an n-dimensional vector
space over F with basis {1, α, α2 , . . . , αn−1 }.

Proof: ex.  (Fun.of.Algebra-224)

√ √
Example 6.10. Consider Q( 2) over Q. Irr( 2, Q) = x2 − 2.
√ √
Therefore, {1, 2} is a basis of Q( 2) over Q.
√ √
Hence, Q( 2) = {a + b 2 : a, b ∈ Q}.
√ √
The dimension of Q( 2) over Q =[Q( 2):Q]= deg(x2 − 2) = 2.
Example 6.11. Consider C over R. C = R(i) and Irr(i,R)=x2 + 1.

Therefore, {1, i} is a basis of C over R.

Hence, C = {a + bi : a, b ∈ R} and [C:R]=deg(x2 + 1)= 2.

Example 6.12. Find the different number fields of dimension 3 over Q.

Solution: Consider the polynomial f (x) = x3 − 5 over Q. By Eisenstein

criterion f (x) irreducible over Q. However f (x) is reducible in R as
√ √ √
f (x) = x3 − 5 = (x − 3 5)(x2 + 3 5x + 3 5)
√ √
Now with α =√3 5, √ E1 = Q( 3 5) is an extension of Q that√is contained in
R and, as {1, 3 5, ( 3 5)2 } is a basis of the vector space Q( 3 5) over Q, by
Theorem 6.10, we see that
√
dimQ E1 = dimQ Q( 3 5) = 3.
On the other hand, roots of the equation
√ √
x2 + 3 5x + 3 5 = 0
are non-real complex numbers. Using quadratic formula, the roots are
√ √
−1 + −3 √ 3 −1 − −3 √ 3
β= 5 and θ = 5
2 2
Setting E2 = Q(β), it again follows, by Theorem 6.10, that dimQ E2 = 3.

Due to the observation made about β, it is clear that E2 is not a subset

of R. Hence E1 and E2 are two extensions of Q with dimension 3 over Q.

c 2018 Biruk G. AMU

Number Theory Lecture Note 103

6.2 Continued Fractions In Real Numbers

∗ Why are continued fractions useful/interesting?

1. Gives good approximation to real numbers.

2. Continued fractions and higher dimensional variants have application

in engineering.

3. Useful in number theory for study of quadratic fields, diophantine equa-

tions.

c 2018 Biruk G. AMU