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

58 views2 pages

Published on 23 Oct 2015

School

Department

Course

Professor

MATH 135 - Lecture 22: PAD, UFT, and DFPF

PAD:

● PAD is referred to as a corollary of CAD

● Generalized PAD:

○ If p is prime and p | (m1m2,...,mn) for integers m1, m2,...,mn then p | mi for some

mi {m∈1, 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 a⇒2 | b2

## 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.