need help on the following two questions
1.
2.
Thanks
We must have $\displaystyle n>1$ since 1 is a perfect square. Thus n can be written as a product of distinct primes: $\displaystyle n=p_1^{m_1}p_2^{m_2}\ldots p_r^{m_r}$ $\displaystyle (m_i\ge1)$.
Now if all the $\displaystyle m_i$’s were even, n would be a perfect square. Since it isn’t, at least one of the $\displaystyle m_i$’s must be odd. Hence, we can write $\displaystyle n=p^mk$ where m is odd and p does not divide k.
Suppose $\displaystyle \sqrt{n}$ is rational: $\displaystyle \sqrt{n}=\frac{a}{b}$, where $\displaystyle a,b\in\mathbb{Z}$, $\displaystyle b\ne0$ and $\displaystyle \gcd(a,b)=1$.
Then $\displaystyle a^2=nb^2=p^mkb^2$
$\displaystyle \therefore p\mid a^2$ $\displaystyle \Rightarrow$ $\displaystyle p\mid a$ as p is prime $\displaystyle \Rightarrow$ $\displaystyle p\nmid b$ as $\displaystyle \gcd(a,b)=1$.
Hence the factor of p occurs an odd number of times in $\displaystyle p^mkb^2 = a^2$. This is a contradiction because $\displaystyle a^2$ is a perfect square and so each prime factor of $\displaystyle a^2$ has to occur an even number of times.
Thus $\displaystyle \sqrt{n}$ must be irrational.
It suffices to prove that $\displaystyle x^2+y^2+1\equiv 0(\bmod p)$ has a solution with $\displaystyle 0\leq x,y\leq \tfrac{p-1}{2}$.
Let $\displaystyle A = \{ 1 + 0^2,1+1^2,...,1+\left( \tfrac{p-1}{2} \right)^2\}$.
Let $\displaystyle B = \{ -0^2,-1^2,...,-\left( \tfrac{p-1}{2} \right)^2\}$.
If $\displaystyle x,y \in A$ then $\displaystyle x=1+x_0^2$ and $\displaystyle y=1+y_0^2$. If $\displaystyle x\equiv y(\bmod p)$ then it means $\displaystyle y_0^2 \equiv x_0^2(\bmod p)$ so $\displaystyle x_0\equiv \pm y_0 (\bmod p)$. The negative sign is impossible so $\displaystyle x_0=y_0\implies x=y$. Thus distinct elements in that set are not congruent to eachother. Thus, $\displaystyle |A| = 1+\tfrac{p-1}{2}$. Using a similar argument we can show $\displaystyle |B| = 1+\tfrac{p-1}{2}$. This means altogether $\displaystyle A$ and $\displaystyle B$ has $\displaystyle 2(1+\tfrac{p-1}{2}) = p+1$ elements. Thus, by pigeonhole principle there is $\displaystyle a\in A$ and $\displaystyle b\in B$ such that $\displaystyle a\equiv b(\bmod p)$ because the set of remainders mod $\displaystyle p$ is size $\displaystyle p$. Thus, $\displaystyle 1+x^2 \equiv - y^2(\bmod p)$.