Find the required gcd

Question

Question: Let $\gcd(a,n)=d_1\gt 1$ and $\gcd(b,n)=d_2\gt 1$, given that $\gcd(d_1,d_2)=1$, find $\gcd(a+b,n)$.

My try Since $\gcd(a,n)=d_1$ so $a=pd_1$ and since $\gcd(b,n)=d_2$ so $b=qd_2$.

My guess is since the greatest common divisors of $a,b$ have gcd =1, so $\gcd(a+b,n)=1$. But I cant prove it in a compact and well defined fashion

Can someone please help me out?

The question boils down to this:

How is $\gcd(a+b,n)$ related to $\gcd(a,n)$ and $\gcd(b,n)$?

Answer 1

As counter-examples to $\gcd(a+b,n)=1$, let $n=ab(a+b)$, for example $30$.

Answer 2

I don't think this is answerable.

Deep breath. Let's break everything down to "components".

$\gcd(n,a) = d_1$ so let $\alpha = \frac a{d_1}$ so $a = d_1\alpha$ and let $\nu = \frac n{d_1}$ so $n = d_1\nu$. It's easy to verify that $\alpha$ and $\nu$ are relatively prime. But $\alpha$ and $d_1$ and $\nu$ and $d_1$ may have factors in common, but the factors that $d_1$ his in common with $\alpha$ must be relatively prime to the factors in common with $\nu$.

Let $k_1 =\gcd(d_1, \alpha)$ and $m_1\gcd(d_1, \nu)$ so that we may express $a = d_1k_1a'$ and $n=d_1m_1\overline n$ where: $d_1,d_2$ are relatively prime; $j_1,m_1$ are relatively prime but $k_1,m_1|d_1$; and $a',\overline n$ are relatively prime.

We can do the same for $b$ so that $b=d_2k_2b'$ and $n = d_2m_2\overline{\underline n}$.

Now $d_1$ is relatively prime to $d_2$ and $m_1|d_1$ and $m_2|m_2$ so $d_1m_1$ is relatively prime to $d_2m_2$ so $d_1m_1|\overline{\underline n}$.

And so we can write $n = d_1m_1d_2m_2n'$.

So $\gcd(a+b,n)=$

$\gcd(d_1k_1a' + d_2k_2b', d_1m_1d_2m_2n')=$.

$\gcd(d_1k_1a' + d_2k_2b', n')$

(The last step is acceptable as $d_1,m_1,d_2,m_2$ each divide one of the summands but is relatively prime to the other summand, therefore $d_1m_1d_2m_2$ is relatively prime to $d_1k_1a' + d_2k_2b'$)

And this can be pretty much any thing we want provided we chose the terms so that they are mutually relatively prime.

Suppose, for example, I want $\gcd(a+b, n) = 39$.

I can let $n'=39$ and $a+b=39$ and $a=d_1k_1a'= 20$ with $d_1=4$ and $k_1=1;a'=5$ and $b=d_2k_2b'=19$ with $d_1=19;k_1=b'=1$.

Then $n=4\cdot 19\cdot 39 = 2964$

And thus we have $\gcd(20,2964)= 4$ and $\gcd(19,2964)=19$. And $\gcd(20,19)=1$. And $\gcd(20+19,2964)=\gcd(39,2964)= 39$.