I want to ask 2 number theory questions. I would better to make different forum but I will not do it since the second question is really short.
1) Let $p$ be a prime. Show that $ x^2+y^2 +1 \equiv 0 \pmod p$ always has a solution $(x,y)$
This was the solution provided by Brilliant:
I do understand the part that says that there are $ \frac {p+1}{2}$ elements of $ \{0,1, \cdots p-1\}$ than can be written as $ x^2 \pmod p$ but I really don't understand the following parts about the subsets.
2) Assume $a$ and $n$ are positive interger s.t gcd$(a,n)=1$. Show that if $ a^m \equiv 1 \pmod n$ then ord$_n (a)| m$.
I do know how to show that, just give some values to $m$ so that it increases and compute $ a^m \pmod n$, you realize that start getting the same values, and its smallest period woul be ord$_n (a)$ and then it would $d$ since it also is another period. But I saw another proof, it was:
Let $d=$ord$_n (a)$. Since $ a^m \equiv 1 \pmod n$ and $ a^d \equiv 1 \pmod n$, $ a^{mx+dy} \equiv 1 \pmod n$. By bezout's identity there are some values of $x$ and $y$ such that $mx+dy=$ gcd$(m,d)$. I've understood everything up until here but then they say: from the minimality $d$, it follows that $d \leq $ gcd$(m,d)$, which cannot hold unless they are equal and $d|m$.
So it's just that part about minimality that I don't understand.
a) If I take the $\frac{p+1}2$ squares $\bmod p$ and multiply by $-1\pmod p$, I still have $\frac{p+1}2$ residue classes $\bmod p$. If I then add $1\pmod p$, I still have $\frac{p+1}2$ residue classes. Hence there are also $\frac{p+1}2$ residue classes that can be written as one minus a square, i.e., as $1-y^2$. If the set of squares and the set of one-minus-squares were disjoint, they together would provide $\frac{p+1}2+\frac{p+1}2=p+1$ residue classes - but there are only $p$! We conclude that one residue class $a\bmod p$ can be written both as $a\equiv x^2\bmod p$ aand as $a\equiv 1-y^2\bmod p$. Then $x^2\equiv 1-y^2\pmod p$ and finally $x^2+y^2\equiv 1\pmod p$.
b) Let $d$ be the smallest positive integer with $a^d\equiv 1\pmod n$. Assume $a^m\equiv 1\pmod n$ with positive integer $m$. Division with remainder gives you integes $q\ge0$, $0\le r<d$ with $m=qd+r$. Then $$1\equiv a^m\equiv a^{qd+r}\equiv (a^d)^qa^r\equiv 1^qa^r\equiv a^r\pmod n.$$ As $d$ is the smallest positive integer with that property, it follows that either $r\ge d$ or $r$ is not a positive integer. Together with $0\le r<d$, only the option $r=0$ remains, i.e., $m$ is a multiple of $d$.