Assiut University

‫قومية‬ ‫كلية‬
‫ل معتمدة من الهيئة ال عتماد‬
‫ضمان جودة التعليم واال‬

Course Title: Discrete Structures

Course Code: CS201

Prof. Dr. Khaled F. Hussain

Introduction to Number Theory
Integers: Z={…-3, -2, -1, 0, 1, 2, 3, …}
Operations: addition, multiplication, subtraction.
Given any two integers a, bZ we can define
a + b Z
a − b Z
a  b Z
Integers Z are closed under operations ‘+’, ‘−’, ‘’.

Closure properties under +, −, : If a, b are integers, then a+b, a −b, a  b are integers.

Commutative Law: If a, b are integers, then a+b=b+a; ab=ba

Associative Law: If a, b are integers, then

a+(b+c) = (a+b)+c
a( bc ) = (ab)c
Introduction to Number Theory (Cont.)
Distributive Law
If a, b are integers, then a(b+c) = ab+ ac

Identity elements for addition and multiplication

For all integer a, a+0=a; a  1= a

Additive inverse
For all integer a, a + (−a) = (−a)+a = 0

Division
If a, b Z, b 0, then it may be that (a / b)  Z, so integers are not closed under division.
Divisibility
• If a and b are integers with a ≠ 0, we say that a divides b if there is an integer c such that b = ac, or
equivalently, if b/a is an integer. When a divides b we say that a is a factor or divisor of b, and that b is a
multiple of a. The notation a | b denotes that a divides b.
• We can express a | b using quantifiers as ∃c(ac = b), where the universe of discourse is the set of integers.

• Example: Determine whether 3 | 7

• 7/3 is not an integer

• Example: Determine whether 3 | 12

• 3 | 12 because 12/3 = 4
Divisibility (Cont.)
Some properties of divisibility
For any a Z :
1) a | 0 because 0= a 0
2) 1 | a because a =1a

For any a, b Z
3) If a | b and b | a, then a = b
4) If a | b and b>0 and a>0, then a  b
5) If mZ, m0, then a | b if and only if (ma)|(mb)
Divisibility (Cont.)
For any a, b, c
THEOREM: If a | b and b | c, then a | c.

Proof.
a | b → b = ax for some xZ (by definition of divisibility)
b | c → c = by for some yZ (by definition of divisibility)
By substitution we have c = (ax)y.
By associative law, c = a(xy).
xy=k is an integer by the closure property of integers under
multiplication.
c = ak means that a | c .
Divisibility (Cont.)
THEOREM : If a | b then a | bc.

Proof
By the definition of divisibility, a | b implies that there is some integer x such that b = ax.
For any integer c, bc = (ax)c = a(xc) by associative property of multiplication.
By the closure property integers under multiplication
xc = k, an integer, so bc =ak, i. e. a | bc
Divisibility (Cont.)
• THEOREM : If a | b and a | c then a | (bx + cy) for any x, y Z
Proof is left as an exercise.
Divisibility (Cont.)
• THEOREM
• THE DIVISION ALGORITHM Let a be an integer and d a positive integer. Then there are unique
integers q and r, with 0 ≤ r < d, such that a = dq + r.
• Note that the remainder cannot be negative.
• In the equality given in the division algorithm, d is called the divisor, a is called the dividend, q is
called the
quotient, and r is called the remainder. This notation is used to express the quotient and
remainder: q = a div d, r = a mod d.
• when a is an integer and d is a positive integer, we have
• a div d = 𝑎/𝑑
• Example: What are the quotient and remainder when 101 is divided by 11?
• We have 101 = 11 ・ 9 + 2.
• the quotient when 101 is divided by 11 is 9 = 101 div 11, and the remainder is 2 = 101 mod 11.
• Example: What are the quotient and remainder when −11 is divided by 3?
• Hence, the quotient when −11 is divided by 3 is −4 = −11 div 3, and the remainder is 1 = −11 mod 3.
• Consequently, the remainder is not −2, even though −11 = 3(−3) − 2, because r = −2 does not satisfy 0 ≤ r < 3.
Modular Arithmetic
• We now introduce a notation that indicates that two integers have the same remainder when they are divided
by the positive integer m.
• DEFINITION: If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m
divides a − b. We use the notation a ≡ b (mod m) to indicate that a is congruent to b modulo m. We say that a
≡ b (mod m) is a congruence and that m is its modulus (plural moduli).
• THEOREM: Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only if a mod
m = b mod m.
• Example: Determine whether 17 is congruent to 5 modulo 6
• Because 6 divides 17 − 5 = 12, we see that 17 ≡ 5 (mod 6).
• Example: Determine whether 24 is congruent to 14 modulo 6
• 24 − 14 = 10 is not divisible by 6, we see that 24 is not congruent to 14 (mod 6).
Arithmetic Modulo m
• We can define arithmetic operations on Zm, the set of nonnegative integers less than m, that is, the set {0, 1, . .
. , m − 1}.
• We define addition of these integers, denoted by +m by a +m b = (a + b) mod m.
• We define multiplication of these integers, denoted by ・m by a ・m b = (a ・ b) mod m.
• Example: find 7 +11 9
• 7 +11 9 = (7 + 9) mod 11 = 16 mod 11 = 5

• Example: find 7 ・11 9

• 7 ・11 9 = (7 ・ 9) mod 11 = 63 mod 11 = 8.
Arithmetic Modulo m (Cont.)
• Closure If a and b belong to Zm, then a +m b and a ・m b belong to Zm.
• Associativity If a, b, and c belong to Zm, then (a +m b) +m c = a +m (b +m c) and (a ・m b) ・m c = a ・m (b ・m
c).
• Commutativity If a and b belong to Zm, then a +m b = b +m a and a ・m b = b ・m a.
• Identity elements The elements 0 and 1 are identity elements for addition and multiplication modulo m,
respectively. That is, if a belongs to Zm, then a +m 0 = 0 +m a = a and a ・m 1 =1 ・m a = a.
• Additive inverses If a ≠ 0 belongs to Zm, then m − a is an additive inverse of a modulo m and 0 is its own
additive inverse. That is a +m (m − a) = 0 and 0 +m 0 = 0.
• Distributivity If a, b, and c belong to Zm, then a ・m (b +m c) = (a ・m b) +m (a ・m c) and (a +m b) ・m c = (a
・m c) +m (b ・m c).
Primes
• An integer p greater than 1 is called prime if the only positive factors of p are 1
and p.
• A positive integer that is greater than 1 and is not prime is called composite.
• Example: the integer 7 is prime because its only positive factors are 1 and 7
• Example: the integer 9 is composite because it is divisible by 3.
Primes (Cont.)
• THEOREM:THE FUNDAMENTAL THEOREM OF ARITHMETIC
• Every integer greater than 1 can be written uniquely as a prime or as the product of two or more primes
where the prime factors are written in order of nondecreasing size.
• Examples:
• 100 = 2 ・ 2 ・ 5 ・ 5 = 2252
• 641 = 641
• 999 = 3 ・ 3 ・ 3 ・ 37 = 33 ・ 37,
• 1024 = 2 ・ 2 ・ 2 ・ 2 ・ 2 ・ 2 ・ 2 ・ 2 ・ 2 ・ 2 = 210.
Primes (Cont.)
• THEOREM: If n is a composite integer, then n has a prime divisor less than or equal to 𝑛.
• Example: Show that 101 is prime
• Solution: The only primes not exceeding 101 are 2, 3, 5, and 7. Because 101 is not divisible by 2, 3, 5, or 7 (the quotient of 101 and
each of these integers is not an integer), it follows that 101 is prime.
Greatest Common Divisors
• DEFINITION: Let a and b be integers, not both zero. The largest integer d such that d | a and d | b is called
the greatest common divisor of a and b. The greatest common divisor of a and b is denoted by gcd(a, b).

• EXAMPLE: What is the greatest common divisor of 24 and 36?

• Solution: The positive common divisors of 24 and 36 are 1, 2, 3, 4, 6, and 12. Hence, gcd(24, 36) = 12.

• EXAMPLE: What is the greatest common divisor of 17 and 22?

• Solution: The integers 17 and 22 have no positive common divisors other than 1, so that gcd(17, 22) = 1.

• DEFINITION: The integers a and b are relatively prime if their greatest common divisor is 1.
• Example: it follows that the integers 17 and 22 are relatively prime, because gcd(17, 22) = 1.
Greatest Common Divisors (Cont.)
Suppose that the prime factorizations of the integers a and b are:
a a
a = p1 1 p2 2 ...pna n b b
b = p1 1 p22 ...pnbn
(ai, bi 0 )

where all primes occurring in either factorization are included in

both factorizations with zero exponent if necessary.
Then min( a ,b ) min( a ,b )
gcd( a, b) = p1 p2
1 1
...pnmin( a ,b )
2 2 n n

Example: Find gcd(120, 500) using prime factorization.

We have 120 =23 ×3 ×5 and 500=22 ×53 , then
gcd(120, 500)= 2min(3, 2) ×3min(1, 0) ×5min(1, 3) =22 ×30 ×51=20.
Least common multiple
• The least common multiple of two integers:

max( a1 ,b1 ) max( a 2 ,b2 )

lcm( a, b) = p1 p2 ...pnmax( a n ,bn )
• Lemma. For any two integers x and y we have: x + y = max(x, y)+min(x, y)

• Theorem. For any two integers a and b ab = gcd (a, b) lcm(a, b)

a a a b b b
a  b = ( p1 1  p2 2  ... pk k )  ( p1 1  p22  ... pkk )

a + b1 a + b2 a + bk
= p1 1  p2 2  ...  pk k

max( a1 ,b1 ) + min( a1 ,b1 ) max( a k ,bk ) + min( a k ,bk )

= p1  ...  pk

min( a1 ,b1 ) min( a k ,bk ) max( a1 ,b1 ) max( a k ,bk )

= ( p1  ...  pk )( p1  ...  pk )
What is the lcm(120, 500)?
120500 = 23+23151+3
= gcd(120, 500) lcm(120, 500)
= 22 30 51lcm(120, 500)

lcm(120, 500)= 233153= 3000

The Euclidean Algorithm
• We will discuss an efficient method of finding the greatest common divisor, called the Euclidean algorithm.
• Let a = bq + r, where a, b, q, and r are integers. Then gcd(a, b) = gcd(b, r).
• Example: find gcd(91, 287)
• 287 = 91 ・ 3 + 14.
• Any divisor of 91 and 287 must also be a divisor of 287 − 91 ・ 3 = 14.
• Any divisor of 91 and 14 must also be a divisor of 287 = 91 ・ 3 + 14
• gcd(91, 287) = gcd(91, 14).
• 91 = 14 ・ 6 + 7.
• gcd(91, 14) = gcd(14, 7)
• gcd(14, 7) = 7
• gcd(91, 287) = 7
The Euclidean Algorithm
• Example: Consider computing gcd(125, 87)

125 = 1*87 + 38
= 2*38 + 11
= 3*11 + 5
11 = 2*5 + 1
= 5*1

• Thus, we find that gcd(125,87) = 1.

The Euclidean Algorithm
• Example: gcd(125, 20)

125 = 6*20 + 5
= 4*5,

Thus, the gcd(125,20) = 5

The Euclidean Algorithm (Cont.)
Proof: It is sufficient to prove that set of common divisors of a and b is equal to the set of common divisors
of b and r.

Let d be a common divisor of a and b.

a=a’d
b=b’d
r=a-bq =d(a’-b’q) , i. e. d is also a divisor of r.

Let f be a common divisor of b and r

a = bq + r =f(b’q+r’) i. e. f is also a divisor of a .
The Euclidean Algorithm (Cont.)
• Find the greatest common divisor of 414 and 662 using the Euclidean algorithm
• 662 = 414 ・ 1 + 248
• 414 = 248 ・ 1 + 166
• 248 = 166 ・ 1 + 82
• 166 = 82 ・ 2 + 2
• 82 = 2 ・ 41.
• Hence, gcd(414, 662) = 2, because 2 is the last nonzero remainder
The Euclidean Algorithm (Cont.)
procedure gcd(a, b: positive integers)
x := a
y := b
while y = 0
r := x mod y
x := y
y := r
return x{gcd(a, b) is x}
Theorem
• Theorem: An integer solution (x , y) of equation ax + by =c exists if and only if c is divisible by gcd(a, b).
• To find integer solution of an equation ax+by=c, we need to check first, that gcd(a, b) divides c.

For example, to find integer solution for 85x +34y = 51, find the gcd(85, 34) using Euclid Algorithm:
85=342+17
34= 172
So, gcd(85, 34)=17.
Since 17|51 a solution exists

Find the integers u, v in gcd(a, b)=au+bv.

17 = 85 − 342,  u = 1, v = −2.
By multiplying by 3 we find:
51=853+34 (−6),
i. e. x =3, y = −6 is a solution.
• Other integer solutions
51= 85×x+34×y
17 = 85×u +34×v
1= 5u +2v
1=5(u−2k) +2(v+5k) where k is any integer.
17= 85(u−2k)+34(v+5k)
51 = 85(x −6k) + 34(y+15k)

• So, if a solution (x, y) exists, then there are infinitely many solutions (x −6k, y+15k), k is any integer.