# MATH135 Lecture Notes - Lecture 22: Integer Factorization, If And Only If

58 views2 pages MATH 135 - Lecture 22: PAD, UFT, and DFPF
If p is prime and p | (m1m2,...,mn) for integers m1, m2,...,mn then p | mi for some
mi {m1, m2,...,mn}
Recall Prime Factorization (PF)
Infinitely Many Primes (INF P)
There are an infinite number of primes
Unique Factorization Theorem (UFT):
Also known as the Fundamental Theorem of Arithmetic
If n > 1 is an integer, then n can be written as a product of prime factors and, apart from
the order of factors, this factorization is unique
Divisors from Prime Factorization (DFPF):
Let n > 1 be an integer and d . If n = p∈ ℕ 1a1p2a2...pmam is the unique prime factorization of
n into powers of distinct primes p1,p2,...,pm, where the integers a1,a2,...,am ≥ 1, then d is a
positive divisor of n if and only if a non-unique prime factorization of d is given by
d = p1d1p2d2...pkdk where 0 ≤ di ≤ ai for i = 1, 2,...,k
Ex. 1 Find the divisors of 63
63 = 32 * 7
So its divisors are:
30 * 70 = 1 31 * 71 = 21
30 * 71 = 7 32 * 70 = 9
31 * 70 = 3 32 * 71 = 63
The number of divisors is determined by the exponent on each unique factor (ie. 3 and 7
and raised to the powers of 2 and 1, respectively)
So 63 has (2 + 1) (1 + 1) = 6 divisors
Ex. 2 How many multiples of 12 are divisors of 2940?
2940 = 22 * 3 * 5 * 72
12 = 22 * 3
We consider negative divisors as well as positive divisors, so 2 * (1 + 1) (2 + 1) = 12
divisors of 2940 are multiples of 12
Ex. 3 Prove that a2 | b2 iff a | b
Proof:
( ) Assume a | b, so b = ka for some k ∈ ℤ
b2 = (ka)2 = k2a2
Since k , then k∈ ℤ 2 , so a∈ ℤ 2 | b2
( ) Assume a2 | b2
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

## Document Summary

Math 135 - lecture 22: pad, uft, and dfpf. Pad is referred to as a corollary of cad. If p is prime and p | (m1m2,,mn) for integers m1, m2,,mn then p | mi for some mi. There are an infinite number of primes. Also known as the fundamental theorem of arithmetic. If n > 1 is an integer, then n can be written as a product of prime factors and, apart from the order of factors, this factorization is unique. The number of divisors is determined by the exponent on each unique factor (ie. 3 and 7 and raised to the powers of 2 and 1, respectively) So 63 has (2 + 1) (1 + 1) = 6 divisors. We consider negative divisors as well as positive divisors, so 2 * (1 + 1) (2 + 1) = 12 divisors of 2940 are multiples of 12. 3 prove that a2 | b2 iff a | b.