If $a,b$ are quadratic residues, then so is $ab$. Thus it suffices to show that the set $S = \{ s \in \mathbb Z | 0 < s < \sqrt p +1 \}$ generates all residues $\neq 0$. Assume this to be false and let $x$ be the smallest positive integer whose residue class is not represented by $S$. Then $x \geq \sqrt p +1$ and we consider $a := 1+\left\lfloor \frac{p-1}{x} \right\rfloor$ and observe: a) $0<a<1+ \frac{p-1}{x} \leq 1+ \frac{p-1}{\sqrt p +1} = \sqrt p$, thus $a \in S$. b) $p-1 = \frac{p-1}{x} \cdot x < ax \leq \left( \frac{p-1}{x} +1 \right) \cdot x = p+x-1$, thus (clearly $p \nmid a,x$) $ax-p \in S$ (remember that $x$ was minimal). But now $x=1 \cdot x \equiv a^{p-1} \cdot x = a^{p-2} \cdot (ax) \mod p$, so $x$ is a product of elements of $S$ seen $\mod p$, contradiction. And we are done

Peter wrote: Let p be an odd prime number. Show that the smallest positive quadratic nonresidue of p is smaller than \sqrt{p}+1. Let $S=\{m\in \mathbb{F}_p|m^2<p\}$. The statement is equivalent to showing that $S$ contains a non-square. Suppose not, for contradiction; then all of $S$ are squares. The crucial observation here is that $T=\left\{\prod_i s_i | s_i \in S\right\}$ generates all of $\mathbb{F}_p$. But this yields a contradiction, since we supposed that all of $S$ was square, hence all of $T$ is square, contradiction.

ZetaX wrote: b) $p-1 = \frac{p-1}{x} \cdot x < ax \leq \left( \frac{p-1}{x} +1 \right) \cdot x = p+x-1$, thus (clearly $p \nmid a,x$) $ax-p \in S$ (remember that $x$ was minimal). I have only one question. You say that $ax-p \in S,$ but is it always true? Actually, I think that it is enough to say that $ax-p$ is a quadratic residue since it is strictly less than $x.$

$S$ should be replaced with the residues generated by $S$ there.

ZetaX wrote: $S$ should be replaced with the residues generated by $S$ there. It is okay now.

Let $a$ be the least quadratic nonresidue $\pmod{p}$, and let $b=\left\lfloor\frac{p}{a}\right\rfloor+1$. Since $0<ab-p<a$, $ab-p$ must be a quadratic residue. Thus, \[1=\left(\frac{ab-p}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{a}{p}\right)=-\left(\frac{b}{p}\right),\] so $\left(\frac{b}{p}\right)=-1$, so $b$ is a quadratic nonresidue $\pmod{p}$, which means $a\le b<\frac{p}{a}+1$, and the result trivially follows.

me@home wrote: Peter wrote: Let p be an odd prime number. Show that the smallest positive quadratic nonresidue of p is smaller than \sqrt{p}+1. Let $S=\{m\in \mathbb{F}_p|m^2<p\}$. The statement is equivalent to showing that $S$ contains a non-square. Suppose not, for contradiction; then all of $S$ are squares. The crucial observation here is that $T=\left\{\prod_i s_i | s_i \in S\right\}$ generates all of $\mathbb{F}_p$. But this yields a contradiction, since we supposed that all of $S$ was square, hence all of $T$ is square, contradiction. Sorry to revive, can you show how $T$ generates all of $\mathbb{F}_b$? I don't quite see

Instant by Thue's Lemma