To prove that $S$ has an upper bound in $L$, we will use Zorn’s lemma. Let $T$ be the set of all chains in $L$ that are contained in $S$, and let $C$ be a chain in $T$. We want to show that $C$ has an upper bound in $L$.

Since $C$ is a chain in $L$, we know that $(C, \leq)$ is a partially ordered set. Let $c$ be an upper bound for $C$ in $L$. We claim that $c$ is also an upper bound for $S$.

Suppose for the sake of contradiction that $c$ is not an upper bound for $S$. Then there exists some $s \in S$ such that $s \nleq c$. Since $S \subseteq C$, we know that $s \in C$. Since $c$ is an upper bound for $C$, we have $s \leq c$. This contradicts the assumption that $s \nleq c$, so our claim is proven.

Therefore, $c$ is an upper bound for $S$. To complete the proof, we need to show that $c$ is in fact an element of $L$. Since every countable chain in $L$ has an upper bound, we know that $L$ is a complete partial order. In particular, every chain in $L$ has a least upper bound (lub).

Let $D$ be the set of all upper bounds of $S$ in $L$. We want to show that $c = \operatorname{lub}(D)$, which will complete the proof. First, we show that $c$ is an upper bound of $S$. We have already shown this above.

Now, let $d$ be an upper bound of $S$ in $L$. We want to show that $c \leq d$. By definition of $D$, we have $c \in D$, so $c$ is an upper bound of $S$. Therefore, we have $c \leq d$, since $d$ is also an upper bound of $S$.

Finally, we need to show that $c$ is the least upper bound of $D$. Suppose for the sake of contradiction that there exists some $d’ \in L$ such that $d’ < c$ and $d’$ is an upper bound of $D$. Since $c$ is an upper bound of $D$, we have $d’ \leq c$. But this contradicts the assumption that $c$ is the least upper bound of $D$. Therefore, $c$ must be the least upper bound of $D$.

We have now shown that $S$ has an upper bound in $L$. Therefore, by definition of a complete partial order, $L$ has a least upper bound for $S$, which completes the proof.

First, let’s assume that $\sqrt[k]{n}$ is rational. This means that there exists some integers $a$ and $b$ such that $\sqrt[k]{n}=\frac{a}{b}$, where $b\neq 0$. Raising both sides to the $k$-th power gives us $n=\frac{a^k}{b^k}$, which can be written as $nb^k=a^k$. This shows that $a^k$ is a multiple of $b^k$, which implies that $a$ must be a multiple of $b$. Let $a=cb$ for some integer $c$. Then we have $n=cb^k$, which can be written as $n=(b^{k-1}c)^k$. Therefore, $n$ is of the form $d^k$ for some integer $d=b^{k-1}c$.

Now let’s assume that $n=d^k$ for some integer $d$. We can write $d$ as $d=be$, where $b$ is the largest integer such that $b^k$ divides $d^k$, and $e$ is some integer. Then $n=d^k=(be)^k=b^ke^k$. Since $b$ is the largest integer such that $b^k$ divides $d^k$, $e$ is not divisible by $b$. Therefore, $b$ and $e$ are relatively prime. This implies that $b^k$ and $e^k$ are also relatively prime. Thus, $n=b^ke^k$ is in its simplest form as a product of relatively prime integers, and its $k$-th root is $\sqrt[k]{n}=e\in \mathbb{Z}$. Therefore, $\sqrt[k]{n}$ is rational.

Combining the two directions of the proof, we have shown that for all nonnegative integers $n \geq 0$ and $k>1$, $\sqrt[k]{n}$ is rational if and only if $n=d^k$ for some integer $d$.

Let $s=\sqrt{p}+\sqrt{q}+\sqrt{r}$.

Squaring both sides, we get:

$$s^2=p+q+r+2\sqrt{pq}+2\sqrt{qr}+2\sqrt{rp}$$

Since $s$ is rational, $s^2$ is also rational. Thus, $\sqrt{pq}$, $\sqrt{qr}$, and $\sqrt{rp}$ must be rational.

Suppose, for contradiction, that $p$ is not a perfect square. Then, $\sqrt{p}$ is irrational, and $\sqrt{q}+\sqrt{r}=s-\sqrt{p}$ is also irrational.

But this implies that $\sqrt{pq}$ and $\sqrt{qr}$ are irrational, which contradicts the fact that they are rational. Thus, $p$ must be a perfect square.

Similarly, we can show that $q$ and $r$ are also perfect squares. Thus, $p$, $q$, and $r$ are all perfect squares, as required.

The largest such integer is $a b-a-b$. To see it’s not a nonnegative integer linear combination, suppose $a b-a-b=a x+b y$ with $x, y \in \mathbb{Z}_{\geq 0}$. Then $a(b-1-x)=b(y+1)$. And since $(a, b)=1$ we have $a \mid y+1$ (and $b \mid b-1-x$ ). This forces $y \geq a-1$ because $y+1 \geq 1$. So
$$
a x+b y \geq a \cdot 0+b(a-1)=a b-b>a b-a-b
$$
contradicting $a b-a-b=a x+b y$.
On the other hand, suppose $n>a b-a-b$. Since $\operatorname{gcd}(a, b)=1$ we can write $n=a x+b y$ with $x, y \in \mathbb{Z}$ (not necessarily nonnegative). Now note that $n=a(x-b k)+b(y+a k)$ for any integer $k$. By the division algorithm, there exists an integer $k$ such that $0 \leq x-b k<b$. Let $x^{\prime}=x-b k$ and $y^{\prime}=y+a k$. Then we have $n=a x^{\prime}+b y^{\prime}$ with $0 \leq x^{\prime} \leq b-1$, so
$$
b y^{\prime}=n-a x^{\prime} \geq(a b-a-b+1)-a(b-1)=-(b-1)
$$
Therefore $y^{\prime} \geq \frac{-(b-1)}{b}$, and since $y^{\prime}$ is an integer, we get $y^{\prime} \geq 0$. This shows that $n=a x^{\prime}+b y^{\prime}$ is a nonnegative integer linear combination.

Suppose $n$ is prime. Then, since the binomial coefficients in the middle vanish mod $p$,
$$
\begin{aligned}
(x-a)^n & \equiv x^n+(-a)^n \
& \equiv x^n+(-a) \quad(\bmod n) .
\end{aligned}
$$
Now for the converse. The polynomial congruence in particular means that $n$ must divide $\left(\begin{array}{l}n \ i\end{array}\right)$ for $i=1, \ldots, n-1$. We’ll see first that this implies $n$ must be a power of a prime.

Let $p$ be any prime dividing $n$. If $n$ is not a power of $p$, then the base $p$ expansion of $n$ does not look like 1 followed by a bunch of zeroes, so it’s either $n_r 0 \cdots 0$ with $n \geq 2$, or $n_r n_{r-1} \cdots n_i \cdots n_0$ with some $n_i \geq 1$ for $i<r$. In any case, let $k$ have the base $p$ expansion $10 \cdots 0$ (i.e., $k=p^r$ ). Then subtracting $k$ from $n$ in base $p$ doesn’t involve any carries, so $p \nmid\left(\begin{array}{l}n \ k\end{array}\right)$ and therefore $n \nmid\left(\begin{array}{l}n \ k\end{array}\right)$, contradiction. So $n$ must be a power of $p$.

Let’s assume $n$ is not a prime, so we now have $n=p^r$ with $r \geq 2$. Then it’s clear that subtracting $p^{r-1}$ (whose base $p$ expansion is $010 \cdots 0$ ) from $n$ in base $p$ will involve only one carry. So $p |\left(\begin{array}{c}r \ p^{r-1}\end{array}\right)$, and thus $n=p^r$ cannot divide this binomial coefficient, contradiction. Therefore, $n$ is indeed a prime.

We have.
$$
p^e \mid\left(x^2-1\right)=(x-1)(x+1)
$$
Suppose $p$ is odd. Then $p$ can’t divide both $x+1$ and $x-1$, since their difference 2 isn’t divisible by $p$, so $\left(p^e, x+1\right)=1$ or $\left(p^e, x-1\right)=1$. Hence $p^e \mid x-1$ or $p^e \mid x+1$, and the only two solutions are $x \equiv \pm 1$ $\left(\bmod p^3\right)$
Now suppose $p=2$. Then $x^2 \equiv 1\left(\bmod 2^c\right)$ means $x$ must be odd, so let $x=2 y+1$. We have
$$
2^e \mid(x-1)(x+1)=4 y(y+1)
$$
Note that if $p=2$ then $x=1$, and if $p=4$ then $x=1,3$. So let’s assume $e \geq 3$. Since $y$ and $y+1$ are obviously coprime, we have $2^{e-2} \mid y$ or $2^{e-2} \mid y+1$, i.e., $y \equiv 0\left(\bmod 2^{\varepsilon-2}\right)$ or $y \equiv-1\left(\bmod 2^{c-2}\right)$. Then, modulo $2^{c-1}$, the possible solutions for $y$ are $0,2^{c-2}, 2^{e-2}-1,-1$, and the corresponding solutions for $x$ are $1,-1,2^{e-1}+1,2^{e-1}-1$. It’s easy to verify that all of these work and are distinct modulo $2^e$.