Greatest number that divides $x$ and is coprime with $y$ 
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$?
 A: 
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$.
A: 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$.
A: 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)}$$
A: 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$.
A: 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.$     
