Proving prime divisibility relation between $a^2-a+3$ and $b^2-b+25$.

Question

Let $p$ be a given prime number. Prove that there exists an integer $a$ such that $p|a^2-a+3$ if and only if there exists an integer $b$ such that $p|b^2-b+25$.

I've managed to prove that if $p|a^2-a+3$ for some $a$, then $p|b^2-b+25$ for some $p$ like so:

Working mod $p$, we have $a^2-a+3=0$. Hence $9a^2-9a+27=0$, which implies $9a^2-6a+1=3a-26$. Rearranging this, we find that $$(3a-1)^2=(3a-1)-25$$ so simply taking $b=3a-1$ proves this part.

I had the idea of multiplying everything by $9$ because $3\times 9\approx 27$, and because $9$ is a square. However, I can't find a similar relation for turning $b^2-b+25$ into $a^2-a+3$.

According to the person I found this question from, this question is from a very old TST (I think it was from China, but we're not sure).

Answer 1

$3a - 1\equiv b\pmod p$

for any prime $p \ne 3$

$3$ has a multiplicative inverse.

$a \equiv 3^{-1}b + 3^{-1}\pmod p$

And if $p=3$ let $a = 1$

Answer 2

$a^2-a+3\equiv0\pmod p$

$\iff(2a-1)^2\equiv-11$ for odd $p$

$4(b^2-b+25)=(2b-1)^2+99$

So, we need $(2b-1)^2\equiv-99\pmod p$

$\implies(2b-1)^2\equiv3^2(2a-1)^2\pmod p$

$\iff2b-1\equiv\pm3(2a-1)$

Answer 3

Here is another proof, via quadratic residues. Note that, $a^2-a+3$ is odd, hence $p\neq 2$. Now, $p\mid a^2-a+3\iff p\mid (2a-1)^2+11$. Similarly, $p\mid b^2-b+25 \iff p\mid (2b-1)^2+99$. Namely, the goal is to prove, $$ \exists a: p\mid (2a-1)^2+11 \iff \exists b: p\mid (2b-1)^2+99 $$ which is equivalent to proving, $$ \left(\frac{-11}{p}\right) =1 \iff \left(\frac{-99}{p}\right) =1, $$ where, $(a/p)$ is the standard Legendre's symbol. But this last statement is obvious, since $(-99/p)=(9/p)(-11/p)=(-11/p)$, as $(9/p)=1$, due to the fact that $9$ is a quadratic residue modulo $p$.