Prime Factorizations and the Greatest Common Divisor

Divisors From Prime Factorization (DFPF)

Proposition

Let and be positive integers, and let

where are distinct primes, where some or all of the exponents may be zero.

The integer is a positive divisor of if and only if can be represented as a product

The proof is very long and may be included later.

Example

Find all positive divisor of

Observe,
By DFPF, the positive divisors of are integers of the form

Hence, the positive divisors are given by:

Proposition

Let and be positive integers, and let and
Where are distinct primes, and some or all of the exponents may be zero.
We have

Proof

Let and be arbitrary positive integers, where and for distinct primes with for

Let , where for
Then , and since , and , for each
By DFPF, we obtain and . (See divisibility)

Suppose that is such that and . Then by DFPF, is of the form

where (Since ) and (since ).
But this means that for , and hence by FPF we have that . By DIC, we obtain

We conclude, from the definition of GCD, that

Example

Determine by using prime factorizations

Observe that and
Then from GCD PF, we obtain

Note that for large numbers, it if faster and more efficient to use the Extended Euclidean Algorithm