Book 2. Olympiad Number Theory Methods

Let \(d=\gcd(n+4,n^2+2n+10)\). Modulo \(n+4\), \(n\equiv-4\), so \(n^2+2n+10\equiv16-8+10=18\). Hence \(d=\gcd(n+4,18)\), so only the divisors of \(18\) are possible: \(1,2,3,6,9,18\). Each occurs: for a divisor \(r\mid18\), take \(n+4=r+18\). Then \( \gcd(n+4,18)=r \).

If \(d\mid n+1\), then \(n\equiv-1\pmod d\). Therefore \(n^2+n+1\equiv1-1+1=1\pmod d\). A common divisor must divide \(1\), so it is \(1\).

Any common divisor \(d\) of \(3n+2\) and \(5n+3\) divides \(5(3n+2)-3(5n+3)=1\). Hence \(d=1\), so the numbers are coprime.

Modulo \(n+3\), \(n\equiv-3\), hence \(n^2+1\equiv10\). Thus \( \gcd(n^2+1,n+3)=\gcd(10,n+3) \). This gcd is greater than \(1\) exactly when \(n+3\) is divisible by \(2\) or by \(5\). Therefore \(n\) is odd or \(n\equiv2\pmod5\).

We have \((2n+1)^2=4n^2+4n+1\). If \(d\) divides \(2n+1\) and \(4n^2+4n+3\), then \(d\) divides the difference \(2\). But \(2n+1\) is odd, so the common divisor cannot be \(2\). Hence \(d=1\).

We have \(n^3-1=(n-1)(n^2+n+1)\) and \(n^2-1=(n-1)(n+1)\). Hence the gcd equals \((n-1)\gcd(n^2+n+1,n+1)\). The last gcd is \(1\), because for \(n\equiv-1\), the expression \(n^2+n+1\) has remainder \(1\). Therefore the gcd is \(n-1\).

Let \(d\) be a common divisor. Since \(d\mid2n+1\), we have \((2n+1)^2\equiv0\pmod d\). But \(4(n^2+n+1)=(2n+1)^2+3\), so \(d\mid3\). Thus the gcd is greater than \(1\) only when \(3\mid2n+1\), that is, \(n\equiv1\pmod3\). In this case \(3\) really divides both numbers. Answer: \(n\equiv1\pmod3\).

Let an odd prime \(p\) divide both numbers. From \(a+b\equiv0\pmod p\), we get \(b\equiv-a\). Then \(a^2+b^2\equiv2a^2\pmod p\). Since \(p\ne2\), this gives \(p\mid a\), hence \(p\mid b\), contradicting \( \gcd(a,b)=1 \). Thus only the divisor \(2\) is possible. It occurs exactly when both \(a+b\) and \(a^2+b^2\) are even, that is, when \(a,b\) are both odd. Then \(a^2+b^2\equiv2\pmod4\), so the gcd is exactly \(2\).

Let \(m=n+2\). Then \(n^2+3n+3=m^2-m+1\), and \(n^2+5n+7=m^2+m+1\). A common divisor divides the difference \(2m\). But \(m^2-m+1\) is coprime to \(m\), because modulo \(m\) it has remainder \(1\). Hence the common divisor can only divide \(2\). Since \(m^2-m+1\) is always odd, the common divisor is not \(2\). Therefore the gcd is \(1\).

Since \( \gcd(m,n)=1 \), the general power identity gives \( \gcd(a^m-1,a^n-1)=a^1-1=a-1 \). Directly, the common divisor is preserved when the exponent pair \((m,n)\) is replaced by \((m-n,n)\), until the Euclidean algorithm reaches exponent \(1\).

A common divisor divides the difference \((3^n+2)-(3^n-1)=3\). Thus the only possible common prime divisor is \(3\). But \(3^n-1\equiv -1\pmod3\), so \(3\) does not divide the first number. Hence the gcd is \(1\).

Let \(d\) be a common divisor. Then \(d\mid n(n^2+2)-(n^3+3)=2n-3\). Hence \(2n\equiv3\pmod d\). Multiplying \(n^2+2\) by \(4\), we get \(4n^2+8\equiv9+8=17\pmod d\). Thus \(d\mid17\). A nontrivial common divisor can occur only when \(17\mid d\), that is, when \(2n\equiv3\pmod{17}\). Since \(2^{-1}\equiv9\pmod{17}\), we get \(n\equiv27\equiv10\pmod{17}\). Direct checking shows that for such \(n\), both expressions are divisible by \(17\).

Let \(d\) divide both numbers. Then \(d\mid (n+1)!+1-(n+1)(n!+1)=-n\). Hence \(d\mid n\), so \(d\mid n!\). But \(d\mid n!+1\), therefore \(d\mid1\). Thus \(d=1\).

Let \(d\) be a common divisor. Then \(d\mid p^3+1-p(p^2+1)=1-p\). Thus \(d\mid p-1\). Modulo \(p-1\), \(p\equiv1\), so \(p^2+1\equiv2\). Hence a common divisor can only divide \(2\). If \(p=2\), then \(\gcd(5,9)=1\). If \(p\) is odd, both \(p^2+1\) and \(p^3+1\) are even, so the gcd is \(2\). Answer: all odd primes \(p\).

Let \(g=\gcd(m,n)\). The number \(a^g-b^g\) divides both expressions. Conversely, let \(d\) divide both. Since \( \gcd(b,d)=1 \), the inverse \(b^{-1}\pmod d\) exists. From \(a^m\equiv b^m\) and \(a^n\equiv b^n\), we get \((ab^{-1})^m\equiv1\) and \((ab^{-1})^n\equiv1\pmod d\). The Euclidean algorithm on the exponents gives \((ab^{-1})^g\equiv1\pmod d\). Hence \(a^g\equiv b^g\pmod d\), so \(d\mid a^g-b^g\).

Since \(4^m-1=2^{2m}-1\), the power formula gives \( \gcd(2^{2m}-1,2^n-1)=2^{\gcd(2m,n)}-1 \). This is the answer.

Let \(d\) be the gcd. Modulo \(x+y\), \(x\equiv-y\), hence \(x^{2k}+y^{2k}\equiv2y^{2k}\pmod d\). Since \( \gcd(y,x+y)=1 \), the common divisor \(d\) divides \(2\). Therefore only \(1\) and \(2\) are possible. If \(x,y\) are both odd, then \(x+y\) and \(x^{2k}+y^{2k}\) are even, so the gcd is \(2\). If one is even and the other is odd, then \(x+y\) is odd, so the gcd is \(1\).

Let an odd prime \(p\) divide both expressions. Since \(p\nmid b\), put \(t\equiv ab^{-1}\pmod p\). From \(a^2+b^2\equiv0\), we get \(t^2\equiv-1\); from \(a^3+b^3\equiv0\), we get \(t^3\equiv-1\). Dividing the second congruence by the first gives \(t\equiv1\), but then \(1\equiv-1\pmod p\), a contradiction. Thus there are no odd common prime divisors. If one of \(a,b\) is even, both expressions are odd, so the gcd is \(1\). If both are odd, both expressions are even and \(a^2+b^2\equiv2\pmod4\), so the gcd is \(2\).

We have \(u_{n+1}=u_n(u_n-1)+1\), so \(u_{n+1}\equiv1\pmod{u_n}\). If \(u_k\equiv1\pmod{u_n}\), then \(u_{k+1}=u_k^2-u_k+1\equiv1-1+1=1\pmod{u_n}\). Hence for every \(m>n\), \(u_m\equiv1\pmod{u_n}\). Thus a common divisor of \(u_m\) and \(u_n\) divides \(1\), so the gcd is \(1\).

Let \(Q=a^2+ab+b^2\). If \(3\mid n\), then \(a^3-b^3=(a-b)Q\), so \(a^3\equiv b^3\pmod Q\), and therefore \(Q\mid a^n-b^n\). In this case the gcd is \(Q\). Now suppose \(3\nmid n\). Let a prime \(p\ne3\) divide both \(Q\) and \(a^n-b^n\). Since \(p\nmid b\), put \(t\equiv ab^{-1}\pmod p\). From \(Q\equiv0\), we get \(t^2+t+1\equiv0\), hence \(t^3\equiv1\) and \(t\not\equiv1\). Thus the order of \(t\) is \(3\). But \(a^n\equiv b^n\) gives \(t^n\equiv1\), so \(3\mid n\), a contradiction. Therefore, when \(3\nmid n\), the only possible common prime divisor is \(3\). The number \(3\) divides \(Q\) exactly when \(a\equiv b\pmod3\); by coprimality neither is divisible by \(3\), and then \(Q\) is divisible by \(3\) but not by \(9\). Under the same condition \(a^n-b^n\) is divisible by \(3\). Answer: if \(3\mid n\), the gcd is \(Q\); if \(3\nmid n\) and \(a\equiv b\pmod3\), the gcd is \(3\); otherwise the gcd is \(1\).

If the number is even, \(n=2k\), then \(n^2=4k^2\), and \(k^2\pmod4\) is \(0\) or \(1\), giving \(0\) or \(4\). If the number is odd, \(n=2k+1\), so \(n^2=4k(k+1)+1\); since \(k(k+1)\) is even, \(n^2\equiv1\) or \(9\pmod{16}\). Thus the possible residues are \(0,1,4,9\).

A square modulo \(4\) is \(0\) or \(1\). Hence a sum of two squares modulo \(4\) can be only \(0,1,2\). The right-hand side has residue \(3\), contradiction.

For \(n\equiv0,1,2,3,4,5,6\pmod7\), the expression \(n^2+n+1\) gives residues \(1,3,0,6,0,3,1\). Thus divisibility by \(7\) holds exactly when \(n\equiv2\) or \(n\equiv4\pmod7\).

We need \(n^2\equiv-1\equiv4\pmod5\). This occurs for \(n\equiv2\) or \(n\equiv3\pmod5\).

It is enough to check residues \(0,1,\ldots,9\). Their squares modulo \(10\) are \(0,1,4,9,6,5,6,9,4,1\). The residues \(2,3,7,8\) do not appear.

The squares \(0^2,1^2,\ldots,6^2\) modulo \(13\) are \(0,1,4,9,3,12,10\). Hence \(x\equiv5\) or \(x\equiv-5\equiv8\pmod{13}\).

A sum of two elements from \(\{0,1,4\}\) modulo \(8\) can be \(0,1,2,4,5\). Residue \(7\) is impossible. The right-hand side is \(7\pmod8\), so there are no solutions.

Modulo \(8\), each square is \(0,1\), or \(4\). Checking sums of three such residues shows that residue \(7\) is impossible: the possible residues include \(0,1,2,3,4,5,6\), but not \(7\). The right-hand side has residue \(7\), contradiction.

We have \(4(n^2+3n+5)=(2n+3)^2+11\). Divisibility by \(11\) is equivalent to \((2n+3)^2\equiv0\pmod{11}\), so \(2n+3\equiv0\pmod{11}\). Since \(2^{-1}\equiv6\pmod{11}\), we get \(n\equiv-18\equiv4\pmod{11}\).

Since \(p\mid a^2+1\), we have \(a^2\equiv-1\pmod p\), and \(p\nmid a\). Then \(a^4\equiv1\), but \(a^2\not\equiv1\). Hence the order of \(a\) modulo \(p\) is \(4\). The order of an element divides \(p-1\), so \(4\mid p-1\), meaning \(p\equiv1\pmod4\).

Assume \(p\nmid y\). Then \(y^{-1}\pmod p\) exists, and \(x^2+y^2\equiv0\) gives \((xy^{-1})^2\equiv-1\pmod p\). But for a prime \(p\equiv3\pmod4\), \(-1\) is not a square. Contradiction. Hence \(p\mid y\), and then \(p\mid x^2+y^2\) gives \(p\mid x^2\), so \(p\mid x\).

The condition is equivalent to \(x^2\equiv1\pmod3\) and \(x^2\equiv4\pmod5\). The first gives \(x\not\equiv0\pmod3\), and the second gives \(x\equiv\pm2\pmod5\). Combining the classes gives \(x\equiv2,7,8,13\pmod{15}\).

The condition \(x^2\equiv1\pmod{24}\) is equivalent to \(x^2\equiv1\pmod8\) and \(x^2\equiv1\pmod3\). Modulo \(8\), this means \(x\) is odd. Modulo \(3\), it means \(x\not\equiv0\pmod3\). Therefore, among residues \(0,\ldots,23\), the solutions are all odd residues not divisible by \(3\): \(1,5,7,11,13,17,19,23\). Direct checking confirms that each gives square \(1\pmod{24}\).

We need to solve \(x^2\equiv-1\pmod5\) and \(x^2\equiv-1\pmod{13}\). Modulo \(5\): \(x\equiv\pm2\). Modulo \(13\): \(x\equiv\pm5\). Combining the four pairs by CRT gives \(x\equiv8,18,47,57\pmod{65}\).

From \(x^2\equiv y^2\pmod p\), we get \(p\mid (x-y)(x+y)\). Since \(p\) is prime, it divides one of the factors. Hence \(x\equiv y\pmod p\) or \(x\equiv -y\pmod p\).

Squares modulo \(3\) are \(0\) or \(1\). If \(3\mid x^2+y^2\), the sum of residues cannot be \(1+0\) or \(1+1\), so both squares have residue \(0\). Thus \(3\mid x\) and \(3\mid y\). Then \(9\mid x^2+y^2=3z^2\), so \(3\mid z\). Dividing all variables by \(3\) gives a smaller solution. A nonzero solution would lead to infinite descent, so only \(x=y=z=0\) is possible.

Since \(p\nmid b\), put \(t\equiv ab^{-1}\pmod p\). Then \(t^2+t+1\equiv0\). Multiplying by \(t-1\), we get \(t^3-1\equiv0\). Also \(t\not\equiv1\), otherwise \(3\equiv0\pmod p\), impossible. Hence the order of \(t\) is \(3\). The order divides \(p-1\), so \(3\mid p-1\), meaning \(p\equiv1\pmod3\).

Assume not both numbers are divisible by \(p\). If \(p\mid b\), then the form gives \(p\mid a^2\), hence \(p\mid a\), contradiction. Thus we may assume \(p\nmid b\). Then \(t=ab^{-1}\) satisfies \(t^2+t+1\equiv0\pmod p\), and as in the previous problem this gives an element of order \(3\). Hence \(3\mid p-1\), so \(p\equiv1\pmod3\), contradicting \(p\equiv2\pmod3\). Therefore \(p\mid a\) and \(p\mid b\).

Let \(p\equiv3\pmod4\) and \(p\mid x^2+y^2\). By the lemma, \(p\mid x\) and \(p\mid y\), so \(x=px_1\), \(y=py_1\). Then \(N=p^2(x_1^2+y_1^2)\). If \(p\) again divides \(x_1^2+y_1^2\), repeat the same step. Each step decreases the exponent of \(p\) by \(2\). Therefore the exponent of \(p\) in \(N\) must be even.

The equation implies \(p\mid x^2+y^2\). By the lemma for primes \(p\equiv3\pmod4\), we get \(p\mid x\) and \(p\mid y\). Then \(p^2\mid x^2+y^2=pz^2\), so \(p\mid z\). Dividing \(x,y,z\) by \(p\), we obtain a smaller integer solution. If a nonzero solution existed, iteration would give infinite descent. Therefore no nonzero solution exists, and the only solution is \(x=y=z=0\).

\(2^1\equiv2\), \(2^2\equiv4\), \(2^3\equiv8\equiv1\pmod7\). Since \(1\) did not appear earlier, the order is \(3\).

\(3,9,27,81,243\) modulo \(11\) give \(3,9,5,4,1\). Therefore \( \operatorname{ord}_{11}(3)=5 \).

Since the order of \(2\) modulo \(7\) is \(3\), reduce the exponent: \(100\equiv1\pmod3\). Hence \(2^{100}\equiv2\pmod7\).

Powers of \(3\) modulo \(10\) are \(3,9,7,1\), then the cycle repeats. Since \(2026\equiv2\pmod4\), the last digit is \(9\).

\(5^2=25\equiv12\equiv-1\pmod{13}\). Hence \(5^4\equiv1\). The order is not \(1\) or \(2\), because \(5\not\equiv1\) and \(5^2\not\equiv1\). Therefore the order is \(4\).

Let \(k=qd+r\), where \(0\le r

If \(d=\operatorname{ord}_m(a)\), then \(a^r\equiv1\) and \(a^s\equiv1\) imply \(d\mid r\) and \(d\mid s\). Therefore \(d\mid\gcd(r,s)\), hence \(a^{\gcd(r,s)}\equiv1\pmod m\).

From \(2^m\equiv1\pmod p\), we get \( \operatorname{ord}_p(2)\mid m \). Since \(p\) is prime and \(2\not\equiv0\pmod p\), the order also divides \(p-1\). Therefore it divides \(\gcd(m,p-1)\).

For \(p=2\), there is no divisibility. If \(p\) is odd, Fermat's little theorem gives \(2^p\equiv2\pmod p\). Then \(2^p+1\equiv3\pmod p\), so \(p\mid3\), hence \(p=3\). Check: \(2^3+1=9\) is divisible by \(3\).

From \(a^2+a+1\equiv0\pmod p\), we get \(a^3-1=(a-1)(a^2+a+1)\equiv0\pmod p\). If \(a\equiv1\pmod p\), then \(3\equiv0\pmod p\), so \(p=3\). If \(a\not\equiv1\), the order of \(a\) is \(3\), hence \(3\mid p-1\), so \(p\equiv1\pmod3\).

Compute \(7^2=49\), \(7^4\equiv49^2=2401\equiv1\pmod{100}\). Since \(100\) is divisible by \(4\), \(7^{100}=(7^4)^{25}\equiv1\pmod{100}\). The last two digits are \(01\).

We have \(5^2=25\not\equiv1\pmod{31}\), while \(5^3=125\equiv1\pmod{31}\). Hence \( \operatorname{ord}_{31}(5)=3 \). Therefore \(5^n\equiv1\pmod{31}\) if and only if \(3\mid n\).

Compute \(2^4=16\equiv-1\pmod{17}\), hence \(2^8\equiv1\). The order of \(2\) modulo \(17\) is \(8\), because the smaller divisors \(1,2,4\) do not give \(1\). Thus \(2^n\equiv-1\) exactly when \(n\equiv4\pmod8\).

From \(p\mid a^n+1\), we get \(a^n\equiv-1\pmod p\). Then \(a^{2n}\equiv1\), so the order divides \(2n\). If the order divided \(n\), then \(a^n\equiv1\pmod p\), contradicting \(a^n\equiv-1\pmod p\), since \(p\) is odd.

The number \(2^{16}+1\) is odd, so \(q\ne2\). From \(2^{16}\equiv-1\pmod q\), we get \(2^{32}\equiv1\). Also \(2^{16}\not\equiv1\), and the order divides \(32\). The only divisor of \(32\) that does not divide \(16\) is \(32\). Thus the order of \(2\) modulo \(q\) is \(32\). Therefore \(32\mid q-1\), so \(q\equiv1\pmod{32}\).

\(3^4+1=82=2\cdot41\). Hence \(p=2\) or \(p=41\). For the method: if \(p\ne2\) divides \(3^4+1\), then \(3^4\equiv-1\), so the order of \(3\) modulo \(p\) is \(8\), and \(8\mid p-1\). Among the divisors of \(82\), this holds only for \(41\).

From the condition \(a^{2^r}\equiv-1\pmod p\). Then \(a^{2^{r+1}}\equiv1\), so the order of \(a\) modulo \(p\) divides \(2^{r+1}\). But the order does not divide \(2^r\), otherwise \(a^{2^r}\equiv1\), not \(-1\). Among the divisors of \(2^{r+1}\), the only one not dividing \(2^r\) is \(2^{r+1}\). Hence the order is \(2^{r+1}\), and it divides \(p-1\).

Let \(q\) be a common prime divisor of \(F_m\) and \(F_n\), \(m

Take \(F_n=2^{2^n}+1\) for \(n\ge k-1\). Every prime divisor \(q\) of \(F_n\) is odd and, by the Fermat-type lemma, satisfies \(q\equiv1\pmod{2^{n+1}}\), hence also \(q\equiv1\pmod{2^k}\). The numbers \(F_n\) are pairwise coprime, so their prime divisors for different \(n\) do not repeat. Therefore infinitely many such primes exist.

Let \(d=\operatorname{ord}_p(a)\). From \(a^6\equiv1\pmod p\), we get \(d\mid6\). The conditions \(p\nmid a^3-1\) and \(p\nmid a^2-1\) mean \(d\nmid3\) and \(d\nmid2\). Among the divisors of \(6\), only \(6\) divides neither \(2\) nor \(3\). Hence \(d=6\). The order modulo a prime divides \(p-1\), so \(6\mid p-1\), meaning \(p\equiv1\pmod6\).

By Fermat, \(2^{10}\equiv1\pmod{11}\). Since \(2026\equiv6\pmod{10}\), we get \(2^{2026}\equiv2^6=64\equiv9\pmod{11}\).

Since \(\gcd(2,9)=1\), Euler gives \(2^6\equiv1\pmod9\). Since \(100\equiv4\pmod6\), \(2^{100}\equiv2^4=16\equiv7\pmod9\).

Directly, \(7\cdot2=14\equiv1\pmod{13}\). Thus the inverse is \(2\). This agrees with Fermat: \(7^{12}\equiv1\), so \(7^{11}\) is also an inverse.

Since \(11\) is prime, \(10!\equiv-1\equiv10\pmod{11}\).

Use the formula: \(\varphi(45)=45(1-1/3)(1-1/5)=45\cdot2/3\cdot4/5=24\).

If \(p\mid a\), then \(a^p-a\) is divisible by \(p\). If \(p\nmid a\), Fermat gives \(a^{p-1}\equiv1\pmod p\), and multiplying by \(a\) gives \(a^p\equiv a\pmod p\).

By Fermat, \(7^{12}\equiv1\pmod{13}\). Since \(100\equiv4\pmod{12}\), \(7^{100}\equiv7^4\). Now \(7^2=49\equiv10\), so \(7^4\equiv100\equiv9\pmod{13}\).

\(\gcd(3,100)=1\), \(\varphi(100)=40\). Euler gives \(3^{40}\equiv1\pmod{100}\), hence \(3^{80}\equiv1\pmod{100}\). The last two digits are \(01\).

By Wilson, \(10!\equiv-1\pmod{11}\). But \(10!=10\cdot9\cdot8!\equiv(-1)(-2)8!\equiv2\cdot8!\). Hence \(2\cdot8!\equiv10\), so \(8!\equiv5\pmod{11}\).

By Wilson, \((p-1)!\equiv-1\pmod p\). But \((p-1)!\equiv(p-1)(p-2)!\equiv-(p-2)!\pmod p\). Hence \(-(p-2)!\equiv-1\), so \((p-2)!\equiv1\pmod p\).

We have \((p-1)!=(p-1)(p-2)(p-3)!\equiv(-1)(-2)(p-3)!\equiv2(p-3)!\pmod p\). By Wilson this equals \(-1\). Hence \(2(p-3)!\equiv-1\), so \((p-3)!\equiv -2^{-1}\pmod p\). Since \(2^{-1}\equiv (p+1)/2\), we get \((p-3)!\equiv (p-1)/2\pmod p\).

Notice that \(7^4\equiv1\pmod{100}\). Since \(222\equiv2\pmod4\), we get \(7^{222}\equiv7^2=49\pmod{100}\).

By Fermat's form, \(a^p\equiv a\pmod p\). Multiplying by \(a\), we get \(a^{p+1}\equiv a^2\pmod p\). Hence \(p\mid a^{p+1}-a^2\).

Since \(8!\) contains factors \(3\) and \(6\), the product is divisible by \(9\). Thus \(8!\equiv0\pmod9\), not \(-1\). There is no contradiction: Wilson's theorem states \((p-1)!\equiv-1\pmod p\) for prime \(p\), while \(9\) is composite.

Euler's theorem gives \(a^{\varphi(n)}\equiv1\pmod n\). But \(a\cdot a^{\varphi(n)-1}=a^{\varphi(n)}\). Hence \(a^{\varphi(n)-1}\) is indeed the inverse.

For \(p=2\), \(2^{p-1}+1=3\) is not divisible by \(2\). If \(p\) is odd, Fermat gives \(2^{p-1}\equiv1\pmod p\). Then \(2^{p-1}+1\equiv2\pmod p\), not \(0\). Answer: there are no such primes.

In the set \(1,2,\ldots,p-1\), every residue has an inverse. Residues equal to their own inverses satisfy \(x^2\equiv1\pmod p\), hence \(x\equiv1\) or \(x\equiv-1\pmod p\). All other residues pair as \(x,x^{-1}\), and each pair has product \(1\). Therefore \((p-1)!\equiv1\cdot(-1)\equiv-1\pmod p\).

The self-inverse elements satisfy \(x^2\equiv1\pmod p\), so they are \(1\) and \(-1\). The product of all nonzero residues is \((p-1)!\equiv-1\pmod p\). Removing the factors \(1\) and \(-1\), the remaining product is \((-1)/(1\cdot(-1))\equiv1\pmod p\).

\(\gcd(11,72)=1\), \(\varphi(72)=72(1-1/2)(1-1/3)=24\). Thus \(11^{24}\equiv1\pmod{72}\). Since \(2026\equiv10\pmod{24}\), we need \(11^{10}\pmod{72}\). Now \(11^2=121\equiv49\), \(11^4\equiv49^2=2401\equiv25\), \(11^8\equiv25^2=625\equiv49\). Hence \(11^{10}=11^8\cdot11^2\equiv49\cdot49=2401\equiv25\pmod{72}\).

Suppose \(n\) is composite. If \(n=4\), then \(3!=6\equiv2\pmod4\), not \(-1\). Now let \(n\ne4\). Write \(n=ab\), where \(1

\(72=2^3\cdot3^2\), hence \(v_2(72)=3\).

\(1000=2^3\cdot5^3\). Therefore \(v_5(1000)=3\).

By Legendre's formula, \(v_3(50!)=16+5+1=22\).

The number of zeros is \(v_5(80!)=\lfloor80/5\rfloor+\lfloor80/25\rfloor=16+3=19\).

\(v_2(100!)=50+25+12+6+3+1=97\). Thus the largest \(k\) is \(97\).

\(v_2(2026!)=1013+506+253+126+63+31+15+7+3+1=2018\).

We need \(2k\le v_2(100!)=97\) and \(k\le v_3(100!)=48\). Hence \(k\le48\) in both cases, and the answer is \(48\).

\(v_3(30!)=10+3+1=14\), \(v_3(10!)=3+1=4\), \(v_3(20!)=6+2=8\). Therefore \(v_3\left(\binom{30}{10}\right)=14-4-8=2\).

Let \(a=p^r u\), \(b=p^s v\), where \(p\nmid u\) and \(p\nmid v\). Then \(ab=p^{r+s}uv\), and \(p\nmid uv\). Hence the exponent of \(p\) in \(ab\) is \(r+s\), namely \(v_p(a)+v_p(b)\).

Since \(12=2^2\cdot3\), the number of zeros is \(\min(\lfloor v_2(100!)/2\rfloor, v_3(100!))=\min(48,48)=48\).

By Legendre's formula, \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots\). Each term is at most the corresponding \(n/2^i\), and the sum of floors is strictly less than \(n/2+n/4+\cdots=n\). Thus \(v_2(n!)

\(v_2(200!)=197\), \(v_3(200!)=66+22+7+2=97\), \(v_5(200!)=40+8+1=49\). Since \(30^k\) requires \(k\) copies of each prime \(2,3,5\), the answer is \(\min(197,97,49)=49\).

\(v_5(100!)=20+4=24\), \(v_5(25!)=5+1=6\), \(v_5(75!)=15+3=18\). The difference is \(24-6-18=0\). Hence \(\binom{100}{25}\) is not divisible by \(5\).

\(\prod_{i=1}^{100} i(i+1)=(1\cdot2\cdots100)(2\cdot3\cdots101)=100!\cdot101!\). Thus the exponent of \(2\) is \(v_2(100!)+v_2(101!)=97+97=194\). Answer: \(194\).

\(v_2(100!)=97\), \(v_2(50!)=25+12+6+3+1=47\). Therefore the required exponent is \(97-47=50\).

We need to prove \(v_2((2n)!)-2v_2(n!)>0\). Let \(n=2^t u\), where \(u\) is odd. In Legendre's sum, consider the term with \(2^{t+1}\): \(\lfloor2n/2^{t+1}\rfloor-2\lfloor n/2^{t+1}\rfloor=\lfloor u\rfloor-2\lfloor u/2\rfloor=1\). All other terms are nonnegative, so \(v_2\left(\binom{2n}{n}\right)\ge1\).

Let \(A=(m+1)(m+2)\cdots(m+n)\). Among these \(n\) numbers, at least \(\lfloor n/p\rfloor\) are divisible by \(p\), at least \(\lfloor n/p^2\rfloor\) are divisible by \(p^2\), and so on. Therefore \(v_p(A)\ge\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots=v_p(n!)\). This holds for every prime \(p\), so \(n!\mid A\).

Legendre's formula implies the identity \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots=n-s_2(n)\), where \(s_2(n)\) is the sum of binary digits of \(n\). The condition \(2^{n-1}\mid n!\) is equivalent to \(v_2(n!)\ge n-1\), that is, \(n-s_2(n)\ge n-1\). Hence \(s_2(n)\le1\). For a positive integer \(n\), this means the binary representation has exactly one \(1\), so \(n\) is a power of two. Conversely, if \(n=2^r\), then \(s_2(n)=1\), hence \(v_2(n!)=n-1\), and the divisibility holds.

\(v_2(150!)=75+37+18+9+4+2+1=146\). \(v_3(150!)=50+16+5+1=72\). For \(36^k=2^{2k}3^{2k}\), we need \(2k\le146\) and \(2k\le72\), so \(k\le73\) and \(k\le36\). Answer: \(36\).

By Legendre, \(v_3(n!)=\lfloor n/3\rfloor+\lfloor n/9\rfloor+\cdots\). This sum is strictly less than \(n/3+n/9+\cdots=n/2\), hence certainly less than \(n\). Therefore \(v_3(n!)

By LTE, \(v_3(10^{2025}-1)=v_3(10-1)+v_3(2025)=v_3(9)+4=2+4=6\).

By LTE, \(v_7(8^{100}-1)=v_7(7)+v_7(100)=1+0=1\).

\(v_5(6^{50}-1)=v_5(5)+v_5(50)=1+2=3\).

Since \(3\mid2+1\) and \(100\) is even, \(v_3(2^{100}-1)=v_3(3)+v_3(100)=1\).

\(v_2(3^{100}-1)=v_2(2)+v_2(4)+v_2(100)-1=1+2+2-1=4\).

\(v_7(8^n-1)=1+v_7(n)\). We need \(1+v_7(n)\ge3\), i.e. \(v_7(n)\ge2\). Answer: all \(n\) divisible by \(49\).

From Problem 1, \(v_3(10^{2025}-1)=6\). Since \(9^k=3^{2k}\), \(2k\le6\), hence \(k=3\).

By LTE, \(v_5(11^n-1)=v_5(10)+v_5(n)=1+v_5(n)\).

\(v_3(4^n-1)=v_3(3)+v_3(n)=1+v_3(n)\).

By the \(a+b\) case, \(v_3(5^{2n}-1)=v_3(6)+v_3(2n)=1+v_3(n)\).

If \(n\) is odd, \(v_2(5^n-1)=v_2(5-1)=2\). If \(n\) is even, \(v_2(5^n-1)=v_2(4)+v_2(6)+v_2(n)-1=2+1+v_2(n)-1=2+v_2(n)\).

If \(n\) is odd, \(v_2(3^n-1)=v_2(2)=1\), not enough. If \(n\) is even, then \(v_2(3^n-1)=v_2(2)+v_2(4)+v_2(n)-1=2+v_2(n)\). We need \(2+v_2(n)\ge4\), so \(v_2(n)\ge2\). Answer: \(4\mid n\).

We need \(1+v_3(n)\ge5\), i.e. \(v_3(n)\ge4\). Answer: \(81\mid n\).

By LTE, \(v_p(a^{p^{r-1}}-b^{p^{r-1}})=v_p(a-b)+v_p(p^{r-1})\). Since \(p\mid a-b\), the first term is at least \(1\), and the second equals \(r-1\). The total exponent is at least \(r\), so divisibility by \(p^r\) follows.

\(2^{2n}-1=4^n-1\). Since \(3\mid4-1\), \(v_3(4^n-1)=1+v_3(n)\). Therefore \(k=1+v_3(n)\).

By LTE, \(v_3(13^n-1)=v_3(12)+v_3(n)=1+v_3(n)\).

By LTE, \(v_3(10^n-1)=v_3(9)+v_3(n)=2+v_3(n)\). We need \(2+v_3(n)\ge n\). The values \(n=1,2,3\) work. If \(n\ge4\), then \(2+v_3(n)

We need \(1+v_7(n)\ge n\). For \(n=1\), the condition holds. If \(n\ge2\), then \(v_7(n)\le \log_7 n

By LTE, \(v_p(a^n-b^n)=v_p(a-b)+v_p(n)=1+v_p(n)\). The divisibility \(p^r\mid a^n-b^n\) is equivalent to \(1+v_p(n)\ge r\), i.e. \(v_p(n)\ge r-1\). This is equivalent to \(p^{r-1}\mid n\).

\(v_2(3^{2^m}-1)=v_2(3-1)+v_2(3+1)+v_2(2^m)-1=1+2+m-1=m+2\).

We have \(xy+2x+3y+6=60\), hence \((x+3)(y+2)=60\). Since \(x,y>0\), we need \(x+3\ge 4\), \(y+2\ge 3\). The suitable divisor pairs of \(60\) are \((4,15),(5,12),(6,10),(10,6),(12,5),(15,4),(20,3)\). Thus \((x,y)=(1,13),(2,10),(3,8),(7,4),(9,3),(12,2),(17,1)\). Each pair checks in the original equation.

From \(10x+10y=xy\), we get \(xy-10x-10y=0\), hence \((x-10)(y-10)=100\). Thus \(x=10+d\), \(y=10+\frac{100}{d}\), where \(d\) runs over the positive divisors of \(100\). The answer is \((11,110),(12,60),(14,35),(15,30),(20,20),(30,15),(35,14),(60,12),(110,11)\).

We write \((x-y)(x+y)=105\). The two factors must have the same parity; since the product is odd, both are odd. The factor pairs are \((1,105),(3,35),(5,21),(7,15)\). They give \((x,y)=(53,52),(19,16),(13,8),(11,4)\).

Modulo \(n+5\), we have \(n^2+7\equiv 25+7=32\). Therefore \(n+5\mid 32\). Since \(n+5>5\), we get \(n+5=8,16,32\). Hence \(n=3,11,27\). Direct checking shows that all three values work.

If \(q=2\), then \(p^2=124\), impossible. Thus \(p,q\) are odd, and \(p-q\), \(p+q\) are positive even factors of \(120\). Check \((2,60),(4,30),(6,20),(10,12)\). These give \((p,q)=(31,29),(17,13),(13,7),(11,1)\). The last one is invalid because \(1\) is not prime. The answer is \((31,29),(17,13),(13,7)\).

The equation is equivalent to \(xy-4x-7y=9\). Add \(28\): \((x-7)(y-4)=37\). Since \(37\) is prime, the only factor pairs are \((1,37)\) and \((37,1)\). Thus \((x,y)=(8,41)\) and \((44,5)\).

We get \(8x+8y+8=xy\), so \(xy-8x-8y=8\). Therefore \((x-8)(y-8)=72\). For every positive divisor \(d\mid 72\), \(x=8+d\), \(y=8+\frac{72}{d}\). The solutions are \((9,80),(10,44),(11,32),(12,26),(14,20),(16,17),(17,16),(20,14),(26,12),(32,11),(44,10),(80,9)\).

Rewrite the equation as \((x+y)(x-y)-2(x+y)=21\), hence \((x+y)(x-y-2)=21\). Let \(A=x+y\), \(B=x-y-2\). The positive factor pairs \((A,B)\) are \((1,21),(3,7),(7,3),(21,1)\). The first two give nonpositive \(y\). From \((7,3)\) we get \(x=6,y=1\), and from \((21,1)\) we get \(x=12,y=9\). The answer is \((6,1),(12,9)\).

We have \((x+2)^2-y^2=15\), so \((x+2-y)(x+2+y)=15\). The positive factor pairs with the same parity are \((1,15)\) and \((3,5)\), both odd. They give \((x,y)=(6,7)\) and \((2,1)\). Both check in the original equation.

If \(2n+1\mid n^2+n+10\), then \(2n+1\mid 4(n^2+n+10)\). But \(4n^2+4n+40=(2n+1)^2+39\). Hence \(2n+1\mid 39\). Since \(2n+1>1\) and is odd, \(2n+1=3,13,39\). Thus \(n=1,6,19\), and all three work.

An integer square modulo \(4\) is \(0\) or \(1\). The right side satisfies \(4xy+3\equiv 3\pmod 4\). The left side can be \(0,1,\) or \(2\) modulo \(4\), but never \(3\). Contradiction. Therefore there are no integer solutions.

The equation gives \(y(x+1)=x^2-x-11\). But \(x^2-x-11=(x+1)(x-2)-9\). Hence \(x+1\mid 9\). Since \(x>0\), \(x+1=3\) or \(9\). For \(x=2\), we get \(y=-3\), invalid. For \(x=8\), we get \(9y=45\), so \(y=5\). The answer is \((8,5)\).

Since \(x\le y\le z\), \(1=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\le \frac{3}{x}\), so \(x\le 3\). If \(x=1\), the remaining sum is \(0\), impossible. If \(x=2\), then \(\frac{1}{y}+\frac{1}{z}=\frac{1}{2}\), so \((y-2)(z-2)=4\). With \(y\le z\), this gives \((y,z)=(3,6),(4,4)\). If \(x=3\), then \(\frac{1}{y}+\frac{1}{z}=\frac{2}{3}\). Since \(y\ge 3\), the maximum possible left side is \(\frac{2}{3}\), so \(y=z=3\). The answer is \((2,3,6),(2,4,4),(3,3,3)\).

We have \(x^2+y^2=(60-x-y)^2\). Expanding and simplifying gives \(xy-60x-60y+1800=0\), so \((x-60)(y-60)=1800\). Since \(x,y<60\), put \(a=60-x\), \(b=60-y\). Then \(ab=1800\), and the hypotenuse is \(a+b-60\), so we need \(a<60\), \(b<60\), \(a+b>60\). The suitable divisor pairs are \((36,50)\) and \((40,45)\), with swaps. We get the side triples \(24,10,26\) and \(20,15,25\). The answer is \((10,24,26)\) and \((15,20,25)\).

The equation is equivalent to \((x-y)^2=x+y\). Let \(d=|x-y|\). Then \(x+y=d^2\). If \(x\ge y\), then \(x-y=d\), hence \(x=\frac{d^2+d}{2}\), \(y=\frac{d^2-d}{2}\). Positivity requires \(d\ge 2\). Conversely, every \(d\ge 2\) gives positive integers satisfying the equation. Including the swapped order, the answer is \(\left(\frac{d(d+1)}{2},\frac{d(d-1)}{2}\right)\) and its swap, where \(d=2,3,4,\ldots\).

If \(x,y\ge 2\), then \(x^2+y^2-xy-1=(x-y)^2+xy-1\ge 3>0\), so \(x^2+y^2>xy+1\). The divisibility is then impossible because the positive divisor is larger than the positive number. If \(x=1\), the condition becomes \(1+y^2\mid y+1\), which is possible only for \(y=1\). The case \(y=1\) is symmetric. The pair \((1,1)\) indeed works: \(2\mid 2\). The answer is \((1,1)\).

If \(N+1\) is composite, take the block \(N+2,N+3,\ldots,2N+1\). Every prime \(p\le N\) divides the product of any \(N\) consecutive integers, because one of them is divisible by \(p\). Every prime \(p\) with \(N+2\le p\le 2N+1\) appears in the block as one of the factors. The skipped number \(N+1\) is not prime.

If \(N+1\) is prime, take the block \(N+3,N+4,\ldots,2N+2\). Primes \(p\le N\) are again covered by a block of length \(N\). The prime \(N+1\) divides the last term \(2N+2=2(N+1)\). The number \(N+2\) is not prime: if \(N+1\) is prime and greater than \(3\), then \(N+1\) is odd, so \(N+2\) is even and greater than \(2\); the case \(N=2\) is excluded. Primes between \(N+3\) and \(2N+1\) appear in the block. Thus the required block exists in both cases.

From \(x\le y\le z\), we get \(\frac{3}{x}\ge \frac{1}{2}\), so \(x\le 6\). If \(x=1\), the sum is already greater than \(\frac{1}{2}\); if \(x=2\), the remaining fractions would have to sum to \(0\), impossible.

If \(x=3\), then \(\frac{1}{y}+\frac{1}{z}=\frac{1}{6}\), so \((y-6)(z-6)=36\). With \(y\le z\), this gives \((y,z)=(7,42),(8,24),(9,18),(10,15),(12,12)\).

If \(x=4\), then \(\frac{1}{y}+\frac{1}{z}=\frac{1}{4}\), so \((y-4)(z-4)=16\). We get \((5,20),(6,12),(8,8)\).

If \(x=5\), then \(\frac{1}{y}+\frac{1}{z}=\frac{3}{10}\). Multiplying and completing a product gives \((3y-10)(3z-10)=100\). With \(y\ge 5\) and \(y\le z\), the only suitable choice is \(3y-10=5\), hence \((y,z)=(5,10)\).

If \(x=6\), then \(\frac{1}{y}+\frac{1}{z}=\frac{1}{3}\). Since \(y,z\ge 6\), the maximum is \(\frac{1}{3}\), so \(y=z=6\). The answer is \((3,7,42),(3,8,24),(3,9,18),(3,10,15),(3,12,12),(4,5,20),(4,6,12),(4,8,8),(5,5,10),(6,6,6)\).

Let \(D=n^2+3n+3\). From \(n^2\equiv -3n-3\pmod D\), we get \(n^3\equiv -3n^2-3n\equiv 9n+9-3n=6n+9\pmod D\). Thus \(n^3-1\equiv 6n+8\pmod D\), so \(D\mid 6n+8\). For \(n\ge 5\), \(D=n^2+3n+3>6n+8\), impossible. Checking \(n=1,2,3,4\), only \(n=1\) works, since \(7\mid 0\). The answer is \(n=1\).

From \(x\le y\le z\), we have \(\frac{3}{x}\ge \frac{2}{3}\), hence \(x\le 4\). The value \(x=1\) is impossible because \(\frac{1}{x}=1>\frac{2}{3}\).

For \(x=2\): \(\frac{1}{y}+\frac{1}{z}=\frac{1}{6}\), so \((y-6)(z-6)=36\). With \(y\le z\), this gives \((y,z)=(7,42),(8,24),(9,18),(10,15),(12,12)\).

For \(x=3\): \(\frac{1}{y}+\frac{1}{z}=\frac{1}{3}\), so \((y-3)(z-3)=9\). We get \((y,z)=(4,12),(6,6)\).

For \(x=4\): \(\frac{1}{y}+\frac{1}{z}=\frac{5}{12}\). Multiplying and completing a product gives \((5y-12)(5z-12)=144\). We need \(y\ge 4\), \(y\le z\), hence \(5y-12\le 12\), and this divisor must be congruent to \(3\) modulo \(5\). Among divisors of \(144\) not exceeding \(12\), the possibilities are \(3\) and \(8\); \(3\) gives \(y=3\), invalid, while \(8\) gives \(y=4,z=6\). The answer is \((2,7,42),(2,8,24),(2,9,18),(2,10,15),(2,12,12),(3,4,12),(3,6,6),(4,4,6)\).

If \(x^2=2y^2\), then \(x^2\) is even, so \(x=2u\). Then \(4u^2=2y^2\), hence \(y^2=2u^2\), and \(y\) is also even: \(y=2v\). We get \(u^2=2v^2\), a smaller positive solution. Infinite descent is impossible.

From \(x^2=5y^2\), \(5\mid x^2\), hence \(x=5u\). Then \(25u^2=5y^2\), so \(y^2=5u^2\), and \(5\mid y\). With \(y=5v\), we get \(u^2=5v^2\), a smaller solution. Impossible.

Modulo \(3\), \(x^2+y^2\equiv 0\). This is possible only when \(x\equiv y\equiv 0\pmod 3\). Then \(9\mid x^2+y^2\), so \(9\mid 3z^2\), and \(3\mid z\). Dividing \(x,y,z\) by \(3\), we get a smaller nonzero solution. Contradiction.

Squares modulo \(7\) are \(0,1,2,4\). A sum of two such residues can be \(0\) modulo \(7\) only if both residues are \(0\). Hence \(7\mid x\) and \(7\mid y\). Then \(49\mid x^2+y^2\), so \(7\mid z\). Dividing all variables by \(7\) gives a smaller solution, impossible.

The right side is divisible by \(4\). A square modulo \(4\) is \(0\) or \(1\). For \(x^2+y^2\equiv 0\pmod 4\), both squares must be \(0\), so \(x,y\) are even. Thus \(x,y\) have common divisor \(2\), so the solution cannot be primitive.

Let \(x\le y\) and take a minimal solution. As a quadratic in \(y\), the equation is \(Y^2-4xY+x^2+1=0\). The second root is \(y'=4x-y=\frac{x^2+1}{y}\), positive and integral. Since \(y\ge x\), \(y'\le x+\frac{1}{x}\), so \(y'\le x\). Equality \(y'=x\) would give \(y=3x\), hence \(x^2+9x^2+1=12x^2\), or \(2x^2=1\), impossible. We get a smaller solution. For \(x=1\), the discriminant is \(16-8=8\), not a square. Contradiction.

Let \(x\le y\) and take a minimal solution. For \(x=1\), \(y^2-3y+3=0\) has no integer roots; for \(x=2\), \(y^2-6y+6=0\) also has no integer roots. For \(x\ge 3\), the second root is \(y'=3x-y=\frac{x^2+2}{y}\), positive and integral. Since \(y\ge x\), \(y'\le x+\frac{2}{x}

Let \(x\le y\). For \(x=1\), \(y^2-3y+2=0\), so \(y=1\) or \(2\). For \(x>1\), the second root is \(y'=3x-y=\frac{x^2+1}{y}\). It is positive and integral. Since \(y\ge x\), \(y'\le x+\frac{1}{x}1\), \(0

Write \(Y^2-mxY+x^2+c=0\). One root is \(y\). By Vieta's formula, the sum of the roots is \(mx\), so the second root is \(y'=mx-y\). Since the coefficients are integers and \(y'\) is assumed to be a positive integer, substituting the second root again makes the quadratic zero. Hence \(x^2+(y')^2+c=mxy'\).

Let \(x\le y\) and take a solution with minimal sum. For \(x=1\), we get \(y^2-ky+2=0\). Its discriminant \(k^2-8\) is not a square: if \(k^2-8=t^2\), then \((k-t)(k+t)=8\), impossible for \(k\ge 4\). Now let \(x\ge 2\). The second root is \(y'=kx-y=\frac{x^2+1}{y}\), positive and integral. Since \(y\ge x\), \(y'\le x+\frac{1}{x}

Consider \(Z^2-3xyZ+x^2+y^2=0\). One root is \(z\), the other is \(z'=3xy-z\). The product of the roots is \(x^2+y^2>0\), so \(zz'>0\); since \(z>0\), \(z'>0\). By Vieta's formula, the second root satisfies the same quadratic equation, so \(x^2+y^2+(z')^2=3xyz'\).

Fourth powers modulo \(7\) are \(0,1,2,4\). A sum of two such residues can be \(0\pmod 7\) only as \(0+0\). Hence \(7\mid x\) and \(7\mid y\). Write \(x=7x_1\), \(y=7y_1\). Then the left side is divisible by \(7^4\), so \(7z^2\) is divisible by \(7^4\), meaning \(z^2\) is divisible by \(7^3\). Since valuations in a square are even, \(7^2\mid z\); write \(z=49z_1\). Substitution gives \(7^4(x_1^4+y_1^4)=7\cdot 7^4 z_1^2\), hence \(x_1^4+y_1^4=7z_1^2\). We have obtained a smaller positive solution. Infinite descent is impossible, so no original solution exists.

If \(p\nmid y\), then \((xy^{-1})^2\equiv -1\pmod p\). Raise both sides to \(\frac{p-1}{2}\). The left side is \(1\), while the right side is \((-1)^{(p-1)/2}=-1\), since \(p\equiv 3\pmod 4\). Contradiction. Hence \(p\mid y\), and then \(p\mid x\) follows from \(p\mid x^2+y^2\).

Since \(11\equiv 3\pmod 4\) and \(11\mid x^2+y^2\), we get \(11\mid x\) and \(11\mid y\). Then \(121\mid x^2+y^2=11z^2\), so \(11\mid z\). Dividing all variables by \(11\), we obtain a smaller nonzero solution. Infinite descent is impossible.

The equation gives \(p\mid x^2+y^2\). By the lemma for primes \(3\pmod 4\), \(p\mid x\) and \(p\mid y\). Then \(p^2\mid x^2+y^2=pz^2\), so \(p\mid z^2\), hence \(p\mid z\). Dividing \(x,y,z\) by \(p\), we get a smaller nonzero solution of the same equation. This gives infinite descent, impossible in positive integers.

From \(x^4+y^4\equiv 0\pmod 3\), both \(x\) and \(y\) are divisible by \(3\). Then the left side is divisible by \(81\), so \(3z^4\) is divisible by \(81\), and \(z\) is divisible by \(3\). Dividing \(x,y,z\) by \(3\) preserves the equation and gives a smaller nonzero solution. Contradiction.

A fourth power modulo \(5\) is \(0\) or \(1\). Therefore \(x^4+y^4\equiv 0\pmod 5\) implies \(5\mid x\) and \(5\mid y\). Then \(5^4\mid x^4+y^4=5z^4\), so \(5^3\mid z^4\), hence \(5\mid z\). Dividing all variables by \(5\), we get a smaller nonzero solution of the same equation. Contradiction.

Squares modulo \(5\) are \(0,1,4\). Thus \(2y^2\) has residues \(0,2,3\). The sum \(x^2+2y^2\) can be \(0\pmod 5\) only if both terms are \(0\). Hence \(5\mid x,y\). Then \(25\mid x^2+2y^2=5z^2\), so \(5\mid z\). Dividing all variables by \(5\), we get a smaller solution of the same equation. Contradiction.

By Problem 8, all solutions are neighbouring terms of the sequence \(1,1,2,5,13,34,89,233,\ldots\), where \(a_{n+1}=3a_n-a_{n-1}\). The bound \(x+y\le 150\) leaves the neighbouring pairs \((1,1),(1,2),(2,5),(5,13),(13,34),(34,89)\) and their swaps. The pair \((89,233)\) already has sum greater than \(150\).

Let \(x\le y\). For \(x=1\), \(y^2-4y+4=0\), so \(y=2\). For \(x=2\), \(y^2-8y+7=0\), so \(y=1\) or \(7\); this matches neighbouring terms of the future sequence. For \(x=3\), the discriminant \(144-48=96\) is not a square. For \(x\ge 4\), the second root is \(y'=4x-y=\frac{x^2+3}{y}\), positive and integral. Since \(y\ge x\), \(y'\le x+\frac{3}{x}

Reversing the jump: if \((a,b)\) is a solution, then \((b,4b-a)\) is also a solution. Starting from \((1,2)\), define \(a_0=1\), \(a_1=2\), \(a_{n+1}=4a_n-a_{n-1}\). All solutions are \((a_n,a_{n+1})\) and swaps, \(n\ge 0\).

Substitute: \(9t+4\equiv 7\pmod {11}\), so \(9t\equiv 3\pmod {11}\). Since \(9^{-1}\equiv 5\pmod {11}\), \(t\equiv 15\equiv 4\pmod {11}\). Thus \(x=9(11s+4)+4=99s+40\). The answer is \(x\equiv 40\pmod {99}\).

From the first two conditions: \(x=4a+1\), \(4a+1\equiv 2\pmod 5\), so \(4a\equiv 1\), \(a\equiv 4\pmod 5\). Hence \(x\equiv 17\pmod {20}\). Now \(20b+17\equiv 3\pmod 7\), or \(6b\equiv 0\pmod 7\), so \(b\equiv 0\pmod 7\). The least positive solution is \(x=17\).

If \(x\equiv 2\pmod 6\), then \(x\equiv 2\pmod 3\). If \(x\equiv 3\pmod 9\), then \(x\equiv 0\pmod 3\). The same integer cannot have two different residues modulo \(3\). Therefore there are no solutions.

The common divisor of \(12\) and \(18\) is \(6\), and \(17-5=12\) is divisible by \(6\), so the system is compatible. Let \(x=12t+5\). Then \(12t+5\equiv 17\pmod {18}\), so \(12t\equiv 12\pmod {18}\). Divide by \(6\): \(2t\equiv 2\pmod 3\), hence \(t\equiv 1\pmod 3\). Therefore \(x=12(3s+1)+5=36s+17\). The answer is \(x\equiv 17\pmod {36}\).

The conditions mean \(N\equiv -1\pmod 3\), \(N\equiv -1\pmod 5\), \(N\equiv -1\pmod 7\). Hence \(N\equiv -1\pmod {105}\). For example, \(N=104\).

We need \(N\equiv 3\pmod 4\), \(N\equiv 3\pmod 5\), \(N\equiv 6\pmod 9\). The first two conditions give \(N\equiv 3\pmod {20}\). Let \(N=20t+3\). Then \(20t+3\equiv 6\pmod 9\), so \(2t\equiv 3\pmod 9\). The inverse of \(2\) modulo \(9\) is \(5\), hence \(t\equiv 15\equiv 6\pmod 9\). The least \(N\) is \(20\cdot 6+3=123\).

From \(4n+1\equiv 0\pmod 9\), \(4n\equiv 8\), so \(n\equiv 2\pmod 9\). From \(5n-2\equiv 0\pmod {11}\), \(5n\equiv 2\), and \(5^{-1}\equiv 9\pmod {11}\), so \(n\equiv 18\equiv 7\pmod {11}\). Solve \(n=9t+2\), \(9t+2\equiv 7\pmod {11}\), so \(9t\equiv 5\). Since \(9^{-1}\equiv 5\), \(t\equiv 25\equiv 3\pmod {11}\). The answer is \(n\equiv 29\pmod {99}\).

Impose \(N+1\equiv 0\pmod 2\), \(N+2\equiv 0\pmod 3\), \(N+3\equiv 0\pmod 5\), \(N+4\equiv 0\pmod 7\). Thus \(N\equiv 1\pmod 2\), \(N\equiv 1\pmod 3\), \(N\equiv 2\pmod 5\), \(N\equiv 3\pmod 7\). By CRT, a solution exists modulo \(210\). One solution is \(N=157\). Then \(158,159,160,161\) are divisible by \(2,3,5,7\), respectively, and are larger than those divisors; hence they are composite.

We have \(385=5\cdot 7\cdot 11\). For each of the moduli \(5,7,11\), the congruence \(x^2\equiv 1\) has two solutions: \(x\equiv 1\) and \(x\equiv -1\). The moduli are pairwise coprime, so the choices combine independently. There are \(2^3=8\) solutions modulo \(385\).

There are four systems. \((1,1)\) gives \(x\equiv 1\). \((-1,-1)\) gives \(x\equiv -1\equiv 34\). For \(x\equiv 1\pmod 5\), \(x\equiv -1\pmod 7\), checking \(1,6,11,16,21,26,31\) gives \(6\). For \(x\equiv -1\pmod 5\), \(x\equiv 1\pmod 7\), we get \(29\). The answer is \(1,6,29,34\pmod {35}\).

Let \(d=\gcd(m,n)\). If \(x\) is a solution, then \(m\mid x-a\), \(n\mid x-b\), so \(d\mid (x-a)\) and \(d\mid (x-b)\), hence \(d\mid a-b\). Conversely, suppose \(d\mid a-b\). Write \(m=dm_1\), \(n=dn_1\), \(\gcd(m_1,n_1)=1\). Seek \(x=a+mt\). We need \(a+d m_1t\equiv b\pmod {dn_1}\), or \(m_1t\equiv \frac{b-a}{d}\pmod {n_1}\). Since \(m_1\) is coprime to \(n_1\), it has an inverse, and such \(t\) can be chosen. Thus the system is solvable.

We need to solve \(N\equiv -1\pmod 3\), \(N\equiv -2\pmod 5\), \(N\equiv -3\pmod 7\), \(N\equiv -4\pmod {11}\), \(N\equiv -5\pmod {13}\). The moduli are pairwise coprime, so by CRT a solution exists modulo \(M=3\cdot 5\cdot 7\cdot 11\cdot 13\). If \(N_0\) is one solution, then all \(N=N_0+tM\) are also solutions. There are infinitely many.

Require \(n\equiv 0\pmod 5\), \(n+2\equiv 0\pmod 7\), \(n+6\equiv 0\pmod {11}\). This is \(n\equiv 0\pmod 5\), \(n\equiv 5\pmod 7\), \(n\equiv 5\pmod {11}\). The moduli are coprime, so there is a solution \(n_0\) modulo \(385\). All \(n=n_0+385t\) have the same divisibility properties. For sufficiently large \(t\), the numbers \(n,n+2,n+6\) are larger than their assigned divisors, hence composite. There are infinitely many.

The moduli \(8,3,5,7\) are pairwise coprime. Modulo \(8\), all odd residues \(1,3,5,7\) square to \(1\), so there are \(4\) solutions. For each of \(3,5,7\), there are \(2\) solutions: \(\pm 1\). By CRT, the total number is \(4\cdot 2\cdot 2\cdot 2=32\).

For \(k=2\), this is the usual CRT. Suppose the statement is true for \(k-1\) moduli. The first \(k-1\) conditions are equivalent to one congruence \(x\equiv r\pmod M\), where \(M=m_1\cdots m_{k-1}\). Since \(m_k\) is coprime to each \(m_i\), \(\gcd(M,m_k)=1\). By CRT, \(x\equiv r\pmod M\), \(x\equiv r_k\pmod {m_k}\) is solvable. The induction is complete.

Let \(A=(k+1)!\). The numbers \(A+2,A+3,\ldots,A+(k+1)\) form \(k\) consecutive integers. For each \(j=2,\ldots,k+1\), \(A+j\) is divisible by \(j\), because \(A\) is divisible by \(j\). Also \(A+j>j\), so \(A+j\) is composite. This gives the required block.

Choose distinct primes \(p_1,\ldots,p_k>k\). Consider the system \(N+i\equiv 0\pmod {p_i}\) for \(i=1,\ldots,k\), or \(N\equiv -i\pmod {p_i}\). The moduli are pairwise coprime, so by CRT there is a solution \(N_0\) modulo \(P=p_1\cdots p_k\). Every \(N=N_0+tP\) also works. For sufficiently large \(t\), \(N+i>p_i\), so each \(N+i\) is composite and has its assigned prime divisor \(p_i>k\).

Since \(m_i>1\), choose a residue \(b_i\) different from \(a_i\) modulo \(m_i\). By CRT there exists \(x_0\) such that \(x_0\equiv b_i\pmod {m_i}\) for all \(i\). Then all \(x=x_0+tM\), where \(M=m_1\cdots m_k\), have the same residues modulo all \(m_i\). Hence they avoid all forbidden classes, and there are infinitely many such integers.

Choose pairwise distinct primes \(p_1,\ldots,p_k\) so large that \(p_i>|a_i-a_j|\) for all \(i,j\). The system \(N\equiv -a_i\pmod {p_i}\) is solvable by CRT. Let \(N_0\) be a solution and \(P=p_1\cdots p_k\). Then \(N=N_0+tP\) preserves all divisibilities \(p_i\mid N+a_i\). For sufficiently large \(t\), all \(N+a_i\) are positive and larger than \(p_i\), hence composite. There are infinitely many such \(t\).

For an odd prime \(p\), the congruence \(u^2\equiv 1\pmod p\) has only the solutions \(u\equiv \pm 1\pmod p\), because \((u-1)(u+1)\equiv 0\pmod p\). Therefore the condition “not congruent to \(\pm 1\) modulo any \(p_i\)” is incompatible with \(x^2\equiv 1\pmod {p_i}\) for every odd prime. Such an \(x\) does not exist for any choice of \(p_i\). Answer: the claim is false.