Problems in Quadratic Congruencies

The following compilation of solved problems is related to quadratic residues, quadratic congruences, Legendre\( \prime \)s symbols, Jacobi\( \prime \)s symbols, and related Gauss\( \prime \) reciprocity law. The problems are at the level of math olympiads for high schools and universities. You may wish to read these notes before starting to work on problems.

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


2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us