Skip to main content
Logo image

Section 3.7 Two facts from the gcd

Here are two facts that seem really obvious but do need proofs. All can be done just with the gcd, using no facts about primes from Chapter 6 as would typically be done. Kudos go to users Math Gems
and coffeemath
for most of these clever arguments. See this question
for Proposition 3.7.1 and this question
for Proposition 3.7.2.


First, let \(d=\gcd(a,z)\text{.}\) Then we can write \(z^2=a^2 \cdot k\) for some integer \(k\text{,}\) and immediately write
\begin{equation*} (z')^2 d^2=(a')^2 d^2 k \end{equation*}
for some integers \(z'\) and \(a'\text{,}\) by definition of gcd. (That is, \(z=z'd\) and \(a=a'd\text{.}\) Also note that \(z',a'\) are now relatively prime; it is not hard to prove using the techniques of the previous chapter, or see Exercise 6.6.7.)
Cancelling the \(d^2\) (yes, we do assume this property of integers) yields
\begin{equation*} (z')^2=(a')^2 k\text{.} \end{equation*}
Since \(\gcd(a',z')=1\text{,}\) we have \(a'x+z'y=1\) for some \(x,y\in\mathbb{Z}\text{;}\) now we substitute for \(1\) in \(a'\cdot 1\cdot x\) (!) to get
\begin{equation*} a'(a' x+z'y)x+z'y=1 \end{equation*}
Now we have that \(a'^2 x^2+z'(a'xy+y)=1\text{,}\) so that \(\gcd((a')^2,z')=1\) as well. But of course \(a'\mid (z')^2\text{.}\) Clearly if a positive number is a divisor, but their greatest common divisor is 1, then that number is going to have to be 1 by definition of divisors. So \(a'=1\text{.}\) (If \(a'\) was negative, the same argument for \(-a'\) shows \(-a'=1\text{,}\) so really \(a'=\pm 1\text{.}\))
Hence \(a=a'd=\pm d\text{,}\) which is a divisor of \(z\text{,}\) we have the desired result.


First, we will need a general fact about gcds:
\begin{equation*} \gcd(x,y)^2=\gcd(x^2,xy,y^2) \end{equation*}
We know that \(1=\gcd(m,n)=\gcd(m,n,j)\text{,}\) so
\begin{equation*} m = m\cdot \gcd(m,n,j)=\gcd(m^2,mn,mj)=\gcd(m^2,j^2,mj) \end{equation*}
Now we use the fact, so that
\begin{equation*} m=\gcd(m,j)^2\text{.} \end{equation*}
That’s a perfect square.
The same argument with \(n\) and \(j\) yields \(n = \gcd(n,j)^2\text{.}\)
(For more ‘traditional’ proofs, see Section 6.4.)