I want $a := mk^2 + mkn$ and $b := mkn + \frac{n^2m}{2}$ to be coprime. That, is I want $\gcd(a, b) = 1$. Which constraints on $m, k, n$ lead to this?

Question

Let $m$, $k$, and $n$ be integers with $m \geq 2$ being even.

Let $a := mk^2 + mkn$ and $b := mkn + \frac{n^2m}{2}$.

How can I simplify $\gcd(a, b)$? Namely, how can I simplify

$$\gcd\left(mk^2 + mkn,\ mkn + \frac{n^2m}{2}\right)$$

Or, alternatively, which constraints on $m$, $k$, and $n$ lead to $gcd(a, b) = 1$ as I want $a$ and $b$ to be coprime.

I know

• $mk \mid (mk^2 + mkn)$, and
• $m \mid (mkn + \frac{n^2m}{2})$ if $m \mid \frac{n^2m}{2}$
• $m \mid \frac{n^2m}{2}$ if $n$ is even (i.e. $2 \mid n$)

From this I can conclude that if $n$ is even, then $m | a$ and $m | b$, go $\gcd(a, b)$ is at least $m \geq 2$, but I want $\gcd(a, b) = 1$, so $n$ can't be even. This is one constraint. Are there others? And if so, what are they and how can I figure them out.

---

Same question for the scenario where $m \geq 1$ is odd and

• $a := mk^2 + 2mkn$
• $b := 2mkn + 2n^2m$

What constraints on $m, k, n$ lead to $\gcd(a, b) = \gcd(mk^2 + 2mkn, 2mkn + 2n^2m) = 1$

In this case:

• $mk \mid a$
• $2mn \mid b$

Is it fair to say that $\gcd(a, b) \geq \gcd(mk, 2mn) = m \cdot \gcd(k, 2n)$?

At the very least, we can say $\gcd(a, b)$ is at least $m >= 1$. Since I want $\gcd(a, b) = 1$, that means $m$ must equal $1$.

Would $\gcd(k, 2n) = 1$ be a constraint as well?

Answer 1

For each scenario, we show the gcd $=1\!\iff $ the boxed conditions below hold true, by applying Lemma: $\,(\color{#c00}a\color{#0a0}b,\color{darkorange}cd)=1\,$ if $\,1\!=\!(\color{#c00}a,\color{darkorange}c)\!=\!(\color{#c00}a,d)\! =\! (\color{#0a0}b,\color{darkorange}c)\!=\!(\color{#0a0}b,d)\ $ [an iteration of Euclid's Lemma], $ $ i.e. if both $\,\color{#c00}a\ \&\ \color{#0a0}b\,$ are coprime to $\,\color{darkorange}c\ \&\ d.\, $

---

Scene $2\!:\,\ 1 = m(\color{#c00}k(\color{#0a0}{k\!+\!2n}),\,\color{darkorange}{2n}({k\!+\!n})) \Rightarrow\, \bbox[5px,border:1px solid #c00]{ m=1=(\color{#c00}k,\color{darkorange}{2n})}\ \,$ If so then, conversely $$\qquad\quad\begin{align} &(\color{#c00}k,\color{darkorange}{2n}) = 1;\ \ {\rm and\,\ further}\ \ (\color{#c00}k,k\!+\!n)\ =(k,n) = 1;\ \ \rm and\\[.4em] &(\color{#0a0}{k\!+\!2n},\,\color{darkorange}{2n}) \!=\! (k,2n)\!=\!1;\ \ (\color{#0a0}{k\!+\!2n},k\!+\!n) \!=\! (n,k\!+\!n) \!=\! (n,k)\!=\!1\end{align}$$

thus our original gcd $= 1$ by the above linked Lemma.

---

Scene $1\!:\, \ 1 = m/2(2k(k\!+\!n),n(2k\!+\!n))\,\Rightarrow\, \bbox[5px,border:1px solid #c00]{m/2=1 = (n,2k)}\ $ If so then, conversely, the gcd $= 1,\,$ by the proof above, with $\,k,n\,$ swapped.