0
$\begingroup$

I have two integers $m,n\in \mathbb{Z}$ and I would like to find in order to solve the following equation over $\mathbb{Z}$:

$$84m+165n=117$$

I guess we need to use the Euler algorithm but I'm not sure how. I have used it only when we spoke about one divisor. How to solve it?

$\endgroup$
1
  • 4
    $\begingroup$ I assume you mean you want to find $m,n$? First, it helps to divide by $3$ to get $28m+55n=39$. Then first solve $28A+55B=1$ That's small enough to do by trial and error (or just inspection, really). To do it via the Euclidean Algorithm, see, e.g., this. $\endgroup$
    – lulu
    Jul 13, 2019 at 10:58

4 Answers 4

1
$\begingroup$

Hint:

By the Euclidean algorithm, $\gcd{(84, 165)} = 3$ and $3 | 117$. Therefore your equation can be rewritten as $28p + 55q = 39$ where $p = 3m$ and $q = 3n$.

Let us try to find solutions such that $28p' + 55q' = 1$. We can immediately notice that $p' = 2, q' = -1$. So $28(39 \cdot 2) + 55(39 \cdot -1) = 39$ and $84(39 \cdot 2) + 165(39 \cdot -1) = 117$.

This is only one solution. Can you find a simpler solution, and then find the general solution?

$\endgroup$
4
  • $\begingroup$ I think you meant $28p+55q=39$ $\endgroup$
    – vesii
    Jul 13, 2019 at 11:06
  • $\begingroup$ Yes, thanks for the correction! $\endgroup$
    – Toby Mak
    Jul 13, 2019 at 11:07
  • $\begingroup$ You mean that $3\mid 117$. $\endgroup$
    – azif00
    Jul 13, 2019 at 11:15
  • $\begingroup$ Edited, thanks. $\endgroup$
    – Toby Mak
    Jul 13, 2019 at 11:19
1
$\begingroup$

So, $2×28-1×55=1\implies 78×28-39×55=39$. Thus $n=78, m=-39$ is a solution.

Now the general solution is $(78+55k,-39-28k)$, as this is a linear diophantine equation.

$\endgroup$
0
1
$\begingroup$

$\!\!\bmod \color{#90f}{84}\!:\ 33 \equiv\overbrace{ 117 \equiv 165n}^{\large 117\ \ =\ \ 165n\ +\ \color{#90f}{84m}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!} \equiv -3n\!$ $\overset{\ \large \ \div\,\color{#c00}3_{\phantom |}}\iff \! \bmod 28\!:\ \overbrace{n \equiv 33/(-3) = -11}^{\large \color{#0a0}{n\ \ =\ \ -11\ +\ 28\,k}}$

Cancelling $\,\color{#c00}3\, \Rightarrow\, 39 = 55\color{#0a0}n+28m$ $\iff m \, =\, \dfrac{39-55(\color{#0a0}{-11\!+\!28k})}{28}= 23-55k$

$\endgroup$
0
$\begingroup$

$165n=117-84m=3(39-28m)$ is divisible by $3.$ So $n$ is divisible by $3.$ So let $n=3n'.$ Dividing through by $3$ we have $28m+165n'=39 .$ We have $$165n'\equiv 39 \mod 28 \iff$$ $$\iff 165n'-28(6n')\equiv 39-28 \mod 28 \iff$$ $$\iff -3n'\equiv 11 \mod 28 \iff$$ $$\iff 9(-3n')\equiv 9(11)\mod 28 \iff$$ $$\iff 28n'+9(-3n') \equiv 9(11)-3(28)\mod 28 \iff$$ $$\iff n'\equiv 15 \mod 28.$$ The main idea is in the 3rd & 4th lines above, where an expression $An'\equiv B$ is multiplied by some $C$ (that's co-prime to $28 $ ) to get $ACn'\equiv BC ,$ which reduces mod $28$ to some $A'n'\equiv B'$ in which $|A'|$ is (much) smaller than $|A|.$ So eventually we reach $A'=\pm 1.$ In this Q we only need to do this once.

So it is necessary that $n'=15+28 n''$ for some $n''$ (and hence $n=3n'=45+84n''.$) And this is also sufficient because $$84m+165n=117 \iff 28m+165 n'=39 \iff $$ $$\iff 28m+165(15+28n'')=39 \iff m=87+165n''.$$

Therefore $\{(87+165n'',\,45+84n''): n''\in \Bbb Z\}$ is the set of all possible $(m,n)$.

$\endgroup$

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.