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

• What does $(b:54)=3$ mean? Is that not division? – Arthur Jun 22 '19 at 6:50
• @Arthur I'm fairly sure $(m:n)$ stands for $\gcd(m,n)$. Somebody else use that notation here recently, so it is in use somewhere on the globe. – Jyrki Lahtonen Jun 22 '19 at 7:14
• Why do you say that $3$ does not divide $b$ and then go on to use $b\equiv0\mod{3}$? – Peter Foreman Jun 22 '19 at 7:35
• Notice this is poły in a, use hansels lemma to get the result for (mod 9) – Kran Jun 22 '19 at 7:42
• You used Fermat's theorem to analyze mod 3, just use Euler's theorem(which is a generalization of Fermat's) to analyze mod 9. – Julian Mejia Jun 22 '19 at 15:10

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

• @Bill Dubuque, I see, yeah I was thinking that there may be some reduction like this one $a\equiv 1,4,7\mod 9$ implies $a\equiv b^2$ (b=1,2,4). So this also proves $a^3\equiv b^6\equiv 1\bmod 9$. The lemma you showed me is quite interesting, thanks. – Julian Mejia Jun 22 '19 at 16:37

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

• Note  question was changed from find $\,a\bmod 8\,$ to find $\,a\bmod 18\ \$ – Bill Dubuque Jun 22 '19 at 16:28

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)

• You missed $\,a\equiv 4\pmod{\!18}\$ because $\,\bmod 3\!:\ a\equiv 1\,$ $\not\Rightarrow\,\bmod 9\!:\ a^{\large 2}\equiv 1,\,$ rather $\,a^{\large 3}\equiv 1\ \$ – Bill Dubuque Jun 22 '19 at 17:02
• @BillDubuque Yes, you right! But I still cant understand, how derives imply $a^3\equiv1$. Only CRT work, without Hensels lemma. I will correct answer. – Dmitry Ezhov Jun 22 '19 at 17:37
• e.g. by the Binomial Theorem or Double Root Test, see here. – Bill Dubuque Jun 22 '19 at 17:46