Find m and n where m + n = 72, and gcd (m , n) = 9 [duplicate]

Solution 1:

Hint

Use $$\gcd(a,b)\text{lcm}(a,b)=ab\implies ab=12[\gcd(a,b)]^2$$and note that since $a=bq+5$, if $\gcd(b,5)=1$ then $$\gcd(a,b)=1$$and if $5|b$ then $b=5k$ and consecutively $$\gcd(a,b)=\gcd(5kq+5,5k)=5\gcd(kq+1,k)=5$$Now you can enumerate the cases handily and obtain the result.

Solution 2:

Remember $lcm(a,b) = \frac {ab}{\gcd(a,b)}$.

So $\frac {ab}{\gcd(a,b)}= 12\gcd(a,b)$ and

$\frac {a}{\gcd(a,b)}\frac {b}{\gcd(a,b)}= 12$.

Let $a' = \frac a{\gcd(a,b)}; b' =\frac b{\gcd(a,b)} = 12$ so

$(a',b') = \{(1,12), (2,6), (3,4),(4,3), (6,2), (12,1)\}$.

But $\gcd(a',b') = 1$ so $(a',b') \ne (2,6)$ or $(6,2)$.

Now $a= mb + 5$ for some integer $m$

So we have $a'\gcd(a,b) = mb'\gcd(a,b) + 5$. Let $d = \gcd(a,b)$ and we have:

$a'd =md + 5$

$(a'-mb')d = 5$

$d = \frac {5}{a'-mb'}$

$5$ is prime so $a'-mb' = 1,5$.

We have 4 cases $(a',b') = (1,12), (3,4), (4,3), (12,1)$.

Case 1: $a'=1;b'=12$ and $1-12m = \pm 1, \pm 5$. That can only be $m=0$ and $d=5$ and $a=1*5=5; b=12*5= 60$. Then $5 = 0*60 + 5$ and $lcm(5,60)= 60=12*5=12\gcd(5,60)$.

Case 2: $a'=3;b'=4$ and $3-4m =1,5$. That's impossible.

Case 3: $a'=4;b'=3$ and $4-3m=1,5$. That can only be $m=1$ and $d=5$ and $a=4*5=20$ and $b=3*5 =15$. and $20 = 1*15+5$ and $lcm(20,15) =60=12*5=12\gcd(20,15)$

Case 4: $a'=12; b'=1$ and $12-3m = 1,5$. That's impossible.

Solution 3:

Hint $\ $ As here cancelling $\,d := \gcd(a,b)$ from both sides we reduce to the case $\,\bar a,\bar b\,$ coprime

$$\bar a \bar b = 12,\,\ \gcd(\bar a,\bar b) = 1,\,\ {\rm for}\ \ \bar a,\,\bar b := a/d,\,b/d\qquad $$

Examining coprime factorizations $\,\bar a\bar b = 12 = \color{#90f}{1\cdot 12} = \color{#0a0}{3\cdot 4}\,$ satisfying our constraint

$$ \color{#c00}5 = a\bmod b = \bar ad\bmod \bar bd = (\color{#c00}{\bar a \bmod \bar b})\,d\qquad $$

we see $2$ of the $4$ possibilities satisfy $\,\color{#c00}{\bar a \bmod \bar b}\,$ divides $\color{#c00}5,\,$ e.g. $\,\color{#0a0}{4\bmod 3}\,$ does but not $\,\color{#0a0}{3\bmod 4}$. Check the same for $\color{#90f}{1\cdot 12}$ and we're done. Total solution time: a minute of easy mental arithmetic.

Remark $ $ The key idea used above is that we can reduce to that case of $\,a,b\,$ coprime by cancelling $\gcd(a,b),\,$ since the equation is homogeneous in $\,a,b,\,$ due to the distributive law for lcm and gcd, i.e. $\,{\rm lcm}(a,b) = d\,{\rm lcm}(a/b,b/d) = {\rm lcm}(\bar a,\bar b),\,$ $\,\gcd(a,b) = d\gcd(a/d,b/d) = d\gcd(\bar a,\bar b).\ $ This reduction makes the problem so simple that we can quickly finish purely mentally, i,e. check the $4$ possible coprime $\rm\color{#90f}{split}\color{#0a0}{tings}$ of $12$ to see which satisfy the mod $\rm\color{#c00}{constraint}$.

Such homogeneous reduction often leads to analogous simplifications, e.g. see here and here and here for further examples. In more advanced contexts one doesn't explicitly change variables $\,a,b\to \bar a,\bar b\,$ then cancel $\,d;\,$ rather one simply writes: "being homogeneous in $\,a,b\,$ wlog we may reduce to the case $\,a,b\,$ coprime $\ldots$".