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$
  • $\begingroup$ What does $(b:54)=3$ mean? Is that not division? $\endgroup$ – Arthur Jun 22 '19 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$ – Jyrki Lahtonen Jun 22 '19 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$ – Peter Foreman Jun 22 '19 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 '19 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$ – Julian Mejia Jun 22 '19 at 15:10
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$

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Julian Mejia Jun 22 '19 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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note $ $ question was changed from find $\,a\bmod 8\,$ to find $\,a\bmod 18\ \ $ $\endgroup$ – Bill Dubuque Jun 22 '19 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)
| cite | improve this answer | |
$\endgroup$
  • 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$ – Bill Dubuque Jun 22 '19 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$ – Dmitry Ezhov Jun 22 '19 at 17:37
  • 1
    $\begingroup$ e.g. by the Binomial Theorem or Double Root Test, see here. $\endgroup$ – Bill Dubuque Jun 22 '19 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.