# Intuition — If $k \in \mathbb{Z}$ and $n \ge 2$, then the n$^{th}$ root of k is either an integer or irrational.

Origin — Elementary Number Theory — Jones — p25 — Exercise 2.4

(1) How do you prefigure the answer? Proofwiki start after prefiguring it.

(2) What's the intuition?

This answer delineates the ground plan here for a proof of a disjunction.
First premise that $k^{1/n}$ = $n$th root of $k$ is irrational. Then nothing to prove.

In the second case, premise that $k^{1/n}$ is not irrational. Then I need to prove $k^{1/n}$ is an integer —
One way to prove it is to use exactly the same idea as for proving the square root of 2 is irrational

Suppose $k^{1/n}=p/q$, with p and q integers, relatively prime. Then $\color{brown}{q^nk}=\color{blue}{p^n}.$
Now think about the prime factorizations. Every prime that divides $\color{blue}{p^n}$ must divide $\color{brown}{q^nk}$.
But $p$ and q are coprime. Therefore none of these primes — already dividing $\color{blue}{p^n}$ — can divide $q^n$. Therefore these primes must divide $k$.

Bill Dubuque's answer says to observe from overhead that $\,p^n\mid k\,$ so $\, \color{#0a0}{p^nj = k}$ for some $\color{#0a0}{j \in\Bbb Z}.$ Thence divide g $\,q^nk = p^n\,$ by $\,p^n\,$: $\, q^n (\color{#0a0}{k/p^n}) = q^n\color{#0a0} j = 1\,$ $\Rightarrow$ $\,q^n = 1\,\Rightarrow\,q=1.$

(3) How does $q^n (\color{#0a0}{k/p^n}) = 1 \implies q^n = 1$ ?

Scilicet, $k=p^n \iff k^{1/n} = p$, which I defined $\in \mathbb{Z}$.
That is, the only way for the $k^{1/n}$ to be a rational is if $k = (\text{integer})^n.$

Proofwiki does the opposite. Proofwiki premises $k^{1/n}$ is an integer first, nothing to prove in this case. Then Proofwiki premises $k^{1/n}$ is not an integer and proves $k^{1/n}$ is irrational.

• I clarified my answer. Please ask questions in comments when you seek clarification. – Bill Dubuque Apr 7 '14 at 14:58

## 2 Answers

The quoted proof shows by induction that $\,p^n\mid k\,$ so $\, \color{#0a0}{k/p^n = j}\in\Bbb Z.\,$ So dividing $\,q^nk = p^n\,$ by $\,p^n\,$ yields $\, q^n (\color{#0a0}{k/p^n}) = q^n\color{#0a0} j = 1\,$ $\Rightarrow$ $\,q^n = 1\,\Rightarrow\,q=1.$ Alternatively, one may proceed as follows.

If $\,q>1\,$ it has a prime factor $\,r\,$ so $\ r\mid q\mid q^nk = p^n\,$ $\smash[t]{\overset{\color{#c00}{\rm(EL)}}\Rightarrow}$ $\ r \mid p,\,$ contra $\,p,q\,$ coprime. So $\,q=1.$

The inference  prime $r\mid p^n\,\Rightarrow\, r\mid p\,$ follows by inductively applying Euclid's Lemma $\color{#c00}{\rm(EL)}$ to conclude that if a prime divides a product then it divides some factor.

Euclid's Lemma is essentially equivalent to uniqueness of prime factorizations. As such, the alternative proof also depends crucially on the Fundamental Theorem of Arithmetic (FTA). In domains lacking this property the proof does not work and the statement generally is not true. More generally, it may be proved by the Rational Root Test, so it is true for all domains satisfying that, i.e. all integrally-closed domains (the classical proof that $\,\Bbb Z\,$ satisfies the Rational Root Test immediately generalizes to all unique factorization domains)

• Thank you. Can you please answer my refashioned question (3)? Withal, can you plase answer (1)? Is your last paragraph your answer to (2)? – Dwayne E. Pouiller May 6 '14 at 19:06

Use the rational root test on $x^n - k = 0$.

• If you follow the usual proof for the rational root test and apply it to the polynomial $x^n - k$, you get pretty much the same proof as in the question.. – spin Feb 13 '14 at 15:57
• I'm sorry. How does this answer my questions? – Dwayne E. Pouiller May 6 '14 at 18:56