Introduction to
Number Theory
Assylbek Issakhov,
Ph.D., professor
Number Theory
▪ The part of mathematics devoted to the study
of the set of integers and their properties is
known as Number Theory. In this lecture we will
develop some of the important concepts of
Number Theory including many of those used in
computer science.
Division
▪ When one integer is divided by a second nonzero
integer, the quotient may or may not be an
integer. For example,
12
=4
3
▪ is an integer, whereas
11
= 2.75
4
▪ is not. This leads to Definition 1.
Division
▪ DEFINITION 1. If 𝑎 and 𝑏 are integers with 𝑎 ≠ 0,
we say that 𝑎 divides 𝑏 if there is an integer 𝑐 such
that 𝑏 = 𝑎𝑐, or equivalently, if 𝑏/𝑎 is an integer.
When 𝑎 divides 𝑏 we say that 𝑎 is a factor or
divisor of 𝑏, and that 𝑏 is a multiple of 𝑎. The
notation 𝑎|𝑏 denotes that 𝑎 divides 𝑏.
▪ We write 𝑎 ∤ 𝑏 when 𝑎 does not divide 𝑏.
Examples
▪ Determine whether 3|7 and whether 3|12.
▪ Let 𝑛 and 𝑑 be positive integers. How many
positive integers not exceeding 𝑛 are divisible
by 𝑑?
Examples
▪ In Figure, a number line indicates which
integers are divisible by the positive integer 𝑑.
▪ Answer:
𝑛
𝑑
Division
▪ THEOREM 1. Let 𝑎, 𝑏, and 𝑐 be integers, where
𝑎 ≠ 0. Then
(i) if 𝑎|𝑏 and 𝑎|𝑐, then 𝑎|(𝑏 + 𝑐);
(ii) if 𝑎|𝑏, then 𝑎|𝑏𝑐 for all integers 𝑐;
(iii) if 𝑎|𝑏 and 𝑏|𝑐, then 𝑎|𝑐.
Division
▪ COROLLARY 1. If 𝑎, 𝑏, and 𝑐 are integers, where
𝑎 ≠ 0, such that
𝑎|𝑏 and 𝑎|𝑐,
▪ then
𝑎|(𝑚𝑏 + 𝑛𝑐)
▪ whenever 𝑚 and 𝑛 are integers.
The Division Algorithm
▪ When an integer is divided by a positive integer,
there is a quotient and a remainder, as the
division algorithm shows.
▪ THEOREM 2. (THE DIVISION ALGORITHM) Let 𝑎
be an integer and 𝑑 a positive integer. Then there
are unique integers 𝑞 and 𝑟, with 0 ≤ 𝑟 < 𝑑,
such that
𝑎 = 𝑑𝑞 + 𝑟
The Division Algorithm
▪ DEFINITION 2. In the equality given in the
division algorithm, 𝑑 is called the divisor, 𝑎 is
called the dividend, 𝑞 is called the quotient, and
𝑟 is called the remainder. This notation is used to
express the quotient and remainder:
𝑞 = 𝑎 𝒅𝒊𝒗 𝑑
𝑟 = 𝑎 𝒎𝒐𝒅 𝑑.
The Division Algorithm
▪ Remark: Note that both 𝑎 𝒅𝒊𝒗 𝑑 and 𝑎 𝒎𝒐𝒅 𝑑
for a fixed 𝑑 are functions on the set of integers.
▪ Furthermore, when 𝑎 is an integer and 𝑑 is a
positive integer, we have
𝑞 = 𝑎 𝒅𝒊𝒗 𝑑 = [𝑎/𝑑]
▪ and
𝑟 = 𝑎 𝒎𝒐𝒅 𝑑 = 𝑎 − 𝑑𝑞
Examples
▪ What are the quotient and remainder when 101
is divided by 11?
▪ What are the quotient and remainder when −11
is divided by 3?
The Division Algorithm
▪ Remark: A programming language may have one,
or possibly two, operators for modular arithmetic,
denoted by mod (in BASIC, Maple, Mathematica,
EXCEL, and SQL), % (in C, C++, Java, and Python),
rem (in Ada and Lisp), or something else. Be
careful when using them, because for 𝑎 < 0,
some of these operators return 𝑎 − 𝑚([𝑎/𝑚] +
1) instead of 𝑎 𝒎𝒐𝒅 𝑚 = 𝑎 − 𝑚[𝑎/𝑚]. Also,
unlike 𝑎 𝒎𝒐𝒅 𝑚, some of these operators are
defined when 𝑚 < 0, and even when 𝑚 = 0.
Modular Arithmetic
▪ In some situations we care only about the
remainder of an integer when it is divided by
some specified positive integer.
▪ For instance, when we ask what time it will be
(on a 24-hour clock) 50 hours from now, we
care only about the remainder when 50 plus
the current hour is divided by 24.
Modular Arithmetic
▪ Because we are often interested only in
remainders, we have special notations for
them. We have already introduced the notation
𝑎 𝒎𝒐𝒅 𝑚 to represent the remainder when an
integer 𝑎 is divided by the positive integer 𝑚.
We now introduce a different, but related,
notation that indicates that two integers have
the same remainder when they are divided by
the positive integer 𝑚.
Modular Arithmetic
▪ DEFINITION 3. If 𝑎 and 𝑏 are integers and 𝑚 is a
positive integer, then 𝑎 is congruent to 𝑏 modulo
𝑚 if 𝑚 divides 𝑎 − 𝑏. We use the notation
𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚)
▪ to indicate that 𝑎 is congruent to 𝑏 modulo 𝑚.
We say that 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚) is a congruence and
that 𝑚 is its modulus (plural moduli). If 𝑎 and 𝑏
are not congruent modulo 𝑚, we write
𝑎 ≢ 𝑏(𝑚𝑜𝑑 𝑚).
Modular Arithmetic
▪ Although both notations 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚) and
𝑎 𝒎𝒐𝒅 𝑚 = 𝑏 include “𝑚𝑜𝑑,” they represent
fundamentally different concepts. The first
represents a relation on the set of integers,
whereas the second represents a function.
▪ However, the relation 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚) and the
𝒎𝒐𝒅 𝑚 function are closely related, as described
in the next Theorem 3.
Modular Arithmetic
▪ THEOREM 3. Let 𝑎 and 𝑏 be integers, and let 𝑚
be a positive integer. Then
𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚)
▪ if and only if
𝑎 𝒎𝒐𝒅 𝑚 = 𝑏 𝒎𝒐𝒅 𝑚.
Example
▪ Determine whether 17 is congruent to 5
modulo 6.
▪ Determine whether 24 and 14 are congruent
modulo 6.
Modular Arithmetic
▪ The great German mathematician Karl Friedrich
Gauss developed the concept of congruences at
the end of the eighteenth century.
▪ The notion of congruences has played an
important role in the development of number
theory. The next Theorem 4 provides a useful
way to work with congruences.
Modular Arithmetic
▪ THEOREM 4. Let 𝑚 be a positive integer. The
integers 𝑎 and 𝑏 are congruent modulo 𝑚 if and
only if there is an integer 𝑘 such that
𝑎 = 𝑏 + 𝑘𝑚.
Modular Arithmetic
▪ The set of all integers congruent to an integer 𝑎
modulo 𝑚 is called the congruence class of 𝑎
modulo 𝑚.
▪ THEOREM 5. Let 𝑚 be a positive integer. If
𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚) and 𝑐 ≡ 𝑑(𝑚𝑜𝑑 𝑚), then
𝑎 + 𝑐 ≡ 𝑏 + 𝑑 𝑚𝑜𝑑 𝑚
▪ and
𝑎𝑐 ≡ 𝑏𝑑(𝑚𝑜𝑑 𝑚)
Example
▪ Because 7 ≡ 2(𝑚𝑜𝑑 5) and 11 ≡ 1(𝑚𝑜𝑑 5), it
follows from Theorem 5 that
18 = 7 + 11 ≡ 2 + 1 = 3(𝑚𝑜𝑑 5),
and that
77 = 7 ⋅ 11 ≡ 2 ⋅ 1 = 2(𝑚𝑜𝑑 5).
Arithmetic Modulo 𝒎
▪ We can define arithmetic operations on ℤ𝑚 , the
set of nonnegative integers less than 𝑚, that is,
the set {0, 1, . . . , 𝑚 − 1}. In particular, we define
addition of these integers, denoted by +𝑚 by
𝑎 +𝑚 𝑏 = (𝑎 + 𝑏)𝒎𝒐𝒅 𝑚,
where the addition on the right-hand side of this
equation is the ordinary addition of integers, and
we define multiplication of these integers,
denoted by ⋅𝑚 by
𝑎 ⋅𝑚 𝑏 = 𝑎 ⋅ 𝑏 𝒎𝒐𝒅 𝒎
HOMEWORK: Exercises 6, 10, 12, 14, 22, 24
on pp. 244-245;
Representations of Integers
▪ In everyday life we use decimal notation to
express integers. For example, 965 is used to
denote
9 ⋅ 102 + 6 ⋅ 10 + 5.
However, it is often convenient to use bases
other than 10.
Representations of Integers
▪ In particular, computers usually use binary
notation (with 2 as the base) when carrying
out arithmetic, and octal (base 8) or
hexadecimal (base 16) notation when
expressing characters, such as letters or digits.
▪ In fact, we can use any integer greater than 1
as the base when expressing integers. This is
stated in Theorem 1.
Representations of Integers
▪ THEOREM 1. Let 𝑏 be an integer greater than 1.
Then if 𝑛 is a positive integer, it can be
expressed uniquely in the form
𝑛 = 𝑎𝑘 𝑏 𝑘 + 𝑎𝑘−1 𝑏𝑘−1 + ⋯ + 𝑎1 𝑏 + 𝑎0 ,
where 𝑘 is a nonnegative integer,
𝑎0 , 𝑎1 , … , 𝑎𝑘 are nonnegative integers less than
𝑏, and 𝑎𝑘 ≠ 0.
Representations of Integers
▪ The representation of 𝑛 given in Theorem 1 is
called the base 𝒃 expansion of 𝒏. The base 𝑏
expansion of 𝑛 is denoted by
𝑎𝑘 𝑎𝑘−1 … 𝑎1 𝑎0 𝑏 .
2
For instance, 245 8 represents 2 ⋅ 8 +4⋅8+
5 = 165.
▪ Typically, the subscript 10 is omitted for base 10
expansions of integers because base 10, or
decimal expansions are commonly used to
represent integers.
Representations of Integers
BINARY EXPANSIONS
▪ Choosing 2 as the base gives binary expansions
of integers. In binary notation each digit is
either a 0 or a 1. In other words, the binary
expansion of an integer is just a bit string.
▪ Binary expansions (and related expansions that
are variants of binary expansions) are used by
computers to represent and do arithmetic with
integers.
Example
▪ What is the decimal expansion of the integer
that has
1 0101 1111 2
as its binary expansion?
Example
▪ Solution:
1 0101 1111 2
= 1 ⋅ 28 + 0 ⋅ 27 + 1 ⋅ 26 + 0 ⋅ 25 + 1 ⋅ 24
+ 1 ⋅ 23 + 1 ⋅ 22 + 1 ⋅ 21 + 1 ⋅ 20
= 256 + 64 + 16 + 8 + 4 + 2 + 1 = 351
Representations of Integers
OCTAL AND HEXADECIMAL EXPANSIONS
▪ Among the most important bases in computer
science are base 2, base 8, and base 16.
▪ Base 8 expansions are called octal expansions
and base 16 expansions are hexadecimal
expansions.
Examples
▪ What is the decimal expansion of the number
with octal expansion 7016 8 ?
▪ Solution:
7016 8 = 7 ⋅ 83 + 0 ⋅ 82 + 1 ⋅ 81 + 6 ⋅ 80
= 7 ⋅ 512 + 8 + 6 = 3598
Examples
▪ Sixteen different digits are required for
hexadecimal expansions. Usually, the
hexadecimal digits used are
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹,
▪ where the letters 𝐴 through 𝐹 represent the
digits corresponding to the numbers 10
through 15 (in decimal notation).
Examples
▪ What is the decimal expansion of the number
with hexadecimal expansion 2𝐴𝐸0𝐵 16 ?
▪ Solution:
2𝐴𝐸0𝐵 16
= 2 ⋅ 164 + 10 ⋅ 163 + 14 ⋅ 162 + 0 ⋅ 161
+ 11 ⋅ 160
= 2 ⋅ 65536 + 10 ⋅ 4096 + 14 ⋅ 256 + 0
+ 11 = 131072 + 40960 + 3584 + 11
= 175627
Representations of Integers
BASE CONVERSION
▪ We will now describe an algorithm for constructing
the base 𝑏 expansion of an integer 𝑛. First, divide
𝑛 by 𝑏 to obtain a quotient and remainder, that is,
𝑛 = 𝑏𝑞0 + 𝑎0 , 0 ≤ 𝑎0 < 𝑏.
▪ The remainder, 𝑎0 , is the rightmost digit in the
base 𝑏 expansion of 𝑛. Next, divide 𝑞0 by 𝑏 to
obtain
𝑞0 = 𝑏𝑞1 + 𝑎1 , 0 ≤ 𝑎1 < 𝑏.
Representations of Integers
BASE CONVERSION
▪ We see that 𝑎1 is the second digit from the right
in the base 𝑏 expansion of 𝑛.
▪ Continue this process, successively dividing the
quotients by 𝑏, obtaining additional base 𝑏
digits as the remainders. This process terminates
when we obtain a quotient equal to zero.
▪ It produces the base 𝑏 digits of 𝑛 from the right
to the left.
Example
▪ Find the binary expansion of 241 10 .
▪ Solution:
241 = 128 + 64 + 32 + 16 + 1
10
= 27 + 26 + 25 + 24 + 20
= 11110001 2
Example
▪ Find the octal expansion of 12345 10 .
▪ Solution:
12345 10
= 8192 + 4096 + 32 + 16 + 8 + 1
= 11 000 000 111 001 2
= 011 000 000 111 001 2
= 30071 8
Representations of Integers
Representations of Integers
Algorithms for Integer Operations
▪ The algorithms for performing operations with
integers using their binary expansions are
extremely important in computer arithmetic.
▪ We will describe algorithms for the addition and
the multiplication of two integers expressed in
binary notation
Representations of Integers
▪ Throughout this discussion, suppose that the
binary expansions of 𝑎 and 𝑏 are
𝑎 = 𝑎𝑛−1 … 𝑎1 𝑎0 2 , 𝑏 = 𝑏𝑛−1 … 𝑏1 𝑏0 2 ,
so that 𝑎 and 𝑏 each have 𝑛 bits (putting bits
equal to 0 at the beginning of one of these
expansions if necessary).
▪ We will measure the complexity of algorithms
for integer arithmetic in terms of the number of
bits in these numbers.
Representations of Integers
ADDITION ALGORITHM
▪ Consider the problem of adding two integers in
binary notation. To add 𝑎 and 𝑏, first add their
rightmost bits. This gives 𝑎0 + 𝑏0 = 𝑐0 ⋅ 2 + 𝑠0 ,
where 𝑠0 is the rightmost bit in the binary
expansion of 𝑎 + 𝑏 and 𝑐0 is the carry, which is
either 0 or 1.
▪ Then add the next pair of bits and the carry,
𝑎1 + 𝑏1 + 𝑐0 = 𝑐1 ⋅ 2 + 𝑠1 , where 𝑠1 is the next
bit (from the right) in the binary expansion of
𝑎 + 𝑏, and 𝑐1 is the carry.
Representations of Integers
ADDITION ALGORITHM
▪ Continue this process, adding the corresponding
bits in the two binary expansions and the carry,
to determine the next bit from the right in the
binary expansion of 𝑎 + 𝑏.
▪ At the last stage, add 𝑎𝑛−1 , 𝑏𝑛−1 , and 𝑐𝑛−2 to
obtain 𝑐𝑛−1 ⋅ 2 + 𝑠𝑛−1 . The leading bit of the
sum is 𝑠𝑛 = 𝑐𝑛−1 . This procedure produces the
binary expansion of the sum, namely,
𝑎 + 𝑏 = 𝑠𝑛 𝑠𝑛−1 … 𝑠1 𝑠0 2
Example
▪ Add 𝑎 = 1110 2 and 𝑏 = 1011 2 .
▪ Solution:
𝑎 + 𝑏 = 1110 2 + 1011 2 = 11001 2
▪ Cheking:
1110 2 = 8 + 4 + 2 = 14
1011 2 = 8 + 2 + 1 = 11
11001 2 = 16 + 8 + 1 = 25
Representations of Integers
MULTIPLICATION ALGORITHM
▪ Next, consider the multiplication of two 𝑛-bit
integers 𝑎 and 𝑏. The conventional algorithm
(used when multiplying with pencil and paper)
works as follows. Using the distributive law, we
see that
𝑎𝑏 = 𝑎 𝑏0 20 + 𝑏1 21 + ⋯ + 𝑏𝑛−1 2𝑛−1 =
𝑎 𝑏0 20 + 𝑎 𝑏1 21 + ⋯ + 𝑎(𝑏𝑛−1 2𝑛−1 ).
▪ We can compute 𝑎𝑏 using this equation.
Example
▪ Find the product of 𝑎 = 110 2 and 𝑏 = 101 2 .
▪ Solution:
𝑎 ⋅ 𝑏 = 110 2 ⋅ 101 2
= 110 2 + 0000 2 + 11000 2
= 11110 2
▪ Cheking:
110 2 = 6, 101 2 = 5
11110 2 = 16 + 8 + 4 + 2 = 30
HOMEWORK: Exercises 2, 4, 6, 8, 22, 32
on pp. 255-256;
