Find the remainder of the division of $a$ by $18$ knowing that $\gcd(a^{226} +4a +1, 54)=3$

Question

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$?

Answer 1

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$

Answer 2

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$.

Answer 3

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)