Problems

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

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

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

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

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.

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

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

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

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.

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

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

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