1. ## Questions about Number Theory

need help on the following two questions

1.

2.

Thanks

2. Originally Posted by toxiccan
1.
We must have $n>1$ since 1 is a perfect square. Thus n can be written as a product of distinct primes: $n=p_1^{m_1}p_2^{m_2}\ldots p_r^{m_r}$ $(m_i\ge1)$.

Now if all the $m_i$’s were even, n would be a perfect square. Since it isn’t, at least one of the $m_i$’s must be odd. Hence, we can write $n=p^mk$ where m is odd and p does not divide k.

Suppose $\sqrt{n}$ is rational: $\sqrt{n}=\frac{a}{b}$, where $a,b\in\mathbb{Z}$, $b\ne0$ and $\gcd(a,b)=1$.

Then $a^2=nb^2=p^mkb^2$

$\therefore p\mid a^2$ $\Rightarrow$ $p\mid a$ as p is prime $\Rightarrow$ $p\nmid b$ as $\gcd(a,b)=1$.

Hence the factor of p occurs an odd number of times in $p^mkb^2 = a^2$. This is a contradiction because $a^2$ is a perfect square and so each prime factor of $a^2$ has to occur an even number of times.

Thus $\sqrt{n}$ must be irrational.

3. Originally Posted by toxiccan
2.
It suffices to prove that $x^2+y^2+1\equiv 0(\bmod p)$ has a solution with $0\leq x,y\leq \tfrac{p-1}{2}$.
Let $A = \{ 1 + 0^2,1+1^2,...,1+\left( \tfrac{p-1}{2} \right)^2\}$.
Let $B = \{ -0^2,-1^2,...,-\left( \tfrac{p-1}{2} \right)^2\}$.
If $x,y \in A$ then $x=1+x_0^2$ and $y=1+y_0^2$. If $x\equiv y(\bmod p)$ then it means $y_0^2 \equiv x_0^2(\bmod p)$ so $x_0\equiv \pm y_0 (\bmod p)$. The negative sign is impossible so $x_0=y_0\implies x=y$. Thus distinct elements in that set are not congruent to eachother. Thus, $|A| = 1+\tfrac{p-1}{2}$. Using a similar argument we can show $|B| = 1+\tfrac{p-1}{2}$. This means altogether $A$ and $B$ has $2(1+\tfrac{p-1}{2}) = p+1$ elements. Thus, by pigeonhole principle there is $a\in A$ and $b\in B$ such that $a\equiv b(\bmod p)$ because the set of remainders mod $p$ is size $p$. Thus, $1+x^2 \equiv - y^2(\bmod p)$.