0
$\begingroup$

Through many operations in an exercise I've reached this point

$17≡4a+19b(mod$ $27)$

$8≡11a(mod$ $27)$

I want to find both a and b to have the answer I need, I've been trying to use the Chinese rest theorem but found it doesn't work in my case, I'm starting converting the second one into

$11a+27a≡1(mod$ $27)$

Despite this I'm not sure if is correct and I still don't know how to clear this $a$ in the second equation in order to replace it in the first.

Any help will be really appreciated

$\endgroup$
2
$\begingroup$

There are a number of ways to go about this. We want to be able to "divide" by $11$, so we need $8 + 27x = 11y$. Solving this linear Diophantine equation (an elementary problem, feel free to Google) gives $x = 5$ and $y = 13$ as possible solutions. Then, \begin{align} 8 &\equiv 11a \mod{27}\\ 8 + 27\cdot 5 &\equiv 11a \mod{27}\\ 13(11) &\equiv 11a \mod{27}\\ 13 &\equiv a \mod{27} \end{align} Then $a = 13 + 27k$ for some $k \in \mathbb{Z}$. You can subtract $4$ times the last congruence above from $17 \equiv 4a + 19b \mod{27}$ to get \begin{align} 17 - 4(13) &\equiv 19b \mod{27}\\ -35 &\equiv 19b \mod{27}\\ -35 + 2(27) &\equiv 19b \mod{27}\\ 19 &\equiv 19b \mod{27}\\ b &\equiv 1 \mod{27} \end{align}

$\endgroup$
4
  • $\begingroup$ But you should say how you computed $k$ such that $\,11\mid 8+27k,\,$ not simply pull it out of hat like magic! Else how is the OP supposed to figure out how to use the method for similar problems? $\endgroup$ – Bill Dubuque Oct 22 '18 at 19:11
  • $\begingroup$ @BillDubuque I alluded to it in my explanation... Solving a linear Diophantine equation is usually a skill that's learned in sections immediately preceding problems like this. For the record though, the Euclidean algorithm with back substitution is the most systematic way of doing it (again, Google is your friend). $\endgroup$ – AlkaKadri Oct 22 '18 at 19:59
  • $\begingroup$ Back-substitution is clumsy and error-prone. Better to use this version, or Gauss's algorithm below $$\!\bmod 11\!:\ \, 27x\!+\!8\equiv 0\iff x\equiv \dfrac{-8}{27}\equiv \dfrac{3}{-6}\equiv \dfrac{-1}{2}\equiv \dfrac{10}2\equiv 5\ $$ In any case, it's not a good idea to say "Google it" in an answer. Google can locate all sorts of nonsense (low-quality, errorneous, crankish, etc). $\endgroup$ – Bill Dubuque Oct 22 '18 at 20:22
  • $\begingroup$ @BillDubuque ah I see.. Yes you have a point there, I’ll certainly refrain from doing that in future answers. Thanks Bill! $\endgroup$ – AlkaKadri Oct 22 '18 at 20:25
2
$\begingroup$

Just so long as you avoid multiplying or dividing by a multiple of $3$ you can use ordinary arithmetic - so you can multiply the first by $11$ and the second by $4$ to isolate a term in $b$ using standard elimination. You avoid $3$ because the base $27$ has the prime factor $3$.

You can solve $ax+by=1$ for coprime $a$ and $b$ using the division algorithm to find their highest common factor (which is $1$ because they are coprime). Other methods are available, and sometimes work more quickly if you spot them. The division algorithm provides a proof that there is always a solution, and a systematic way of finding it.

$\endgroup$
1
  • 1
    $\begingroup$ +1 Eliminating $a$ by cross multiplying yields $-2\equiv\!\!\overbrace{ 5}^{\large 44a}\!\!-7b\,\Rightarrow\, 7b\equiv 7\,\Rightarrow\, b\equiv 1\,$ (use least magnitude reps!), which is probably easier than computing inverses. $\endgroup$ – Bill Dubuque Oct 22 '18 at 19:01
1
$\begingroup$

Guide:

\begin{align} 27 &= 11(2)+5 \\ 11 &= 2(5)+1 \end{align}

\begin{align} 1 &= 11-2(5)\\ &= 11 - 2(27-2(11)) \\ &= 5(11)-2(27) \end{align}

Hence $$11^{-1} \equiv 5 \pmod{27}$$

Now you should be able to solve for $a$, substitute that to the first equation and solve for $b$ using similar procedure.

$\endgroup$
1
$\begingroup$

\begin{align*} 11a & \equiv 8 \pmod{27}\\ 55a & \equiv 40 \pmod{27}\\ a & \equiv 13 \pmod{27}. \end{align*} Now plug this in the first congruence to get $b$.

$\endgroup$
4
  • $\begingroup$ But you should say how you computed the inverse of $11,\,$ not simply pull it out of a hat like magic! $\endgroup$ – Bill Dubuque Oct 22 '18 at 19:05
  • $\begingroup$ @BillDubuque My intention was not to pull a magic for OP. But when OP says (in his question) that he/she tried using the Chinese Remainder Theorem, then I would assume familiarity of such a step (multiplying by an inverse) on his/her part. One can always seek more explanation if needed. $\endgroup$ – Anurag A Oct 23 '18 at 16:21
  • $\begingroup$ But the question makes it clear the OP is having difficulty inverting $\,11\bmod 27.\,$ Giving the answer with no hint how it was computed is probably not going to help the OP get past their obstacles. $\endgroup$ – Bill Dubuque Oct 23 '18 at 16:36
  • $\begingroup$ It is not that I disagree with your suggestion of adding more but it is a judgement call. When someone says CRT etc. and yet misses some basic step, then one can argue either way about his/her understanding of the basic material. Perhaps OP overlooked some simple step or perhaps OP has difficulty with the concept of inverse. I grapple with this on a daily basis :-) $\endgroup$ – Anurag A Oct 23 '18 at 17:00

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.