Here is an elementary proof (adapted from Hardy's A Course of Pure Mathematics) that for any integer $k$, $\sqrt{k}$ is either irrational or integral.

  1. Suppose $\sqrt{k}$ is rational, $\sqrt{k} = \frac{m}{n}$, $m$ and $n$ have no common factor.
  2. Then $m^2=kn^2$
  3. Every factor of $m^2$ must divide $kn^2$
  4. As $m$ and $n$ have no common factor, every factor of $m^2$ must divide $k$
  5. Hence $k = \lambda m^2,$ $\lambda \in \mathbb{Z}$
  6. Hence $1 = \lambda n^2 \rightarrow \lambda = n = 1$
  7. Hence $k=m^2$

So $\sqrt{k}$ is either irrational or integral.


My question regards one step in this proof, present here and also in Hardy's proof - step 4. We conclude that, because $m$ and $n$ have no common factors, all of $m^2$'s factors must be factors of $k$ - because none of them could be factors of $n^2$. We've subtly used the 'fact' here that:

The relative primality of $m$ and $n$ implies the relative primality of $m^2$ and $n^2$

And this is where I am concerned, because I can't quite pinpoint why this must be true. Further, this statement we have assumed as 'obvious' is as strong as the whole proof. Indeed, a weak form of the the contrapositive is:

If $m^2 = kn^2, k\in\mathbb{N}$ then $m$ and $n$ have a common factor.

And straight from this, if $k$ is not a perfect square then $\sqrt{k}$ is irrational.

This is my problem - I cannot see why the first statement highlighted above must be true. Of course, it is obvious from the fundamental theorem of arithmetic, but the whole proof is obvious from the fundamental theorem of arithmetic!

How could you prove the first highlighted statement above without FTOA?

Thank you very much :)

  • 1
    $\begingroup$ I fear I must learn some more algebra, but thanks for the help all :D $\endgroup$
    – tom
    Jul 7, 2012 at 6:26

5 Answers 5


That's a perceptive observation. In fact the proof works in domains more general than UFDs, e.g. it follows from the monic case of the Rational Root Test, i.e. it works in all integrally-closed domains, which are far from being UFDs. But let's looks closer at the specific proof you give. It employs $\rm\:(m,n)=1\:\Rightarrow\:(m^2,n^2)=1.\:$ This follows from a special case of Euclid's Lemma, viz. $\rm\:(a,b) = 1 = (a,c)\:$ $\Rightarrow$ $\rm\:(a,bc)=1.\:$ Namely,$\rm\: a=m,\,b=n=c\:$ yields $\rm\:(m,n^2)=1.\:$ Finally $\rm\:a=n^2,\,b = m = c\:$ yields $\rm\:(m^2,n^2) = 1.$

This special case of Euclid's Lemma holds true in any GCD domain, in particular in any UFD or any Bezout domain. But it is weaker, i.e. there are domains satisfying this identity which are not GCD domains, i.e. where some elements have no gcd. In fact this is equivalent to Gauss' Lemma, that the product of primitive polynomials is primitive (or the special case for degree $1$ polynomials). Indeed if $\rm\:(m,n)=1\:$ then $\rm\:m\,x\pm n\:$ is primitive, thus so is $\rm\:(m\,x-n)\,(m\,x+n) = m^2\, x - n^2,\:$ hence $\rm\:(m^2,n^2) = 1.\:$ Below is an excerpt of my sci.math post on 2003/5/3 (see here or here) which shows the relationships between various domains closely related to GCD domains. If you wish to understand precisely the class of rings satisfying such properties then see the links in said post, and also google "root-closed" domains.

There has been much study of domains related to GCD domains. Below are some of them, in increasing order of generality.

PID: $\ \ $ every ideal is principal

Bezout: $\ \ $ every ideal (a,b) is principal

GCD: $\ \ $ (x,y) := gcd(x,y) exists for all x,y

SCH: $\ \ $ Schreier = pre-Schreier & integrally closed

SCH0: $\ \ $ pre-Schreier: a|bc $\, \Rightarrow\, $ a = BC, B|b, C|c

D: $\ \ $ (a,b) = 1 & a|bc $\,\Rightarrow\,$ a|c

PP: $\ \ $ (a,b) = (a,c) = 1 $\,\Rightarrow\,$ (a,bc) = 1

GL: $\ \ $ Gauss Lemma: product of primitive polys is primitive

GL2: $\ \ $ Gauss Lemma holds for all polys of degree 1

AP: $\ \ $ atoms are prime [AP = PP restricted to atomic a]

enter image description here

Since atomic & AP $\,\Rightarrow\,$ UFD, reversing the above UFD $\,\Rightarrow\,$ AP path shows that in atomic domains all these properties (except PID, Bezout) collapse, becoming all equivalent to UFD.

There are also many properties known equivalent to D, e.g.

[a] $\ \ $ (a,b) = 1 $\,\Rightarrow\,$ a|bc $\,\Rightarrow\,$ a|c

[b] $\ \ $ (a,b) = 1 $\,\Rightarrow\,$ a,b|c $\,\Rightarrow\,$ ab|c

[c] $\ \ $ (a,b) = 1 $\,\Rightarrow\,$ (a)/\(b) = (ab)

[d] $\ \ $ (a,b) exists $\,\Rightarrow\,$ lcm(a,b) exists

[e] $\ \ $ a + b X irreducible $\,\Rightarrow\,$ prime for b $\ne$ 0 (deg = 1)

  • $\begingroup$ That is a nice classification. There is a class I find missing: as you know, a domain is PSP if all primitive polynomials are superprimitive, and we have preSchreier $\Rightarrow$ PSP $\Rightarrow$ GL. Do you know which is the relation between PSP and D? $\endgroup$
    – Jose Brox
    Nov 5, 2020 at 18:35

See my paper, Irrationality via well-ordering, Gazette of the Australian Mathematical Society 35 (2008) 121–125, available here, for proofs without unique factorization and some history.

  • 1
    $\begingroup$ It is misleading to label these classical proofs "via well-ordering". Rather, the proofs depend crucially on a domain D being Euclidean. This requires not only a "size" map from D into a well-ordered set, but also, crucially, a Division Algorithm with respect to the map. Euclideaness is used implicitly in your proofs when you take the integer or fractional part of a fraction, to help achieve a descent on possible denominators for $\rm\:w = \sqrt{m}\:$ (or w an algebraic integer). See my posts in this May 19, 2009 sci.math thread for much more on these topics. $\endgroup$ Jun 29, 2012 at 14:20
  • 1
    $\begingroup$ @Bill, when you fly from New York to San Francisco via Denver, your flight depends crucially on burning jet fuel; is it misleading to label the journey as "via Denver"? In any event, OP asked about proofs without FTA, and I trust you are not disputing that these proofs qualify. $\endgroup$ Jun 29, 2012 at 23:05

Bezout's identity says that two integers $m, n$ are relatively prime if and only if we can find integers $a, b$ such that $$am + bn = 1.$$

Squaring this identity gives $$a^2 m^2 + 2amn + b^2 n^2 = (a^2m - 2an)m + b^2 n^2 = 1$$

from which we conclude that $\gcd(m, n^2) = 1$. Squaring again gives $\gcd(m^2, n^2) = 1$.

Note that Bezout's identity is often used as a crucial step in the proof of unique factorization. It is very close to the claim that $\mathbb{Z}$ is a principal ideal domain, and it's straightforward to prove that any principal ideal domain has unique factorization.

More generally, in situations where greatest common divisors don't always exist, Bezout's identity is taken to be the definition of being relatively prime.


There is an interesting fact, a "common refinement", which is related to unique factorization:

Suppose $ab=cd$. Then there exist $p,q,r,s$ so that $ab=pqrs=cd$, with $a=pq$, $b=rs$, $c=pr$, $d=qs$.

  • 3
    $\begingroup$ Though it is much older, this is sometimes called Euler's Four Number Theorem (Vierzahlensatz). It is equivalent to the pre-Schreier property in my answer. See this answer for further discussion on this and closely related properties. $\endgroup$ Jan 5, 2017 at 15:19

To justify the first highlighted statement, it is helpful to keep in the back of your mind that:
If $c | ab$; then $c | a$ or $c | b$ (or both). This should have been proven as a lemma prior to handling the irrationality theorems. [I would imagine that Hardy does this or something equivalent, even if only in passing.]

Since $m$ and $n$ are co-prime, $m\!\! \not | n$ and vice-versa.

Now for contradiction, assume that $n|m^2$. Letting $n=c$ and $m=a=b$ in the lemma, $n$ would have to divide $m$ since $c|ab \implies c|a \lor c|b$. But that is impossible since $m$ and $n$ are relatively prime.

So we have $m$ relatively prime to $n^2$ and (by a similar argument) $n$ relatively prime to $m^2$.

Now, if $n^2 | m^2$, then by the lemma, $n^2|m$. But since $n \!\! \not |m$, we cant have $n|m^2$. (Nor, by the same argument the other way.)

So $m$ and $n$ being co-prime implies that $m^2$ and $n^2$ are co-prime, too.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.