1
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ My edit was just for a few obvious typos. $\endgroup$ – DanielWainfleet Aug 9 '18 at 20:19
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What do you mean by $(p,X) = (p, Y) = 1$ ? I cannot understand the notation! $\endgroup$ – code_master5 Aug 10 '18 at 6:21
  • $\begingroup$ @code_master5: $(p,X)$ denotes the ideal generated by $p$ and $X$. As we're in a P.I.D., this means $\gcd(p,X)=1$ – in other words, since $p$ is prime, it is not a factor of $X$. $\endgroup$ – Bernard Aug 10 '18 at 9:14
0
$\begingroup$

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

$\endgroup$

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.