# Solving $84m+165n=117$ over $\mathbb{Z}$

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?

• 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.
– lulu
Jul 13, 2019 at 10:58

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?

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

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.

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

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