Let \( p \neq 3 \) be a prime number. Prove that there exist natural numbers \( a \), \( b \), \( c \), \( d \), none of which are divisible by \( p \), such that \( a^2 + 3b^5 + 5c^6 + 7d^7 \) is divisible by \( p^{1000} \).
Problem
Source: XIII International Festival of Young Mathematicians Sozopol 2024, Theme for 10-12 grade
Tags: number theory
29.09.2024 22:20
Here's a solution for $p\notin\{2,5,7\}$ (these cases shouldn't be too difficult, though I can't see a way right now). Below I make use of the following fact. If $p$ is a prime and $c\in\mathbb{Z}$ are such that $p\mid a^2+c$ for some $a$, then for any $n\ge 1$, there exists $a_n$ for which $p^n\mid a_n^2+c$. We prove this inductively. Let $p^n\mid a_n^2+c$. If $v_p(a_n^2+c)\ge n+1$ we set $a_{n+1}=a_n$. If not, then $v_p(a_n^2+c)=n$ and let $a_{n+1}=a_n + \ell \cdot p^n$, $\ell$ to be tuned. We get $a_{n+1}^2 + c= a_n^2 + c + 2\ell p^n + p^{2n}$. Clearly $p^{2n}\equiv 0\pmod{p^{n+1}}$. Set $a_n^2 + c= p^n u$ where $p\nmid u$. Then, ensuring $u\equiv -2\ell \pmod{p}$ ensures $p^{n+1}\mid a_{n+1}^2+c$. This completes the induction. Now suppose $p\equiv 1\pmod{4}$. Set $b\equiv c\equiv 1\pmod{p^{1000}}$, $d\equiv -1\pmod{p^{1000}}$. Since $p\equiv 1\pmod{4}$, there is $a$ for which $p^{1000}\mid a^2+1$ thanks to fact above. With this choice, we are done. Next let $p\equiv 3\pmod{4}$. First suppose $(5/p)=1$. Then taking $b\equiv d\equiv -1\pmod{p^{1000}}$, $c\equiv 1\pmod{p^{1000}}$ and $a$ such that $p^{1000}\mid a^2-5$ (such $a$ exists due to fact I established and $(5/p)=1$), we are done. Lastly, let $(5/p)=-1$. Since $p\equiv 3\pmod{4}$, we have $(-5/p)=1$. Choose $b\equiv -2\pmod{p^{1000}}$, $c\equiv 5\pmod{p^{1000}}$ and $d\equiv -3\pmod{p^{1000}}$. Then $3b^5+5c^6 + 7d^7 = 5\cdot (112)^2$, and that $5\cdot 112^2$ is a non-zero quadratic residue modulo $p$. Using the fact above one more time, there is an $a$ for which $p^{1000}\mid a^2+5\cdot 112^2$, completing the proof.