Finding Prime Factorization

Example: find the prime factorization of 477,000

You divide the value by the smallest prime numbers until you get a prime number.

Divide by 2 repeatedly: $477,000 / 2^3 = 59625$ / Divide by 3 repeatedly: $59625 / 3^2 = 6625 $ / Divide by 5 repeatedly: $6625 / 5^3 = 53 $ / 53 is a prime number

Therefore, the prime factorization of 477,000 is: $ 2^3 \cdot 3^2 \cdot 5^3 \cdot 53$

The Divisibility Theorem

For any integer $ a, b \in \mathbb{Z}$, we can find $ q,r \in \mathbb{R} $ such that:

$$ a = bq + r $$

*Note: q, r are unique when $ 0 \leq r \leq b $
*Note: when r = 0, b | a
( b | a means a can be divided by b)

The Euclidean Theorem

the gcd(a,b) is the largest $ d \in \mathbb{Z} $ such that d | a and d | b