Discrete Structures

Lecture 9
Elementary Number Theory
Today's Lecture

• Divisors
• Prime Numbers
• Fundamental Theorem of Arithmetic
• Division Algorithm
• Greatest common divisors
• Least Common Multiple
• Relative Prime
Divisors
DEF: Let a, b and c be integers such that

a = b·c
Then b and c are said to divide (or are factors) of a,
while a is said to be a multiple of b (as well as of c). The
pipe symbol “|” denotes “divides” so the situation is
summarized by b | a  c | a.
NOTE: Symbolically if a and b are integers and k is not
equal to zero,
b | a   an integer such a b k
Examples
Which of the following is true?
1. 77 | 7
2. 7 | 77
3. 24 | 24
4. 0 | 24
5. 24 | 0
Solution
1. 77 | 7: false bigger number can’t divide smaller
positive number
2. 7 | 77: true because 77 = 7 · 11
3. 24 | 24: true because 24 = 24 · 1
4. 0 | 24: false,
5. 24 | 0: true, 0 is divisible by every number (0=24·0)
Formula for Number of Multiples up to given N
How many positive multiples of 15 are less than 100?
Answer: Just list them

15, 30, 45, 60, 75, 90.

Therefore the answer is 6.

How many positive multiples of 15 are less than

1,000,000?
Cont…
Listing is too much of a hassle. Since 1 out of 15
numbers is a multiple of 15, if 1,000,000 were divisible
by 15, answer would be exactly 1,000,000/15.
However, since 1,000,000 isn’t divisible by 15, need to
round down to the highest multiple of 15 less than
1,000,000, so answer is remainder of 1,000,000/15
In general: The number of d-multiples less than N is
given as: {m  Z+ | d |m and m  N }.
Divisor Theorems
Theorem: Let a, b, and c be integers. Then
1. Divisibility by Sum

• a | b  a| c  a|(b + c )

2. Multiplicative Property of Divisibility

• a| b  a| b.c
3. Transitive Property of Divisibility

• a| b  b| c  a| c. (Transitive Property)
Examples
17|34  17|170  17|204.
17|34  17|340.
6|12  12|144  6|144.
Proof of the Theorem
In general, such statements are proved by starting
from the definitions and manipulating to get the desired
results.

1.a | b  a| c  a|(b + c )
Suppose a|b and a|c then by definition, there is a
number m such that b = a·m and there is a number n
such that c = a·n. So by adding b and c we get b+c =
am+an = a(m+n)=a·k. So b+c = a·k so by definition of
“|”, we will get that a|(b+c).
Cont….
2. a| b → a| b∙c
Suppose a|b. By definition, there is a number m such
that b = a·m. Multiply both sides by c to get b∙c =
a·m·c = a∙(m∙c ). Consequently, b∙c has been
expressed as a times the integer m∙c so by
definition of “|”, a|b∙c.
3. a| b  b| c → a| c
Suppose a|b. By definition, there is a number m such
that b = a∙m and b|c means there is a number k
such that c=b∙k. putting the value of b = a∙m in c =
b∙k, we will get c = (a∙m)∙k =a∙(m∙k)=a∙n, where
n=m∙k. so by definition of “|”, a|c. We call that
property of the divisibility Transitive Property.
Definitions
• An integer n is even if, and only if, n=2.k for some
integer k.
• An integer n is odd if and only if, n=2k+1 for some
integers k.
• An integer n is prime if and only if n > 1 and for all
positive integers r and s, if n=r.s, then r=1 or s=1.
• An integer n is composite if and only if n=r.s for
some positive integers r and s with r not equals to 1
and s not equals 1.
Prime Numbers
DEF: A number n  2 is prime if it is only divisible by 1
and itself. A number n  2 which isn’t prime is called
composite.

Which of the following are prime?

0,1,2,3,4,5,6,7,8,9.
Answer: 0, and 1 not prime since not positive and greater or
equal to 2.
2 is prime as 1 and 2 are only factors.
3 is prime as 1 and 3 are only factors.
4,6,8,10 not prime as non-trivially divisible by 2.
5, 7 prime.
9 = 3 · 3 not prime.
Last example shows that not all odd numbers are prime.
Fundamental Theorem of Arithmetic
Statement: Any number n  2 is expressible as a
unique product of 1 or more prime numbers.
(Note: prime numbers are considered to be “products” of 1 prime.
We’ll need induction and some more number theory
tools to prove this).

Example
Express each of the following number as a product of
primes: 22, 100, 12, 17.
Answer: 22 = 2·11, 100 = 2·2·5·5, 12 = 2·2·3, 17 = 17
Cont…
The prime factorizations of 100, 641, 999, and 1024
are given by
Sol: 100 = 2*2*5*5.
641 = 641.
999 = 3*3*3*3*7.
1024 = 2*2*2*2*2*2*2*2*2*2.
Cont….
Example: Test if 139 and 143 are prime.
139≈11.79. So we only need to test for prime divisors up to 11 (2, 3, 5, 7, and
11).
1.Check divisibility:
2: 139 is odd, so it’s not divisible by 2.
3: The sum of the digits 1+3+9=13, which is not divisible by 3.
5: 139 does not end in 0 or 5, so it’s not divisible by 5.
7: Divide 139÷7=19.857, which is not an integer, so it’s not divisible by 7.
11: Divide 139÷11=12.63613, which is not an integer, so it’s not divisible
by 11.
Since 139 is not divisible by any prime number up to 139\sqrt{139}139​, 139 is
prime
STOP! Next prime 13 need not be examined since
bigger than
Conclude: 139 is prime, 143 is composite.
Find 143≈11.96. So we only need to test for prime divisors up to 11 (2,
3, 5, 7, and 11).
Check divisibility:
2: 143 is odd, so it’s not divisible by 2.
3: The sum of the digits 1+4+3=8, which is not divisible by
5: 143 does not end in 0 or 5, so it’s not divisible by 5.
7: Divide 143÷7=20.428, which is not an integer, so it’s not divisible by
7.
11: Divide 143÷11=13, which is an integer, so 143 is divisible by 11.

16
Division
Remember long division?

q the

d the divisor 3 quotient

31 117
a the
93 r the remainder
dividend
24

117 = 31·3 + 24
a = d∙q + r
Division Algorithm
Let a be an integer, and d be a positive integer. There
are unique integers q, r with r  {0,1,2,…,d-1} satisfying

a = d∙q + r
The proof is a simple application of long-division. This
is called the division algorithm.
Example
What are the quotient and remainder when -11 is
divided by 3?
Solution: We have -11=3(-4)+1.Hence, the quotient
when -11 is divided by 3 is -4 = -11 div 3, and the
remainder is 1 = -11 mod 3.
Note that the remainder cannot be negative.
Consequently, the remainder is not -2, even though
-11 = 3(-3) - 2,
because r = -2 does not satisfy 0 < r < 3.
Note that the integer a is divisible by the integer d if and
only if the remainder is zero when a is divided by d.
Greatest Common Divisor
DEF: Let a, b be integers, not both zero. The greatest
common divisor (or HCF) of a and b (or gcd
(a , b) ) is the biggest number d which divides
both a and b.
Equivalently: gcd(a,b) is smallest number which divides
any x dividing both a and b.

DEF: a and b are said to be relatively prime if

gcd(a,b) = 1, so no prime common divisors.
Example:
Find the following gcd’s:
1. gcd(11,77)
2. gcd(33,77)
3. gcd(24,36)
4. gcd(24,25)
Answer
1. gcd(11,77) = 11
2. gcd(33,77) = 11
3. gcd(24,36) = 12
4. gcd(24,25) = 1. Therefore 24 and 25 are relatively
prime.
NOTE: A prime number is relatively prime to all other
numbers which it doesn’t divide.
Examples
Pair-wise relatively prime: The numbers a, b, c, d, …
are said to be pair-wise relatively prime if any two
distinct numbers in the list are relatively prime.

Question: Find a pair-wise relatively prime subset of

{ 44, 28, 21, 15, 169, 17 }
Answer: A maximal pair-wise relatively prime
subset of {44, 28, 21, 15, 169, 17} :
{17, 169, 28, 15} is one answer.
{17, 169, 44, 15} is another answer.
Least Common Multiple
The least common multiple of a, and b (or lcm(a,b) ) is
the smallest number m which is divisible by both a and
b.
Equivalently: lcm(a , b) is biggest number which divides
any x divisible by both a and b.
Find the lcm’s:
1.lcm(10,100)
2.lcm(7,5)
3.lcm(9,21)
Answer
1.lcm(10,100) = 100
2.lcm(7,5) = 35
3.lcm(9,21) = 63
L.C.M in terms of G.C.D
Theorem: lcm(a,b) = (a∙b) / gcd(a,b),
Proof. Let g = gcd(a,b). Factor a and b using g: a = g.x, b
= g.y where x and y are relatively prime. Therefore,
a.b/gcd(a,b) = (g.x.g.y)/g = g.x.y. Notice that a and b
both divide g.x.y. On the other hand, let m be divisible
by both a and b. So m/g is divisible by both x and y. As
x and y have no common prime factors, the fundamental
theorem of arithmetic implies that m/g must be divisible
by x.y.
Cont…

m/g must be divisible by x·y. Therefore, m must

be divisible by g.x.y. This shows that any
multiple of a and b is bigger than g.x.y so by
definition, g.x.y = a.b/gcd(a,b) is the lcm.
Example
lcm(10,15)=30, gcd(10,15)=5,
(10*15)/5=30.
Importance of Number Theory
Before the dawn of computers, many viewed
number theory as last bastion of “pure math”
which could not be useful and must be enjoyed
only for its aesthetic beauty.
No longer the case. Number theory is crucial
for encryption algorithms. Of utmost importance
to everyone from Bill Gates, to the CIA, to
Osama Bin Laden.
Check out Angelos Keromytis's lecture---
www.cs.columbia.edu/~angelos/teaching/lecture8/index.html
---from COMS 4180 “Network Security” in which
he applies number theory to encryption.
Lecture Summary

• Divisors
• Prime Numbers
• Fundamental Theorem of Arithmetic
• Division Algorithm
• Greatest common divisors.
• Least Common Multiple
• Relative Prime