Find all positive integers $n$ that are quadratic residues modulo all primes greater than $n$.

The positive integers $a$ and $b$ are such that the numbers $15a+16b$ and $16a-15b$ are both squares of positive integers. What is the least possible value that can be taken on by the smaller of these two squares?

Click for solution The answer is $231361$ : $a = 14911,$ $b = 481.$ $15 \cdot 14911 + 16 \cdot 481 = 231361 = 481^2,$ $16 \cdot 14911 - 15 \cdot 481 = 231361 = 481^2.$ Now, let us prove it. We have : $E_1 : 15a + 16b = x^2,$ $E_2 : 16a - 15b = y^2.$ $E_1^2 + E_2^2 \implies 481(a^2+b^2) = x^4 + y^4.$ So $x^4 + y^4 = 0 \mod 13 \cdot 37.$ But, this implies $x^4 + y^4 = 0 \mod 13$ and $x^4 + y^4 = 0 \mod 37$ that is, since these are primes, and taking $x$ and $y$ to be non-zero in $\mathbb{Z}/13\mathbb{Z}$ and $\mathbb{Z}/37\mathbb{Z}$ : $\left(\frac xy \right)^4 = -1 \mod 13$ and $\left(\frac xy \right)^4 = -1 \mod 37.$ But, this is impossible, which implies that $x$ and $y$ are both divisible by $13$ and $37,$ hence $x = 481u$ and $u = 481v,$ hence $a^2 + b^2 = 481^3(u^2+v^2).$ The possible minimum for $\min(u, v)$ is $1.$ But, $1^2 + 31^2 = 2 \cdot 481 \implies 481^2 + (31 \cdot 481)^2 = 481^3(1^2 + 1^2).$ And, (today's a lucky day ), this necessary condition happens to be sufficient, giving the result announced in the very beginning of this post.

Let $p$ be an odd prime number. Show that the smallest positive quadratic nonresidue of $p$ is smaller than $\sqrt{p}+1$.

Click for solution 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

Let $M$ be an integer, and let $p$ be a prime with $p>25$. Show that the set $\{M, M+1, \cdots, M+ 3\lfloor \sqrt{p} \rfloor -1\}$ contains a quadratic non-residue to modulus $p$.

Let $p$ be an odd prime and let $Z_{p}$ denote (the field of) integers modulo $p$. How many elements are in the set \[\{x^{2}: x \in Z_{p}\}\cap \{y^{2}+1: y \in Z_{p}\}?\]

Click for solution That notation looks ugly, I will use $\mathbb{F}_p$ for the field with $p$ elements Lets work completely in $\mathbb{F}_p$. We look for the solutions $(x,y)$ of $x^2 = y^2+1$. One is given by $P=(1,0)$ and we use the method of secants to find all: We intersect lines $y=\lambda (x-1)$ through $P$ with slope $\lambda$ with the hyperbola $x^2-y^2=1$. This gives $x^2- (\lambda(x-1))^2=1 \iff (x-1)(x+1) - \lambda^2(x-1)^2 =0$, having $x=1$ (giving $y=0$, so resulting in the point $P$) as solution. The second solution is that of $(x+1) - \lambda^2(x-1) =0 \iff x=- \frac{1+\lambda^2}{1-\lambda^2}$. To $\lambda = \pm 1$, there corresponds no solution, but all other $\lambda$ give us some $x$ and thus also some $y$ in an unique way. If $\lambda, \lambda^\prime$ give the same $(x,y)$, then $\lambda (x-1) = y = \lambda^\prime (x-1)$, giving $\lambda=\lambda^\prime$ if $x \neq 1$. If $x=1$, we have $1=x=- \frac{1+\lambda^2}{1-\lambda^2} \iff 2=0$, contradiction. Conversely, every $(x,y) \neq P=(1,0)$ on the hyperbola gives us $\lambda = \frac{y}{x-1}$ by the same arguments. We see that this gives us a bijection between the slopes $\lambda \neq \pm 1$ and the points $\neq P$ on the hyperbola- Thus the set of points $(x,y)$ on the hyperbola equals $1$ (for $P=(1,0)$) plus the number of $\lambda \neq \pm 1$, thus in total equals $p-1$. If $y=0$, then $x^2=1 \iff x= \pm 1$, thus there are exactly two points with $y=0$. Similar, $x=0$ yields $y^2=-1$, having only (two) solutions if $p \equiv 1 \mod 4$. If $x,y \neq 0$, there are always exactly four points with the same value of $x^2$, namely $(\pm x , \pm y)$. It's also possible to get this result from http://www.problem-solving.be/pen/viewtopic.php?t=134 . Counting again, we get $\frac{p-1-4}{4}+1+1=\frac{p+3}{4}$ values for $x^2$ if $p \equiv 1 \mod 4$ and $\frac{p-1-2}{4}+1=\frac{p+1}{4}$ such values for $p \equiv -1 \mod 4$.

Let $a, b, c$ be integers and let $p$ be an odd prime with \[p \not\vert a \;\; \text{and}\;\; p \not\vert b^{2}-4ac.\] Show that \[\sum_{k=1}^{p}\left( \frac{ak^{2}+bk+c}{p}\right) =-\left( \frac{a}{p}\right).\]