Problems in Quadratic CongruenciesThe 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
The statement is trivial for \( p\leq3 \), so we can assume that
\( p\geq5 \).
Since \( p\mid x^2x+3 \) is equivalent to \( p\mid4(x^2x+3)=(2x1)^2+11 \), integer \( x \) exists if and only if \( 11 \) is a quadratic residue modulo \( p \). Likewise, since \( 4(y^2y+25)=(2y1)^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
According to Euler\( \prime \)s criterion, the existence of a solution
of \( x^2\equiv a \) (mod \( p \)) implies \( a^{2k1}\equiv1 \) (mod
\( p \)). Hence for \( x=a^k \) we have \( x^2\equiv a^{2k}\equiv a \) (mod
\( p \)).
Problem 12
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{p1}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
Clearly, \( p\mid a^2+b^2+1 \) if and only if \( a^2\equiv
b^21 \) (mod \( p \)).
Both sets \( \{a^2\mid a\in\mathbb{Z}\} \) and \( \{b^21\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^21 \) being equal modulo \( p \).
Problem 14
If \( y \) is even, \( y^25 \) 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^25 \) is divisible by 4, while \( x^2+1 \) is never a multiple
of 4.
Problem 15
It suffices to show that \( \frac{2(p1)!a}b=
\sum_{i=1}^{p1}\frac{2(p1)!}i \) is divisible by \( p^2 \). To start with,
\[ \frac{2(p1)!a}b=\sum_{i=1}^{p1}
\left(\frac{(p1)!}i+\frac{(p1)!}{pi}\right)=\sum_{i=1}^{p1}\frac
{p(p1)!}{i(pi)}.\] Therefore, \( p\mid a \). Moreover, if for
\( i\in\{1,2, \dots,p1\} \) \( i\prime \) denotes the inverse of \( i \) modulo \( p \),
we have \[ \frac{2(p1)!a}{pb}=\sum_{i=1}^{p1}\frac{(p1)!}{i(pi)}
\equiv\sum_{i=1}^{p1}{i\prime}^2(p1)!\equiv0\;\mbox{(mod \( p \))}.\]
It follows that \( p^2\mid2(p1)!a \).
Problem 16
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)]}{xy}=4(x^2+xy+y^2+14x+14y2)\equiv (2x+y+14)^2+3(y29)^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 y29\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
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\equiv1 \) (mod \( 1999 \)), which is
impossible because 1 is a quadratic nonresidue modulo
\( 1999=4\cdot499+3 \).
Problem 18 (b) Prove that for no \( x,y,z\in\mathbb{N} \) is \( 4xyzxy \) a square.
Part (a) is a special case of (b).
(b) Suppose \( x,y,z,t\in\mathbb{N} \) are such that \( 4xyzxy=t^2 \). Multiplying this equation by \( 4z \) we obtain \[ (4xz1)(4yz1)=4zt^2+1.\] Therefore, \( 4z \) is a quadratic residue modulo \( 4xz1 \). However, it was proved in problem 8 that the value of Legendre\( \prime \)s symbol \( \left(\frac{z}{4xz1}\right) \) is \( 1 \) for all \( x,z \), yielding a contradiction.
Problem 19
Consider an arbitrary prime divisor \( p \) of \( n^8n^4+1 \). It
follows from problem 4 that \( p \) is congruent to \( 1 \) or \( 13 \) (mod
\( 24 \)). Furthermore, since \[ n^8n^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)=1 \). Let \[ 5^m1=2^{\alpha}
p_1^{\alpha_1}\cdots p_k^{\alpha_k}\quad\quad\quad\quad\quad (1)\] be the factorization of
\( 5^m1 \) onto primes, where \( p_i> 2 \) za \( i=1,\dots,k \). By the condition
of the problem, \[ 5^n1=\varphi(5^m1)=2^{\alpha1}
p_1^{\alpha_11}\cdots p_k^{\alpha_k1}(p_11)\cdots(p_k1).\quad\quad\quad\quad\quad(2)\]
Obviously, \( 2^{\alpha}\mid 5^n1 \). On the other hand, it follows from
\( (5^m1,5^n1)=5^11=4 \) that \( \alpha_i=1 \) for each \( i=1,\dots,k \) and
\( \alpha=2 \). Since \( 2^3\mid 5^x1 \) 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})^21 \) 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_i1 \) is divisible by 5. We thus obtain that \( p_i\equiv1 \) (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
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^{2i1}\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\equivab \) (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
The given congruence is equivalent to \[ (zaxy)^2\equiv
(a^2x^21)y^2x^2\;\;\mbox{(mod \( p \))}.\quad\quad\quad\quad\quad (1)\] For any fixed
\( x,y\in\{0,\dots,p1\} \), the number of solutions \( z \) of (1) equals
\[ 1+\left(\frac{(a^2x^21)y^2x^2}p\right).\] Therefore the total
number of solutions of (1) equals \[ N=p^2+\sum_{x=0}^{p1}
\sum_{y=0}^{p1}\left(\frac{(a^2x^21)y^2x^2}p\right).\] According to
theorem 19, \( \sum_{y=0}^{p1}\left(\frac{(a^2x^21)y^2
x^2}p\right) \) is equal to \( \left(\frac{a^2x^21}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}^{p1}\left(\frac{a^2x^21}p
\right)=\left(p+\left(\frac{1}p\right)\right)^2.\]

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