0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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}$ $\endgroup$ – hJulian Apr 22 '20 at 14:24
  • $\begingroup$ @Andrew; how does that help $\endgroup$ – Math_Freak Apr 22 '20 at 15:54
  • $\begingroup$ I guess $\gcd(x_1,x_2)=1$ too $\endgroup$ – Learnmore Apr 23 '20 at 2:41
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Why the downvote? $\endgroup$ – Bladewood Apr 22 '20 at 17:30
  • $\begingroup$ 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 :) $\endgroup$ – Isaac Ren Apr 22 '20 at 19:00
  • $\begingroup$ 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... $\endgroup$ – Isaac Ren Apr 22 '20 at 19:16
  • $\begingroup$ 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 $\endgroup$ – Math_Freak Apr 23 '20 at 2:39
  • $\begingroup$ $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. $\endgroup$ – Isaac Ren Apr 23 '20 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.