Vtyjkyuk

Given two numbers $x gt 0$ and $y gt 0$, find the greatest number $a$ such that $amid 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 $amid x$?

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 xgcd(x,y) = frac A*D*ED = 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 wgcd(w,y) = frac textthe stuff that has nothing to do with ytimestext the stuff in common with ytext that xtext has too much oftextthe 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 zgcd(y, z) = fractextthe stuff that had nothing to do with y timestext the extra stuff that x had too much of if any is lefttext 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$.

Let $gcd(x,y)=d$. If $d=1$ then $$a=x$$ if not let's define $gcd(d,a)=d_1$. If $d_1ne 1$ therefore $$d_1mid a,x\d_1mid d,y$$so $$d_1midgcd(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=dfracxd$ therefore we conclude that $$max a=dfracxgcd(x,y)$$

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_iprod p_i^n_iprod s_i^o_i)$

And $y = (prod u_i^d_i)(prod s_i^e_i)(prod q_i^m_iprod p_i^n_iprod s_i^o_i)$

Let $D = (prod q_i^m_iprod p_i^n_iprod 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 xgcd(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 xgcd(x,y)= frac 2^5*13*3^17*5^2*7^53^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^123^5 = 2^5*13*3^7$.

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

$overline x = frac x''gcd(x'',y) = frac 2^5*13*3^73^5 = 2^5*13*3^2$.

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

$z = frac overline xgcd(overline x,y) = frac 2^5*13*3^23^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$.

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_pX$, $y=p^s_pY$, 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:
begincases
textif r_ple s_p,quad pnmid x'=dfrac xd ,\[1ex]
textif r_p > s_p,quad p^r_p-s_pmid x'.
endcases
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$.

Let $x_1=x.$ For $nin Bbb N$ let $x_n+1=x_n/gcd (x_n,y).$ We have $x_n+1leq x_n$ but we cannot have $x_n+1<x_n$ for every $n,$ otherwise $(x_n)_nin 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_nimplies a|x_n+1,$ suppose $x_n=ab_n$ with $b_nin 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_nin Bbb N.$$

So let $x_n=ab_n$ for each $n,$ with $b_nin 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_nleq a.$ Therefore $b_n=1$ and $x_n=ab_n=a.$