Find the remainder of the division of $a$ by $18$ knowing that $\gcd(a^{226} +4a +1, 54)=3$ 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$?
 A: 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$
A: Let's try to find a solution where all steps can be performed without computer.
binomial expansion and reduction of the big power
You found $a=6c+4$. In the binomial expansion of $(6c+4)^{226}$ all powers of $6$ from the third on are divisible by $54$. $\binom{226}{2}=113\cdot 225$ is divisible by $9$, so that also the quadratic coefficient reduces to zero modulo $54$. Thus
$$
(6c+4)^{226}\equiv 226⋅(6c)⋅4^{225}+4^{226}=(113⋅3c+1)⋅4^{226}\pmod{54}
$$
reduction of the dyadic powers
Then with
$$
2^{18}=(64)^3\equiv 10^3\equiv -80\equiv 28\pmod{54}\implies 2^{18k+1}\equiv 2\pmod{54}
$$
we can reduce
$$
4^{226}=2^{25⋅18+2}\equiv 2^2=4\pmod{54}
$$
equivalent GCD conditions
The GCD identity then reduces to
$$
GCD\left((15c+1)⋅4+4⋅(6c+4)+1,54\right)=3\\
GCD(30c+21,54)=3\\ GCD(10c+7,18)=1
$$
which is satisfied for $c\not\equiv 2\pmod3$.
($10c+7$ is invertible $\bmod{18}$, the multiplicative group is $\{1,5,7,11,13,17\}+18\Bbb Z=\pm1+6\Bbb Z$, thus $10c\in \{0,4\}+6\Bbb Z$,  $-2c\in \{0,-2\}+6\Bbb Z$ and consequently $c\in\{0,1\}+3\Bbb Z$.) 
(new) conclusion $a\bmod{18}$
Combining the parametrizations together we get that either 


*

*$a=6(3k)+4=18k+4$ giving $a\equiv 4\pmod{18}$ or 

*$a=6(3k+1)+4=18k+10$ giving $a\equiv 10\pmod{18}$.


old conclusion $a\bmod8$
With $c=3k$ one gets $a=18k+4\equiv 2k+4\pmod 8$ and with $c=3k+1$ likewise $a=18k+10\equiv 2k+2\pmod 8$.
A: Let $A=a^{226}+4a+1$.
$GCD(A,54)=3\quad\Longrightarrow\quad A\not\equiv_20\wedge A\equiv_30\wedge A\not\equiv_90 \quad\Longrightarrow\quad  a\equiv_20\wedge a\equiv_31\wedge a\equiv_9(0,1,2,3,4,5,6,8)$
? for(r=0,1,m=Mod(r,2);if(m^226+4*m+1==1,print1(r", ")))
0,
? for(r=0,2,m=Mod(r,3);if(m^226+4*m+1==0,print1(r", ")))
1,
? for(r=0,8,m=Mod(r,9);if(m^226+4*m+1!=0,print1(r", ")))
0, 1, 2, 3, 4, 5, 6, 8,

$a\equiv_31\wedge a\equiv_9(0,1,2,3,4,5,6,8) \quad\overset{CRT}{\Longrightarrow}\quad a\equiv_9(1,4)$
? for(r=0,8,if(r!=7,CRT=iferr(chinese(Mod(1,3),Mod(r,9)),E,0);if(CRT,print1(CRT", "))))
Mod(1, 9), Mod(4, 9),

$a\equiv_20\wedge a\equiv_9(1,4) \quad\overset{CRT}{\Longrightarrow}\quad a\equiv_{18}(4,10)$
? chinese(Mod(0,2),Mod(1,9))
%72 = Mod(10, 18)
? chinese(Mod(0,2),Mod(4,9))
%71 = Mod(4, 18)

