# Let $\gcd(x_1,n)=d_1, \gcd(x_2,n)=d_2$ where $1\le x_1,x_2\le n-1$. Find $\gcd(x_1,x_2)$.

Let $$\gcd(x_1,n)=d_1, \gcd(x_2,n)=d_2$$ where $$1\le x_1,x_2\le n-1$$, $$n$$ is a given positive fixed integer. Find $$\gcd(x_1,x_2)$$.

I am stuck at finding the $$\gcd(x_1,x_2)$$. My try

Let $$\gcd(x_1,x_2)=d$$. Then $$d\mid x_1,d\mid x_2$$. So $$x_1=ad_1,x_2=bd_2$$.

But I am stuck at how to use the facts $$\gcd(x_1,n)=d_1, \gcd(x_2,n)=d_2$$. If someone could kindly help me out, I will be grateful.

• Use the fact: $gcd(x_{1},n)=ax_{1}+bn$, for $a,b \in \mathbb{Z}$ and $gcd(x_{2},n)=kx_{2}+ln$ for $k,l \in \mathbb{Z}$ – hJulian Apr 22 '20 at 14:24
• @Andrew; how does that help – Math_Freak Apr 22 '20 at 15:54
• I guess $\gcd(x_1,x_2)=1$ too – Learnmore Apr 23 '20 at 2:41

The problem information is insufficient. Let $$n=2^{10}\times3^{10}\times5^{10}\times7^{10}$$ and $$a=2\times 3\times p_1$$ , $$b=5\times 7\times p_2$$ where $$p_1$$ and $$p_2$$ are two sufficiently small (and not necessarily distinct) primes greater than or equal to $$11$$. Hence $${d_1=6\\d_2=35\\\gcd(d_1,d_2)=1\\\gcd(a,b)=\gcd(p_1,p_2)}$$setting $$p_1=p_2$$ yields to any arbitrary value for $$\gcd(a,b)$$.

Here is my updated solution (the old one was incorrect, you can find it in the edit history):

Let $$d=\gcd(x_1,x_2)$$. Write $$x_1=a_1d_1$$ and $$x_2=a_2d_2$$. Then $$\gcd(d,d_1)$$ divides $$d$$, so it divides $$x_2$$. $$\gcd(d,d_1)$$ also divides $$d_1$$, so it divides $$n$$. Therefore $$\gcd(d,d_1)$$ divides $$\gcd(x_2,n)=d_2$$, so it divides $$\gcd(d_1,d_2)=1$$.

Thus $$d|a_1d_1$$ and $$\gcd(d,d_1)=1$$. By Euclid's lemma, $$d|a_1$$. Similarly, $$d|a_2$$, so $$d|\gcd(a_1,a_2)$$. But $$\gcd(a_1,a_2)|d$$, so $$\gcd(x_1,x_2)=\gcd(a_1,a_2)=\gcd(\frac{x_1}{d_1},\frac{x_2}{d_2})$$

• Why the downvote? – Bladewood Apr 22 '20 at 17:30
• hmm, I can think of three reasons: I poorly presented my answer, I gave the whole answer when the asker only wanted help (to be understood as a hint), or the answer itself is wrong. If it's the last case, I would be glad to see where my mistake is :) – Isaac Ren Apr 22 '20 at 19:00
• Okay, so I realized the problem got updated, so I tried updating my solution... but I realized my reasoning was completely off! $d\nmid d_1$ does not imply $d|a_1$. I'll think about this some more... – Isaac Ren Apr 22 '20 at 19:16
• Thanks for the effort. But unfortunately it does not solve my problem, the solution brings $\gcd(x_1,x_2)$ in terms of $a_1,a_2$ but $a_1,a_2$ are themeselves unknown variables – Math_Freak Apr 23 '20 at 2:39
• $a_1$ and $a_2$ are known, if you allow for euclidean division in the ring of integers, since they are respectively $x_1/d_1$ and $x_2/d_2$. I updated my answer to show that. If that doesn't satisfy you, then Mostafa Ayaz's answer shows that we cannot do any better. – Isaac Ren Apr 23 '20 at 8:15