English | Español

Try our Free Online Math Solver!

Online Math Solver

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


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 = 22 52.
– 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= p1 p2 … pk, where
the prime factors p1 >sqrt(n), p2 >sqrt(n), …
pk>sqrt(n). Furthermore, since n is a composite,
k≥2. So we have
n= p1 p2 … pk≥ p1 p2 > 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: p1,
p2, …, pn . Now consider
p= p1 p2 … pn +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 = 23 X 3 X 7.
196 = 22 X 72.

• 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 22 X 71 = 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 a1, a2, … an. They are
called pairwise coprime if gcd(ai, aj)=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 = 23 X 3 X 7.
196 = 22 X 72.

• 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 23 X 72 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