2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ What does $(b:54)=3$ mean? Is that not division? $\endgroup$
    – Arthur
    Jun 22, 2019 at 6:50
  • $\begingroup$ @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. $\endgroup$ Jun 22, 2019 at 7:14
  • $\begingroup$ Why do you say that $3$ does not divide $b$ and then go on to use $b\equiv0\mod{3}$? $\endgroup$ Jun 22, 2019 at 7:35
  • $\begingroup$ Notice this is poły in a, use hansels lemma to get the result for (mod 9) $\endgroup$
    – Kran
    Jun 22, 2019 at 7:42
  • $\begingroup$ 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. $\endgroup$ Jun 22, 2019 at 15:10

3 Answers 3

2
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$ Jun 22, 2019 at 16:37
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Note $ $ question was changed from find $\,a\bmod 8\,$ to find $\,a\bmod 18\ \ $ $\endgroup$ Jun 22, 2019 at 16:28
0
$\begingroup$

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)
$\endgroup$
3
  • 1
    $\begingroup$ 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\ \ $ $\endgroup$ Jun 22, 2019 at 17:02
  • $\begingroup$ @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. $\endgroup$ Jun 22, 2019 at 17:37
  • 1
    $\begingroup$ e.g. by the Binomial Theorem or Double Root Test, see here. $\endgroup$ Jun 22, 2019 at 17:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .