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$
For any integer $ a, b \in \mathbb{Z}$, we can find $ q,r \in \mathbb{R} $ such that:
$$ a = bq + r $$
$ bq + r = r \mod{b} $ \
Note: q, r are unique when $ 0 \leq r \leq b $
Note: when r = 0, b | a
Note: b = 0 $\mod(b)$
( b | a means a can be divided by b)
Example:
a) $ 17 = r (\mod 6) $
a’) Using the divisibility theorem
$ 17 = 2(6) + 5 $
$ \therefore 17 = 5 (\mod 6) \Rightarrow r = 5 $
C can be an addition or multiplication and the divisibility theorem will still work
Example:
$ 32 + 19 (\mod 7)$
$ \equiv 4 + 5 (\mod 7)$
$ \equiv 9 (\mod 7)$
$ \equiv 2 (\mod 7)$
$ 2 (\mod 7) = 51 (\mod 7) $
the gcd(a,b) is the largest $ d \in \mathbb{Z} $ such that d | a and d | b
there is also this div thing: x div y = $ \lfloor \frac{x}{y} \rfloor $