Introduction to Elementary Number Theory

Prime

• A positive integer p(>1) is called prime if
the only positive integers that divide p are
1 and p itself .
– A positive integer (>1) that is not a prime is
called composite.
• Example:
– Prime: 2, 3, 5, 7, 11, 13, 17, 19
– Composite: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18

Example prime/composite

• Is 234 prime or composite?
• Is 243 prime or composite?
• Is 245 prime or composite?
• Is 71 prime or composite?

Fundamental theorem of arithmetic

Theorem: Every positive 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.
• Example:
– We can write 100= 2 X 2 X 5 X 5 = 2² 5².
– We can write 241= 241.

More examples

• Apply the fundamental theorem to the
following integers:
625 = ?
891 = ?

Prime factor test

Theorem: If n is a composite, then n has a
prime factor less than or equal to sqrt(n).
Proof: We prove by contradiction. Suppose that n
is a composite and does not have any prime
factor ≤sqrt(n). By the fundamental theorem of
arithmetic, we know that n= p₁ p₂ … p_k, where
the prime factors p₁ >sqrt(n), p₂ >sqrt(n), …
pk>sqrt(n). Furthermore, since n is a composite,
k≥2. So we have
n= p₁ p₂ … p_k≥ p₁ p₂ > sqrt(n) sqrt(n) =n.
Contradiction.

Example for prime factor test

• Show that 71 is a prime.
Proof: We prove by contradiction. If 71 is not
a prime, then 71 must have a prime factor
≤ sqrt(71). However, the only primes ≤
sqrt(71) are 2, 3, 5, 7. Hence, one of these
primes must divide 71. But we can easily
see that none of them divides 71.
Contradiction.

Number of primes

Theorem: There are infinitely many primes.
Proof: We prove by contradiction. Suppose that
there are only a finite number of primes: p₁,
p₂, …, p_n . Now consider
p= p₁ p₂ … p_n +1.
Clearly it is a composite since it is greater than
any of the above n primes. So by the
fundamental theorem of arithmetic, it can be
written as the product of two or more primes .
However, it is easy to verify that any prime pi
cannot divide p since the remainder of the
division is 1. Contradiction.

Greatest common divisor

• Let a and b be integers, not both 0. The
largest integer d such that d|a and d|b is
called the greatest common divisor of a
and b.
– We write d=gcd(a,b).
• Example:
gcd(30, 6)=6 since 6 |30.

Calculating gcd (a,b)

• In general, how can we calculate gcd(a,b)?
– Example: how can we calculate gcd(168, 196) ?
• Step 1: Express a and b as products of powers of
increasing primes.
– Example: 168 = 2³ X 3 X 7.
196 = 2² X 7².

• Step 2: Select the prime divisors a and b have in
common.
– Example: 2 and 7 are the common prime divisors of 168
and 196.

• Step 3: For each of the common prime divisor,
pick the smaller exponent.
– Example: for prime divisor 2, we have exponents 3
(for 168) and 2 (for 196). Hence, we select 2; for
prime divisor 7, we have exponents 1 (for 168) and 2
(for 196). Hence, we select 1.

• Step 4: Calculate the product of the powers of
these common prime divisors, where the
exponents are what we just selected.
– Example: calculate 2² X 7¹ = 28. So gcd(168, 196)=28.

Reading assignment

• Rosen page 229 has the Euclidean
algorithm.
– It allows us to calculate the greatest
common divisor in a much faster way.
– You should read it.

Coprime

• The integers a and b are coprime
(relatively prime) if gcd(a,b)=1.
• Example:
15 and 25 are not coprime since gcd(15,
25)=5.
15 and 24 are not coprime since gcd(15,
24)=3.
15 and 28 are coprime since gcd(15, 28)=1.

Coprime: extended definition

• Consider n integers a₁, a₂, … a_n. They are
called pairwise coprime if gcd(a_i, a_j)=1 for
any i≠j.
• Example:
15, 17, 25 are not pairwise coprime since
gcd(15, 25)=5.
15, 17, 28 are pairwise coprime since
gcd(15, 17)=gcd(15, 28)=gcd(17,28)=1.

Least common multiple

• The least common multiple of positive
integers a and b is the smallest positive
integer that can be divided by both a and b.
– We denote it by lcm (a,b).
• Example:
lcm(30, 6)=30 since 6 |30.

Calculating lcm(a,b)

• In general, how can we calculate lcm(a,b)?
– Example: how can we calculate lcm(168, 196) ?
• Step 1: Express a and b as products of powers of
increasing primes. (Analogous to calculating gcd)
– Example: 168 = 2³ X 3 X 7.
196 = 2² X 7².

• Step 2: Select the prime divisors a and b have in
common. (Analogous to calculating gcd)
– Example: 2 and 7 are the common prime divisors of 168
and 196.

• Step 3: For each of the common prime
divisor, pick the larger exponent.
– Example: for prime divisor 2, we (Different
from calculating gcd) have exponents 3 (for
168) and 2 (for 196). Hence, we select 3; for
prime divisor 7, we have exponents 1 (for 168)
and 2 (for 196). Hence, we select 2.

• Step 4: Calculate the product of the
powers of these common prime divisors,
where the exponents are what we just
selected, and also all primes that only one
of them has. ( Different from calculating
gcd)
– Example: calculate 2³ X 7² X 3 = 1176. So
lcm(168, 196)=1176.

GCD vs. LCM

Theorem: Suppose a and b are positive
integers. Then ab=gcd(a,b) lcm(a,b).
• Example:
gcd(168,196)=28.
lcm(168, 196)=1176.
168 X 196 = 32928 =28 X 1176.
• This tells us that if we can calculate the
gcd, then we can easily get the lcm, and
vice versa.

Homework 7

• Due in Class .
• Rosen 3.4: Questions 20, 24.
• Rosen 3.5: Questions 8, 20, 32.
• Optional Question (Extra credit of 10
points): Suppose S is a set of n positive
integers. Show that S has a non-empty
subset A such that the sum of all elements
of A can be divided by n.