Let's define $b:= a^{226} +4a +1$. We know that $b$ is odd because $54$ is even and the gcd is odd. But if $a$ were odd, $b$ would be even; so $a$ is also even.
We also know that $3\nmid a$ (since $3\nmid b$, if it did divide $a$, it would be a divisor of $1$, which is absurd.) Applying Fermat's theorem, we have
$$a^{226} + 4a + 1 = (a^2)^{113} + 4a + 1 \equiv 4a + 2 \equiv 0 \pmod 3$$
This means that $a \equiv 1 \pmod 3$. We infer the following congruences:
$$a \equiv 0 \pmod2 \\ a \equiv 1 \pmod 3$$
If I had a $\pmod 9$ instead of a $\pmod 3$ in the last congruence, I'd be able to aply the Chinese Remainder Theorem.
How can I bound the values of $r_{9}(a)$, given that $r_{3}(a)=1$?
Best Answer
You already got $a\equiv 1\bmod 3$, which means $a\equiv 1,4\hbox{ or }7\bmod 9$. We would like to check which of them is the one that works.
Now, you can look $\mod 9$ by using Euler's theorem. Since $\gcd(a,9)=1$ you can apply Euler's theorem. We have $\varphi(9)=6$, so $$a^{226}+4a+1=(a^6)^{38}a^{-2}+4a+1\equiv \overline{a}^2+4a+1\mod 9$$ where $\overline{a}$ denotes the inverse of $a\bmod 9$.
Now let's check:
If $a\equiv 1\bmod 9$, then $\overline{a}^2+4a+1\equiv 6\mod 9$
If $a\equiv 4\bmod 9$, then $\overline{a}^2+4a+1\equiv 12\mod 9$
If $a\equiv 7\bmod 9$, then $\overline{a}^2+4a+1\equiv 0 \mod 9$
As you can see, if $a\equiv 7\bmod 9$, we have $a^{226}+4a+1$ is divisible by $9$ hence in this case $\gcd(54,a^{226}+4a+1)$ is divisible by $9$. This case is discarded.
We conclude that $$a\equiv 0\bmod 2$$ $$a\equiv 1 \hbox{ or }4\bmod 9$$ By chinese remainder theorem we conclude
$$a\equiv 10 \hbox{ or }4\bmod 18$$
Edit: @Bill Dubuque showed an easier way to compute $a^{226}+4a+1\bmod 9$ in this case. Check that if $a\equiv 1,4,7\bmod 9$ then $a^3\equiv 1\bmod 9$. Hence, $a^{226}+4a+1\equiv a+4a+1=5a+1\bmod 9$