Mathematics for Computing – Discrete Mathematics
1
Lecturer: Dr Nguyen Hieu Thao
Email: [Link]@[Link]
Lecture Notes: Number Theory
(Week 7)1
Divisors and prime numbers
(a) Let n and d be integers, d 6= 0. We say that d divides n if there exists an integer q satisfying
n = dq. We call q the quotient and d a divisor or factor of n. If d divides n, we write
d | n. If d does not divide n, we write d - n.
(b) An integer greater than 1 whose only positive divisors are itself and 1 is a prime.
(c) An integer greater than 1 that is not prime is a composite.
(d) Let m and n be integers with not both zero. A common divisor of m and n is an integer
that divides both m and n. The greatest common divisor of m and n is denoted by
gcd(m, n). We take gcd(m, n) ≥ 0.
(e) Two integers m and n are relatively prime if gcd(m, n) = 1.
(f) Let m and n be positive integers. A common multiple of m and n is an integer that is
divisible by both m and n. The least common multiple of m and n, denoted by lcm(m, n),
is the smallest positive common multiple of m and n.
Theorems
(a) Let m, n and d be integers. If d | m and d | n, then d | (am + bn) for all integers a, b.
(b) The number of primes is infinite.
√
(c) An integer n > 1 is composite iff it has a prime divisor p ≤ n.
(d) Fundamental theorem of arithmetic. Any integer greater than 1 can be written as a
product of primes. Moreover, if the primes are written in nondecreasing order, the factor-
ization is unique. In symbols, if n = p1 p2 · · · pi & n = p01 p02 · · · p0j where pk & p0k are primes
and p1 ≤ p2 ≤ · · · ≤ pi & p01 ≤ p02 ≤ · · · ≤ p0j , then i = j and pk = p0k (∀k = 1, 2, . . . , i).
1 Most of the content of this document is taken from the book [1].
2
(e) Let m and n be integers, m > 1, n > 1, with prime factorizations
m = pa1 1 pa2 2 · · · pakk and n = pb11 pb22 · · · pbkk .
If the prime pi is not a factor of m, we let ai = 0. Similarly, if the prime pi is not a factor
of n, we let bi = 0. Then
min(a1 ,b1 ) min(a2 ,b2 ) min(ak ,bk )
gcd(m, n) = p1 p2 · · · pk ,
and
max(a1 ,b1 ) max(a2 ,b2 ) max(ak ,bk )
lcm(m, n) = p1 p2 · · · pk .
(f) For any positive integers m and n,
gcd(m, n) · lcm(m, n) = mn.
(g) If a is a nonnegative integer, b is a positive integer, and r = a mod b, then
gcd(a, b) = gcd(b, r).
(h) If a and b are nonnegative integers, not both zero, there exist integers s and t such that
gcd(a, b) = sa + tb.
(i) For two integers n > 0 and φ > 1 with gcd(n, φ) = 1, there exists a unique integer s,
0 < s < φ, such that ns mod φ = 1. We call s the multiplicative inverse of n modulo φ.
(j) If a, b, and z are positive integers, then
ab mod z = [(a mod z)(b mod z)] mod z.
(k) (Fermat’s theorem) If p is prime, then
ap−1 ≡ 1 mod p, ∀a ∈ Z∗p ,
where Z∗p = {1, 2, . . . , p − 1} – the multiplicative group modulo p.
(l) If p and q are relatively prime and n = pq, then for all integers x and a,
x ≡ a mod p and x ≡ a mod q ⇐⇒ x ≡ a mod n.
Notes. Multiplicative inverse can be computed using this calculator from PlanetCalc.
Notes. Modulo operations can be computed using this calculator from PlanetCalc.
Proof By the quotient-remainder theorem, there exist q and r satisfying
a = bq + r 0 ≤ r < b.
We show that the set of common divisors of a and b is equal to the set of common divisors
of b and r, thus proving the theorem.
Let c be a common divisor of a and b. By Theorem 5.1.3(c), c | bq. Since c | a and
c | bq, by Theorem 5.1.3(b), c | a − bq (= r). Thus c is a common divisor of b and r.
3
Conversely, if c is a common divisor of b and r, then c | bq and c | bq + r (= a) and c is
a common divisor of a and b. Thus the set of common divisors of a and b is equal to the
The Euclidean
set of commonAlgorithm
divisors of bisand
a [Link] andgcd(a,
Therefore, efficient algorithm
b) = gcd(b, r). for finding the greatest
common divisorWe
of next
two formally
[Link] the Euclidean algorithm as Algorithm 5.3.3.
Algorithm 5.3.3 Euclidean Algorithm
This algorithm finds the greatest common divisor of the nonnegative integers a and
b, where not both a and b are zero.
Input: a and b (nonnegative integers, not both zero)
Output: Greatest common divisor of a and b
1. gcd(a, b) {
2. // make a largest
3. if (a < b)
4. swap(a, b)
5. while (b ¬= 0) { ❦
6. r = a mod b
7. a=b
8. b=r
9. }
10. return a
11. }
Example. Compute
We note that multiplicative
the the while loop in theinverse:
Euclideangiven 0 and5–9)
n >(lines
algorithm 1 with
φ >always gcd(n, φ) = 1,
termi-
there is annates since
integer s,at0 the
< sbottom of thethat
< φ, such loop ns
(lines
mod7 and
φ =8),
[Link] values of a and b are updated
to smaller values. Since nonnegative integers cannot decrease indefinitely, eventually b
Indeed,becomes
since gcd(n,
zero and
φ)the 1, weterminates.
= loop use the Euclidean algorithm to find numbers s0 and t0 such
Let G = gcd(a, b), where a and b are the values input to Algorithm 5.3.3. We can
that s0 n + prove
t0 φ =that Then ns05.3.3
1. Algorithm = −t 0
and
φ + 1, by
is correct hence that
verifying ns0Gmod φ = 1b)asis φ
= gcd(a, Set s = s0 mod φ.
> [Link],
a loop
where
Then we have now0a<and
that s<b denote
φ andthe
nsvariables
mod φ =inns
the0 mod
pseudocode.
φ = 1 as required.
By definition, the loop invariant is true the first time we arrive at line 5. Sup-
pose that G = gcd(a, b) is true prior to another iteration of the loop and that b ̸ = 0.
RSA public-key
Theorem 5.3.2cryptosystems
then tells us that after line 6 executes, gcd(a, b) = gcd(b, r). At lines 7
and 8, a becomes
1. Select at random two b and b becomes
large r. Therefore,
prime numbers G = q,
p and gcd(a,
p 6=b)
[Link] true for the new values
of a and b. It follows that G = gcd(a, b) is a loop invariant. The while loop terminates
2. Compute
when n b becomes
= pq. 0. At this point, the loop invariant becomes G = gcd(a, 0). The algo-
rithm then returns a [= gcd(a, 0)]. Thus the value that the algorithm returns is G, which
3. Selectbyadefinition
small odd integer e that is relatively prime to φ(n) = (p − 1)(q − 1).
is the greatest common divisor of the input values. Therefore, Algorithm
4. Compute
5.3.3 is as the multiplicative inverse of e modulo φ(n).
d correct.
Algorithm 5.3.3 correctly finds the greatest common divisor if lines 3 and 4 are
5. Publish the (see
omitted pairExercise n) as
P = (e,15). Wethe these lines RSA
participant’s
include becausepublic [Link] analysis of
it simplifies
Algorithm 5.3.3 in the next subsection.
6. Keep secret the pair S = (d, n) as the participant’s RSA secret key.
To encode/encrypt a message M associated with a public key P = (e, n), compute
P (M ) = M e mod n, ∀M ∈ Zn .
❦ C associated with a secret key S = (d, n), compute
To decode/decrypt a ciphertext
S(C) = C d mod n, ∀C ∈ Zn .
Theorem. S(P (M )) = P (S(M )) = M for all M ∈ Zn .
on capable of being in two states—one representing 1, the other 0. In this section we discuss 5.2 ◆ Representations of Integers and Integer Algorithms 225
❦
tions of the binary number system, which represents integers using bits, and the hexadecimal
ee number system, which represents integers using 16 symbols. The octal number In thesys-
binary (base 2) number system, to represent integers we need only two
WyqJp9 tem, which represents integers using eight symbols, is discussed before symbols,
Exercise 42.
0 and 1. In representing an integer, reading from the right, the first symbol
In the decimal number system, to represent integers we use the 10represents
symbols 0, the1,number of 1’s, the next symbol the number of 2’s, the next symbol the
2, 3, 4, 5, 6, 7, 8, and 9. In representing an integer, the symbol’s positionnumber
is significant;
of 4’s, the next symbol the number of 8’s, and so on. For example, in base 2,†
reading from the right, the first symbol represents the number of 1’s, the next symbol
the number of 10’s, the next symbol the number of 100’s, and so on. For example, 1011012 = 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20
4 (see Figure 5.2.2). In general, the symbol in position n (with the rightmost symbol be-
3854 = 3 · 103 + 8 · 102 + 5 · 101 + 4 · 100
ing in position 0) represents the number of 2n ’s. Since 20 = 1, the symbol in position 0
Representations
(see Figure 5.2.1).
n
of integers
In general, the symbol in position n (with the rightmostrepresents
0 the
the number of 20 ’s, or 1’s; since 21 = 2, the symbol in position 1 represents
symbol being
number of021 ’s or 2’s; since 22 = 4, the symbol in position 2 represents the number
in position 0) represents the number of 10 ’s. Since 10 = 1, the symbol in2 position
of 21 ’s
represents the number of 100 ’s or 1’s; since 101 = 10, the symbol in position or 4’s; and so on.
represents
the number of 101 ’s or 10’s; since 102 = 100, the symbol in position 2 represents the
8’s place (2 3 ) 4’s place (2 2 )
number of 102 ’s or 100’s; and so on. We call the value on which the system is based (10
in the case of the decimal system) the base of the number system. 16’s place (2 4 ) 2’s place (2 1)
100’s place (10 2 ) 10’s place (10 1) 32’s place (2 5 ) 1’s place (2 0 )
1000’s place (10 3 ) 1’s place (10 0 ) 1 0 1 1 0 1
3 8 5 4 Symbol 5 Symbol 0
Symbol 3 Symbol 0 Symbol 4 Symbol 1
❦ Symbol 2 Symbol 1 Symbol 3 Symbol 2
Figure 5.2.1 The decimal number system. Figure 5.2.2 The binary number system.
Figure 1: Decimal (left) and binary (right) number systems.
Example 5.2.1 Computer Representation of Integers Computer systems represent integers in bi-
nary. Compute the number of bits necessary to represent a positive integer n. Deduce that
Algorithm 5.1.8, which determines whether an integer is prime, is not a polynomial-time
A bit is a binary
❦
digit, that is, 0 or 1. In digital computers, data and instructions are encoded as
algorithm.
bits. Technology determines how the bits SOLUTION
are physically represented
Suppose that the binary within a computer
representation system.
of the positive k-bit integer n is
Hardware relies on the state of an electronic circuit to represent
n = 1 · 2k−1 a
+ bbit.
k−2 2 The
k−2
+ · · ·circuit
+ b0 20 . must be
capable of being in two states - one representing
Now 1, the other 0.
2k−1 ≤ n
The binary number system represents and
integers using bits (0 and 1). Other important bases
n =octal)
for number systems in computer science are base 8 (or 1 · 2 +and
bk−2 2base
+ ·16 b0 2 hexadecimal).
· · +(or k−1 k−2 0
k−1 k−2
≤ 1 ·2 + 1 ·2 + · · · + 1 · 2 = 2k − 1 < 2k .
0
In hexadecimal, we use digits 0 − 9 and letters A − F representing decimal values 10 − 15
(The last equality follows from the formula for the geometric sum; see Example 2.4.4.)
respectively. Therefore
2k−1 ≤ n < 2k .
In general, in the base N number system, N distinct symbols, representing 0, 1, 2, . . . , N − 1
† Without knowing which number system is being used, a representation is ambiguous; for example, 101101
are required. In representing an integer, reading from
represents one numberthe right,
in decimal thea different
and quite first number
symbol represents
in binary. thewill make clear
Often the context
which number system is in effect; but when we want to be absolutely clear, we subscript the number to specify
number of 1s (i.e., N 0 ), the next symbol the number of N s (i.e., N ), the next symbol the 1
the base—the subscript 10 denotes the decimal system and the subscript 2 denotes the binary system.
number of N 2 s, and so on.
❦
References
1. Johnsonbaugh, R.: Discrete Mathematics - Eighth Edition. Pearson Education, New York
(2018).