Quadratic congruences (Table of contents)
# Problems

The following compilation of solved problems is related to quadratic residues, quadratic congruences, Legendre's symbols, Jacobi's symbols, and related Gauss' reciprocity law. The problems are at the level of math olympiads for high schools and universities.

**Problem 10**
Let \(p\) be a prime number. Prove that there exists \(x\in
\mathbb{Z}\) for which \(p\mid x^2-x+3\) if and only if there exists
\(y\in\mathbb{Z}\) for which \(p\mid y^2-y+25\).

The statement is trivial for \(p\leq3\), so we can assume that
\(p\geq5\).

Since \(p\mid x^2-x+3\) is equivalent to \(p\mid4(x^2-x+3)=(2x-1)^2+11\),
integer \(x\) exists if and only if \(-11\) is a quadratic residue modulo
\(p\). Likewise, since \(4(y^2-y+25)=(2y-1)^2+99\), \(y\) exists if and only
if \(-99\) is a quadratic residue modulo \(p\). Now the statement of the
problem follows from \[\left(\frac{-11}p\right)=
\left(\frac{-11\cdot3^2}p\right)=\left(\frac{-99}p\right).\]

**Problem 11**
Let \(p=4k-1\) be a prime number, \(k\in\mathbb{N}\). Show that
if \(a\) is an integer such that the congruence \(x^2\equiv a\) (mod
\(p\)) has a solution, then its solutions are given by \(x=\pm a^k\).

According to Euler's criterion, the existence of a solution
of \(x^2\equiv a\) (mod \(p\)) implies \(a^{2k-1}\equiv1\) (mod
\(p\)). Hence for \(x=a^k\) we have \(x^2\equiv a^{2k}\equiv a\) (mod
\(p\)).

**Problem 12**
Show that all odd divisors of number \(5x^2+1\) have an even
tens digit.

If \(p\mid 5x^2+1\), then \(\left(\frac{-5}p\right)=1\). The
Reciprocity rule gives us \[\left(\frac{-5}p\right)
=\left(\frac{-1}p\right)\left(\frac5p\right)=(-1)^{\frac{p-1}2}
\left(\frac p5\right).\] It is easy to verify that the last expression
has the value 1 if and only if \(p\) is congruent to \(1,3,7\) or \(9\)
modulo \(20\).

**Problem 13**
Show that for every prime number \(p\) there exist integers
\(a,b\) such that \(a^2+b^2+1\) is a multiple of \(p\).

Clearly, \(p\mid a^2+b^2+1\) if and only if \(a^2\equiv
-b^2-1\) (mod \(p\)).

Both sets \(\{a^2\mid a\in\mathbb{Z}\}\) and \(\{-b^2-1\mid
b\in\mathbb{Z}\}\) modulo \(p\) are of cardinality exactly
\(\frac{p+1}2\), so they have an element in common, i.e. there
are \(a,b\in\mathbb{Z}\) with \(a^2\) and \(-b^2-1\) being equal modulo \(p\).

**Problem 14**
Prove that \(\frac{x^2+1}{y^2-5}\) is not an integer for
any integers \(x,y > 2\).

If \(y\) is even, \(y^2-5\) is of the form \(4k+3\), \(k\in\mathbb
{Z}\) and thus cannot divide \(x^2+1\) for \(x\in\mathbb{Z}\). If \(y\) is
odd, then \(y^2-5\) is divisible by 4, while \(x^2+1\) is never a multiple
of 4.

**Problem 15**
Let \(p > 3\) be a prime and let \(a,b\in\mathbb{N}\) be such that
\[1+\frac12+\cdots+\frac1{p-1}=\frac ab.\] Prove that \(p^2\mid a\).

It suffices to show that \(\frac{2(p-1)!a}b=
\sum_{i=1}^{p-1}\frac{2(p-1)!}i\) is divisible by \(p^2\). To start with,
\[\frac{2(p-1)!a}b=\sum_{i=1}^{p-1}
\left(\frac{(p-1)!}i+\frac{(p-1)!}{p-i}\right)=\sum_{i=1}^{p-1}\frac
{p(p-1)!}{i(p-i)}.\] Therefore, \(p\mid a\). Moreover, if for
\(i\in\{1,2, \dots,p-1\}\) \(i\prime\) denotes the inverse of \(i\) modulo \(p\),
we have \[\frac{2(p-1)!a}{pb}=\sum_{i=1}^{p-1}\frac{(p-1)!}{i(p-i)}
\equiv\sum_{i=1}^{p-1}{i\prime}^2(p-1)!\equiv0\;\mbox{(mod \(p\))}.\]
It follows that \(p^2\mid2(p-1)!a\).

**Problem 16**
Consider \(P(x)=x^3+14x^2-2x+1\). Show that there exists a
natural number \(n\) such that for each \(x\in\mathbb{Z}\),
\[101\mid\underbrace{P(P(\dots P}_n(x)\dots))-x.\]

All congruences in the solution will be modulo 101.

It is clear that \(P(x)\equiv P(y)\) for integers \(x,y\) with \(x\equiv y\).

We claim that the converse holds: \(P(x)\not\equiv P(y)\) if \(x\not
\equiv y\). We have
\[\frac {4[P(x)-P(y)]}{x-y}=4(x^2+xy+y^2+14x+14y-2)\equiv
(2x+y+14)^2+3(y-29)^2.\] Since \(-3\) is not a quadratic residue modulo
101, the left hand side is not divisible by 101 unless if \(2x+y+14
\equiv y-29\equiv0\), i.e. \(x\equiv y\equiv 29\). This justifies our
claim.

We now return to the problem. The above statement implies that
\(P(0),P(1),\dots,P(100)\) is a permutation of
\(0,1,\dots,100\) modulo 101. We conclude that for each \(x\in\{0,1,\dots,
100\}\) there is an \(n_x\) such that \(P(P(\dots P(x)\dots))\equiv x\)
(with \(P\) applied \(n_x\) times).

Any common multiple of the numbers \(n_0,n_1,\dots,n_{100}\) is clearly a
desired \(n\).

**Problem 17**
Determine all \(n\in\mathbb{N}\) such that the set \(A=\{n,n+1,
\dots,n+1997\}\) can be partitioned into at least two subsets with
equal products of elements.

Suppose that \(A\) can be partitioned into \(k\) subsets \(A_1,
\dots,A_k\), each with the same product of elements \(m\). Since at least
one and at most two elements of \(A\) are divisible by the prime \(1997\),
we have \(1997\mid m\) and hence \(k=2\). Furthermore, since the number of
elements divisible by the prime 1999 is at most one, we have \(1999
\nmid m\); hence no elements of \(A\) is divisible by 1999, i.e. the
elements of \(A\) are congruent to \(1,2,3,\dots,1998\) modulo 1999. Then
\(m^2\equiv 1\cdot2\cdot3\cdots1998\equiv-1\) (mod \(1999\)), which is
impossible because -1 is a quadratic nonresidue modulo
\(1999=4\cdot499+3\).

**Problem 18**
(a) Prove that for no \(x,y\in\mathbb{N}\) is \(4xy-x-y\) a square;

(b) Prove that for no \(x,y,z\in\mathbb{N}\) is \(4xyz-x-y\) a square.

Part (a) is a special case of (b).

(b) Suppose \(x,y,z,t\in\mathbb{N}\) are such that \(4xyz-x-y=t^2\).
Multiplying this equation by \(4z\) we obtain \[(4xz-1)(4yz-1)=4zt^2+1.\]
Therefore, \(-4z\) is a quadratic residue modulo \(4xz-1\). However, it was
proved in problem 8 that the value of Legendre's symbol
\(\left(\frac{-z}{4xz-1}\right)\) is \(-1\) for all \(x,z\), yielding a
contradiction.

**Problem 19**
If \(n\in\mathbb{N}\), show that all prime divisors of
\(n^8-n^4+1\) are of the form \(24k+1\), \(k\in\mathbb{N}\).

Consider an arbitrary prime divisor \(p\) of \(n^8-n^4+1\). It
follows from problem 4 that \(p\) is congruent to \(1\) or \(13\) (mod
\(24\)). Furthermore, since \[n^8-n^4+1=(n^4+n^2+1)-2(n^3+n)^2,\] \(2\) is
a quadratic residue modulo \(p\), excluding the possibility
\(p\equiv\pm13\) (mod 24).

**Problem 20**
Suppose that \(m,n\) are positive integers such that
\(\varphi(5^m-1)=5^n-1\). Prove that \((m,n) > 1\).

Suppose that \((m,n)=1\). Let \[5^m-1=2^{\alpha}
p_1^{\alpha_1}\cdots p_k^{\alpha_k}\quad\quad\quad\quad\quad (1)\] be the factorization of
\(5^m-1\) onto primes, where \(p_i > 2\) za \(i=1,\dots,k\). By the condition
of the problem, \[5^n-1=\varphi(5^m-1)=2^{\alpha-1}
p_1^{\alpha_1-1}\cdots p_k^{\alpha_k-1}(p_1-1)\cdots(p_k-1).\quad\quad\quad\quad\quad(2)\]
Obviously, \(2^{\alpha}\mid 5^n-1\). On the other hand, it follows from
\((5^m-1,5^n-1)=5^1-1=4\) that \(\alpha_i=1\) for each \(i=1,\dots,k\) and
\(\alpha=2\). Since \(2^3\mid 5^x-1\) for every even \(x\), \(m\) must be odd:
\(m=2m\prime+1\) for some \(m\prime\in\mathbb{N}_0\).

Since \(p_i\mid 5\cdot(5^{m\prime})^2-1\) for \(i=1,\dots,k\), 5 is a
quadratic residue modulo \(p_i\), and consequently \(p_i\equiv\pm1\)
(mod 5). However, (2) implies that none of \(p_i-1\) is divisible by
5. We thus obtain that \(p_i\equiv-1\) (mod 5) for all \(i\).

Reduction of equality (1) modulo 5 yields \((-1)^k=1\). Thus \(k\) is even.
On the other hand, equality (2) modulo 5 yields \((-2)^{k+1}\equiv1\)
(mod 5), and therefore \(k\equiv 3\) (mod 4), contradicting
the previous conclusion.

*Remark.* Most probably, \(m\) and \(n\) do not even exist.

**Problem 21**
Prove that there are no positive integers \(a,b,c\) for which
\[\frac{a^2+b^2+c^2}{3(ab+bc+ca)}\] is an integer.

Suppose that \(a,b,c,n\) are positive integers such that
\(a^2+b^2+c^2=3n(ab+bc+ca)\). This equality can be rewritten as
\[(a+b+c)^2=(3n+2)(ab+bc+ca).\]

Choose a prime number \(p\equiv2\) (mod 3) which divides \(3n+2\) with
an odd exponent, i.e. such that \(p^{2i-1}\mid 3n+2\) and \(p^{2i}\nmid
3n+2\) for
some \(i\in\mathbb{N}\) (such \(p\) must exist). Then \(p^i\mid a+b+c\) and
therefore \(p\mid ab+bc+ca\). Substituting \(c\equiv-a-b\) (mod \(p\))
in the previous relation we obtain \[p\mid a^2+ab+b^2\quad\Rightarrow
\quad p\mid(2a+b)^2+3b^2.\] It follows that \(\left(\frac{-3}p\right)
=1\), which is false because \(p\equiv2\) (mod 3).

**Problem 22**
Prove that, for all \(a\in\mathbb{Z}\), the number of
solutions \((x,y,z)\) of the congruence \[x^2+y^2+z^2\equiv 2axyz\;
\mbox{(mod \(p\))}\] equals \(\left(p+(-1)^{p\prime}\right)^2\).

The given congruence is equivalent to \[(z-axy)^2\equiv
(a^2x^2-1)y^2-x^2\;\;\mbox{(mod \(p\))}.\quad\quad\quad\quad\quad (1)\] For any fixed
\(x,y\in\{0,\dots,p-1\}\), the number of solutions \(z\) of (1) equals
\[1+\left(\frac{(a^2x^2-1)y^2-x^2}p\right).\] Therefore the total
number of solutions of (1) equals \[N=p^2+\sum_{x=0}^{p-1}
\sum_{y=0}^{p-1}\left(\frac{(a^2x^2-1)y^2-x^2}p\right).\] According to
theorem 19, \(\sum_{y=0}^{p-1}\left(\frac{(a^2x^2-1)y^2
-x^2}p\right)\) is equal to \(-\left(\frac{a^2x^2-1}p\right)\) if
\(ax\not\equiv\pm1\) (mod \(p\)), and to \(p\left(\frac{-1}p
\right)\) if \(ax\equiv\pm1\) (mod \(p\)). Therefore \[N=p^2+
2p\left(\frac{-1}p\right)-\sum_{x=0}^{p-1}\left(\frac{a^2x^2-1}p
\right)=\left(p+\left(\frac{-1}p\right)\right)^2.\]