Problems in Quadratic Congruencies

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

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

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

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

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.

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

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

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

(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\( \prime \)s symbol \( \left(\frac{-z}{4xz-1}\right) \) is \( -1 \) for all \( x,z \), yielding a contradiction.

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

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.

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

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