# 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^{2} 5^{2}.

– 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_{1} p_{2} … p_{k}, where

the prime factors p_{1} >sqrt(n), p_{2} >sqrt(n), …

pk>sqrt(n). Furthermore, since n is a composite,

k≥2. So we have

n= p_{1} p_{2} … p_{k}≥ p_{1} p_{2} > 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_{1},

p_{2}, …, p_{n} . Now consider

p= p_{1} p_{2} … 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^{3} X 3 X 7.

196 = 2^{2} X 7^{2}.

• 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^{2} X 7^{1} = 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_{1}, a_{2}, … 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^{3} X 3 X 7.

196 = 2^{2} X 7^{2}.

• 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^{3} X 7^{2} 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.

Prev | Next |