NTIC First consequences of the FTA

Section 6.4 First consequences of the FTA

The impact of the FTA is so great, I cannot overstate its significance. This section collates a few examples, but you will see similar ones throughout the text, as well as in the next section, when we connect the theorem back to congruences.

Most importantly, lots of theorems now have reasons, not just proofs. This distinction is an important point about mathematics! The difference boils down to the fact that \(\gcd(a,b)=1\) can be interpreted as saying \(a\) and \(b\) do not share any common prime factors. You will (re)prove a few things in the Exercises 6.6 to try this insight out. Here is a first example to give the feel.

Example 6.4.1.

If \(a\mid c\text{,}\) \(b\mid c\text{,}\) and \(\gcd(a,b)=1\text{,}\) then \(a=\prod p_i\) and \(b=\prod q_j\) but none of the \(p_i\) can be any of the \(q_j\) (or the gcd would include that prime).

Since by the FTA \(c=\prod r_k^{e_k}\text{,}\) where the \(r_k\) are distinct, the \(p_i\) must be some of the collection of \(r_k\)s and the \(q_j\) must be some of the rest, so that \(\prod p_i q_j\) still divides \(c\text{.}\)

So if \(a\mid c\text{,}\) \(b\mid c\text{,}\) and \(\gcd(a,b)=1\text{,}\) then \(ab\mid c\text{,}\) which is part of Proposition 2.4.10.

As another example, the proofs from Section 3.7 become far simpler. We can prove Proposition 3.7.1 here, and save Proposition 3.7.2 for Exercise 6.6.12.

Example 6.4.2.

Let's show that \(a^2\mid z^2\) implies \(a\mid z\text{.}\)

Solution

To begin, let's write \(a=\prod p^e\text{.}\) Then

\begin{equation*} a^2=\prod p^e\cdot \prod p^e = \prod p^{e+e}=\prod p^{2e} \end{equation*}

Similarly,

\begin{equation*} z=\prod q^f \text{ implies }z^2 =\prod q^{2f} \end{equation*}

If these two numbers divide each other, then we can separate the product by each prime, so that for each \(p\text{,}\)

\begin{equation*} p^{2e}\mid q^{2f} \end{equation*}

for some \(q\text{;}\) in fact we must have \(q=p\) for each such case⁴. But then \(p^{2f}=p^{2e}p^{(2f-2e)}\) and this can be viewed as \(2e\leq 2f\text{,}\) so \(e\leq f\) as well.

To be pedantic, the set of prime factors \(q\) of \(z^2\) contains the set of prime factors \(p\) of \(a^2\text{.}\)

This is true for all the primes \(p\) dividing \(a\text{,}\) so \(p^e \mid p^f = q^f\) for all such \(p\text{;}\) multiplying these together shows that

\begin{equation*} a=\prod p^e \mid \prod p^f \mid \prod q^f = z \end{equation*}

as desired.

The reader should note that for such proofs, the implicit use of Corollary 6.3.7 is crucial along with the FTA.

Nearly as important, computing many kinds of things becomes easier. If we let \(a=\prod_{i=1}^n p_i^{e_i}\) and \(b=\prod_{i=1}^n p_i^{f_i}\text{,}\) where it's possible that \(e_i\) or \(f_i\) is zero at times, then we can often get formulas for various combinations of \(a\) and \(b\text{.}\)

Definition 6.4.3.

Given two numbers \(x\leq y\text{,}\) we let the maximum and minimum be defined by

\begin{equation*} \max(x,y)=y\text{ and }\min(x,y)=x \end{equation*}

with an obvious extension to a min or max of a set consisting of more than two numbers.

Then we have formulas of the following kind.

Example 6.4.4.

Product formula:

\begin{equation*} ab=\prod_{i=1}^n p_i^{e_i+f_i} \end{equation*}

Greatest common divisor formula:

\begin{equation*} \gcd(a,b)=\prod_{i=1}^n p_i^{\min(e_i,f_i)} \end{equation*}

Determining a quotient formula, assuming \(b \mid a\text{,}\) is Exercise 6.6.8:

\begin{equation*} a/b=\prod_{i=1}^n p_i^{???} \end{equation*}

Another use of the FTA is to help us do in a systematic way results that were probably first obtained by extremely ad-hoc methods. As an example, it is likely that you have seen a proof that \(\sqrt{2}\) is irrational, and it probably used mostly the concept of “evenness”. But we can prove that \(\sqrt{m}\notin \mathbb{Q}\) (for \(m\) not an integer perfect square) in a very similar fashion.

Most deeply, it gives us a canonical way to describe every integer in terms of simpler integers, and gives a measure of simplicity. We'll exploit this some much later, such as in Chapter 24.

Next are some ways to calculate these concepts in Sage. Simply replace the numbers below with ones you are interested in.

Note that the first of these functions gives just a list of the prime divisors, while the second one gives the full prime power factorization.

Finally, let's note that depending on the context, we might not need the full power of the computational and theoretical tools in this section. To demonstrate that, let's introduce some useful additional notation.

Definition 6.4.5.

For \(p\) prime, we say that \(p^k\parallel n\) precisely when \(p^k\mid n\) but \(p^{k+1}\) does not divide \(n\text{.}\)

Definition 6.4.6.

We write \(n!\) for the product of the integers from \(1\) to \(n\text{,}\) called \(n\) factorial.

Example 6.4.7.

We can demonstrate these by saying \(5^2\parallel 75\) and \(6!=720\text{.}\)

The prime factorization of a number can now separately give useful information about it.

Example 6.4.8.

How many final zeros does twenty factorial have?

Solution

Either by hand or with help, we can see what the biggest powers of \(2\) and \(5\) in \(20!\) are.

Since \(2^{18} \parallel 20!\) and \(5^4\parallel 20!\text{,}\) we can conclude that \(20!\) ends with exactly 4 zeros merely from the prime factorization, which we could certainly get without multiplying it out (though in this case Sage does that first).

We can check this result: