Try our Free Online Math Solver!

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 da and db 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 nonempty
subset A such that the sum of all elements
of A can be divided by n.
Prev  Next 