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

Question

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.

Answer 1

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

Answer 2

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