Quadratic congruences (Table of contents)


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\).

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\).

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

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\).

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

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\).

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.\]

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.

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.

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}\).

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

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.

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\).