Greatest number that divides $x$ and is coprime with $y$

Question

Given two numbers $x \gt 0$ and $y \gt 0$, find the greatest number $a$ such that $a\mid x$, and $a$ and $y$ are $coprimes$.

A possible solution is given here. The idea is to divide $x$ with $\gcd(x,y)$ until $\gcd(x,y)$ becomes $1$. Whatever is remaining of $x$ is the answer.

I want to understand why this solution works. How is it guaranteed to give the greatest $a$ such that $a\mid x$?

Answer 1

Informal but intuitive:

We can break $x$ done into three components: $A = $ the stuff in $x$ that has nothing to do with $y$. (This is clearly the answer to our question.) $D= \gcd(x,y) =$ the stuff $x$ and $y$ have in common and the exact amount they share. And $E = $ the stuff in common with $y$ that $x$ has too much of.

So $x = A*D*E$.

We do your algorithm. $w = \frac {x}{\gcd(x,y)} = \frac {A*D*E}{D} = A*E = $ the stuff that has nothing to do with $y$ $\times$ the stuff in common with $y$ that $x$ has too much of.

$\gcd(w,y) = \gcd($ the stuff that has nothing to do with $y$ $\times$ the stuff in common with $y$ that $x$ has too much of$, y) = $ the stuff $x$ had too much of (either the excessive amount or the amount in $y$ whichever is smaller).

So $$z = \frac {w}{\gcd(w,y)} = \frac {\text{the stuff that has nothing to do with }y\times\text{ the stuff in common with }y\text{ that }x\text{ has too much of}}{\text{the stuff x had too much of (either the excessive amount or the amount in y whichever is smaller)}}$$ = the stuff that had nothing to do with $y$ $\times$ the extra stuff that $x$ had too much of if any is left.

If there is any stuff that $x$ had too much of we continue.

$\gcd(y, z) = \gcd(y, $the extra stuff that $x$ had too much of if any is left$))$ = some smaller amount of the extra stuff that $x$ had.

And $u = \frac z{\gcd(y, z)} = \frac{\text{the stuff that had nothing to do with }y \times\text{ the extra stuff that x had too much of if any is left}}{\text{ some smaller amount of the extra stuff that x had}}$ = the stuff that had nothing to do with $y$ $\times$ a smaller amount (possibly none) of that extra stuff.

We keep repeating until we don't have any more of the extra stuff that $x$ had.

Then we are left with $a = $the stuff that had nothing to do with $y = A$.

Answer 2

Let $\gcd(x,y)=d$. If $d=1$ then $$a=x$$ if not let's define $\gcd(d,a)=d_1$. If $d_1\ne 1$ therefore $$d_1\mid a,x\\d_1\mid d,y$$so $$d_1\mid\gcd(x,y)$$ and is a contradiction. Therefore $d_1=1$. Surely the biggest $a$ such that $\gcd(x,y)=d$ and $\gcd(d,a)=1$ is $a=\dfrac{x}{d}$ therefore we conclude that $$\max a=\dfrac{x}{\gcd(x,y)}$$

Answer 3

Tantalizer except that you will find in the post below.

(Note: all that is left is the stuff in $x$ that had nothing to do with $y$, and the stuff that $x$ had too much of. We are just going to continue to get rid of the stuff that $x$ had too much of.)

Bear with me.

$x = \prod p_i^{m_i}$ and $y = \prod p_j^{n_j}$ be the unique prime factorization of $x$ and $y$.

Let's classify these primes into categories:

Let $r_i$ be the primes that factor $x$ but do not factor $y$. Let $u_i$ be the primes that factor $y$ but do not factor $x$. Let $q_i$ be the primes that factor $x$ and $y$ but factor $x$ to a higher power then they factor $y$. Let $s_i$ be the primes that factor $x$ and $y$ but factor $y$ to higher power than they factor $x$. And let $p_i$ be the primes common to both $x$ and $y$ and which factor to the same power.

So $x = (\prod r_i^{b_i})(\prod q_i^{c_i})(\prod q_i^{m_i}\prod p_i^{n_i}\prod s_i^{o_i})$

And $y = (\prod u_i^{d_i})(\prod s_i^{e_i})(\prod q_i^{m_i}\prod p_i^{n_i}\prod s_i^{o_i})$

Let $D = (\prod q_i^{m_i}\prod p_i^{n_i}\prod s_i^{o_i})= \gcd(x,y)$ and $S= (\prod u_i^{d_i})$ and $A =(\prod r_i^{b_i})$

So $x =A*(\prod q_i^{c_i})*D$ and $y=S*(\prod s_i^{e_i})*D$.

$A$ is clearly the largest number that divides $x$ but is relatively prime to $y$ (because $q_i$ and $D$ have factors in common with $y$).

So why does that algorithm result in $A$?

Start with $x' = \frac {x}{\gcd(x,y)} = A*(\prod q_i^{c_i})$.

Now $\gcd(x',y) = \prod q_i^{w_i=\min m_i, c_i}$

Do it again. Let $x'' = \frac {x'}{\gcd(x',y)} = A*(\prod q_i^{z_i =c_i-w_i})$.

Now some of those $z_i$ may equal $0$ but all the $z_i$ are smaller than $c_i$.

We keep doing this. Each step the powers of the $q_i$ get smaller and smaller. As they are finite they must eventually reduce to $0$. And we are left with $A$.

=====

It may be easier to see with an example:

Let $x = 2^5*13*3^{17}*5^2*7^5$ and $y=11^4*3^5*5^2*7^{13}$ so $\gcd(x,y) = (3^5*5^2*7^5)$ so

$x' = \frac {x}{\gcd(x,y)}= \frac {2^5*13*3^{17}*5^2*7^5}{3^5*5^2*7^5} = 2^5*13*3^{12}$. (Note: all that is left is the stuff in $x$ that had nothing to do with $y$ (i.e $2^5*13$) and the stuff that $x$ had too much of. We are just going to continue to get rid of the stuff that $x$ had too much of.)

$\gcd(x', y) = 3^5$ so

$x'' = \frac {x'}{\gcd(x',y)} = \frac {2^5*13*3^{12}}{3^5} = 2^5*13*3^7$.

$\gcd(x',y) =3^5$ so

$\overline x = \frac {x''}{\gcd(x'',y)} = \frac {2^5*13*3^{7}}{3^5} = 2^5*13*3^2$.

$\gcd(\overline x,y) = 3^2$ so

$z = \frac {\overline x}{\gcd(\overline x,y)} = \frac {2^5*13*3^{2}}{3^2} = 2^5*13$.

$\gcd(z,y) =1$ so we are done. $a = 2^5*13$ is the largest number reletive prime to $y$ that divides $x$.

Answer 4

Let's consider the prime factors common to $x$ and $y$ and see what happens to them in the algorithm.

Let $p$ be such a prime factor, and say $x=p^{r_p}X$, $y=p^{s_p}Y$, where $r_p, s_p>0$ and $(p,X)=(p,Y)=1$. We have $\;d=p^{\min(r_p,s_p)}D$, $\;(p,D)=1$.

Two cases may happen: \begin{cases} \text{if } r_p\le s_p,\quad p\nmid x'=\dfrac xd ,\\[1ex] \text{if } r_p > s_p,\quad p^{r_p-s_p}\mid x'. \end{cases} Thus, in the first case, the common prime $p$ disappears from $x'$. In the second case, it does not, but its $p$-valuation decreased: $$v_p(x')=r_p-s_p=v_p(x)-v_p(y).$$ So when we proceed with the algorithm, the valuations of all common primes decrease, until they become $0$, i.e. until all common primes have been removed from $x$. What remians, by construction is coprime with $y$, and it is the greatest divisor with this property, since it consists of all prime factors (with their valuation) of $x$ which are not prime factors of $y$.

Answer 5

Let $x_1=x.$ For $n\in \Bbb N$ let $x_{n+1}=x_n/\gcd (x_n,y).$ We have $x_{n+1}\leq x_n$ but we cannot have $x_{n+1}<x_n$ for every $n,$ otherwise $(x_n)_{n\in \Bbb N}$ would be an infinite strictly decreasing sequence of natural numbers. So for some $n$ we have $x_n=x_{n+1}.$

Theorem. If $c|(ab)$ and $\gcd (a,c)=1$ then $c|b.$

Corollary 1. If $\gcd(a,c)=1$ then $\gcd (ab,c)=\gcd(b,c).$

Corollary 2. If $\gcd(a,c)=\gcd(b,c)=1$ then $\gcd(ab,c)=1.$

Let $a$ be the largest divisor of $x$ that is co-prime to $y.$

Note: Any common divisor of $x,y$ is co-prime to $a.$

By induction on $n$ we have $a|x_n$ for every $n.$ Proof: Obvious for $n=1.$ To show that $a|x_n\implies a|x_{n+1},$ suppose $x_n=ab_n$ with $b_n\in \Bbb N.$ Let $c_n=\gcd (x_n,y).$ Now $x_n|x$ so $c_n$ is a common divisor of $x$ and $y.$ So by the above "Note" we have $\gcd (a,c_n)=1.$ So by the Theorem we have $c_n|b_n.$ Hence $$x_{n+1}=x_n/c_n=a (b_n/c_n) \text { with } b_n/c_n\in \Bbb N.$$

So let $x_n=ab_n$ for each $n,$ with $b_n\in \Bbb N.$

Now consider the least, or any, $n$ such that $x_{n+1}=x_n .$ By corollary 1 we have $$x_n=x_{n+1}=x_n/\gcd(x_n,y)=x_n/\gcd (ab_n,y)=x_n/\gcd(b_n,y)$$ and therefore $\gcd (b_n,y)=1.$ Now each of $a, b_n$ is co-prime to $y,$ so by Corollary 2, their product $ab_n,$ is co-prime to $y.$

Now $ab_n$ is a divisor of $x$ and it is co-prime to $y$ so by the def'n of $a$ we have $ab_n\leq a.$ Therefore $b_n=1$ and $x_n=ab_n=a.$