How to show gcd(ac, bd) = gcd(a,d) * gcd(b,c)
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Given that $gcd(a,b) = 1$ and $gcd(c,d) = 1$, show that $gcd(ac,bd) = gcd(a,d) * gcd(b,c)$
The work that I have done so far goes as follows.
We write $gcd(ac,bd) = acv + bdu$
then $gcd(a,d) = ax + dy$ and $gcd(b,c) = bs + ct$
then $gcd(a,d) * gcd(b,c) = (ax + dy) * (bs + ct) = axbs + axct + dybs + dyct$
I tried to factor out some terms, and get $ax(bs+ct) + dy(bs+ct)$
but then I am stuck here. I don't know what else to use to prove the answer
elementary-number-theory
New contributor
add a comment |Â
up vote
4
down vote
favorite
Given that $gcd(a,b) = 1$ and $gcd(c,d) = 1$, show that $gcd(ac,bd) = gcd(a,d) * gcd(b,c)$
The work that I have done so far goes as follows.
We write $gcd(ac,bd) = acv + bdu$
then $gcd(a,d) = ax + dy$ and $gcd(b,c) = bs + ct$
then $gcd(a,d) * gcd(b,c) = (ax + dy) * (bs + ct) = axbs + axct + dybs + dyct$
I tried to factor out some terms, and get $ax(bs+ct) + dy(bs+ct)$
but then I am stuck here. I don't know what else to use to prove the answer
elementary-number-theory
New contributor
1
Please consider using MathJax to format your question - it will make your formulas much more readable
â Zubin Mukerjee
47 mins ago
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Given that $gcd(a,b) = 1$ and $gcd(c,d) = 1$, show that $gcd(ac,bd) = gcd(a,d) * gcd(b,c)$
The work that I have done so far goes as follows.
We write $gcd(ac,bd) = acv + bdu$
then $gcd(a,d) = ax + dy$ and $gcd(b,c) = bs + ct$
then $gcd(a,d) * gcd(b,c) = (ax + dy) * (bs + ct) = axbs + axct + dybs + dyct$
I tried to factor out some terms, and get $ax(bs+ct) + dy(bs+ct)$
but then I am stuck here. I don't know what else to use to prove the answer
elementary-number-theory
New contributor
Given that $gcd(a,b) = 1$ and $gcd(c,d) = 1$, show that $gcd(ac,bd) = gcd(a,d) * gcd(b,c)$
The work that I have done so far goes as follows.
We write $gcd(ac,bd) = acv + bdu$
then $gcd(a,d) = ax + dy$ and $gcd(b,c) = bs + ct$
then $gcd(a,d) * gcd(b,c) = (ax + dy) * (bs + ct) = axbs + axct + dybs + dyct$
I tried to factor out some terms, and get $ax(bs+ct) + dy(bs+ct)$
but then I am stuck here. I don't know what else to use to prove the answer
elementary-number-theory
elementary-number-theory
New contributor
New contributor
edited 44 mins ago
greedoid
29.1k93879
29.1k93879
New contributor
asked 50 mins ago
Mario G
242
242
New contributor
New contributor
1
Please consider using MathJax to format your question - it will make your formulas much more readable
â Zubin Mukerjee
47 mins ago
add a comment |Â
1
Please consider using MathJax to format your question - it will make your formulas much more readable
â Zubin Mukerjee
47 mins ago
1
1
Please consider using MathJax to format your question - it will make your formulas much more readable
â Zubin Mukerjee
47 mins ago
Please consider using MathJax to format your question - it will make your formulas much more readable
â Zubin Mukerjee
47 mins ago
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
Take all prime factors in turn. We have the following relations between the multiplicities:
$$gcd(a,b) = 1iffmin(alpha,beta)=0,$$
$$gcd(a,b) = 1iffmin(gamma,delta)=0,$$
$$gcd(ac,bd) = gcd(a,d) gcd(b,c)iffmin(alpha+gamma,beta+delta)=min(alpha,delta)+min(beta,gamma).$$
If we consider the case $alpha=gamma=0$,
$$min(0,beta+delta)=min(0,delta)+min(beta,0)$$ does hold.
Then with $beta=gamma=0$,
$$min(alpha,delta)=min(alpha,delta).$$
By symmetry other cases hold.
add a comment |Â
up vote
2
down vote
Let $x = gcd(a,d)$ and $y= gcd(b,c)$, then $xymid ac$ and $xymid bd$ so $boxedxymid z$ where $z=gcd(ac,bd)$.
Vice versa:
We can write $a=xa'$ and $d=xd'$ where $gcd(a',d')=1$ and $b=yb'$ and $c=yc'$ where $gcd(b',c')=1$
Now since $zmid ac = xya'c'$ and $zmid bd = xyb'd'$
Now if there is prime $p$ such that $pmid z$ and $gcd(xy,p)=1$ then $pmid a'c'$ and $pmid b'd'$. If $pmid a'$ then $pmid b'$ since $gcd(a',d')=1$. But then $pmid a$ and $pmid b$ so $pmid gcd(a,b)=1$ a contradiction. So there is no such $p$ and thus $boxedzmid xy$
What is the property you are using in the first line where $xy|ac$ and $xy|bd$ so $xy|z$ ?
â Mario G
30 mins ago
$xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them.
â greedoid
28 mins ago
The greatest common divisor is a multiple of every other common divisor.
â PossiblyDakota
26 mins ago
You did not use the fact that $gcd(a,b) = gcd(c,d) = 1$. As your "counterexample" did not satisfy the assumption.
â Hw Chu
25 mins ago
add a comment |Â
up vote
1
down vote
Let $gcd(a,d) = g$ so that $a = a'g$ and $d = d'g$ and $gcd(a',d') =1$. (why?)
And let $gcd(b,c) = h$ so that $b =b'h$ and $c= c'h$ and $gcd(b',c') =1$ (why?).
Then $gcd(ac,bd) = gcd(a'c'gh, b'd'gh) = gh*gcd(a'c',b'd')$. [$gcd(m*k, n*k) = kgcd(m,n)$. (why?)]
And if you take any prime factor of $a'c'$ then it is a prime factor of $a'$ or $c'$ so it is not a prime factor of either $b'$ or $d'$ (as those both coprime to both $a'$ and $c'$; $a$ and $b$ are coprime, $c$ and $d$ are coprime, and so are $a'$ and $d'$ and so are $b'$ and $c'$). So it is not a prime factor of $b'd'$. Likewise no prime factor of $b'd'$ is a prime factor of $a'c'$. So $gcd(a'c', b'd') = 1$.
So $gcd(ac, bd) = gh = gcd(a,d)gcd(b,c)$.
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Take all prime factors in turn. We have the following relations between the multiplicities:
$$gcd(a,b) = 1iffmin(alpha,beta)=0,$$
$$gcd(a,b) = 1iffmin(gamma,delta)=0,$$
$$gcd(ac,bd) = gcd(a,d) gcd(b,c)iffmin(alpha+gamma,beta+delta)=min(alpha,delta)+min(beta,gamma).$$
If we consider the case $alpha=gamma=0$,
$$min(0,beta+delta)=min(0,delta)+min(beta,0)$$ does hold.
Then with $beta=gamma=0$,
$$min(alpha,delta)=min(alpha,delta).$$
By symmetry other cases hold.
add a comment |Â
up vote
3
down vote
Take all prime factors in turn. We have the following relations between the multiplicities:
$$gcd(a,b) = 1iffmin(alpha,beta)=0,$$
$$gcd(a,b) = 1iffmin(gamma,delta)=0,$$
$$gcd(ac,bd) = gcd(a,d) gcd(b,c)iffmin(alpha+gamma,beta+delta)=min(alpha,delta)+min(beta,gamma).$$
If we consider the case $alpha=gamma=0$,
$$min(0,beta+delta)=min(0,delta)+min(beta,0)$$ does hold.
Then with $beta=gamma=0$,
$$min(alpha,delta)=min(alpha,delta).$$
By symmetry other cases hold.
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Take all prime factors in turn. We have the following relations between the multiplicities:
$$gcd(a,b) = 1iffmin(alpha,beta)=0,$$
$$gcd(a,b) = 1iffmin(gamma,delta)=0,$$
$$gcd(ac,bd) = gcd(a,d) gcd(b,c)iffmin(alpha+gamma,beta+delta)=min(alpha,delta)+min(beta,gamma).$$
If we consider the case $alpha=gamma=0$,
$$min(0,beta+delta)=min(0,delta)+min(beta,0)$$ does hold.
Then with $beta=gamma=0$,
$$min(alpha,delta)=min(alpha,delta).$$
By symmetry other cases hold.
Take all prime factors in turn. We have the following relations between the multiplicities:
$$gcd(a,b) = 1iffmin(alpha,beta)=0,$$
$$gcd(a,b) = 1iffmin(gamma,delta)=0,$$
$$gcd(ac,bd) = gcd(a,d) gcd(b,c)iffmin(alpha+gamma,beta+delta)=min(alpha,delta)+min(beta,gamma).$$
If we consider the case $alpha=gamma=0$,
$$min(0,beta+delta)=min(0,delta)+min(beta,0)$$ does hold.
Then with $beta=gamma=0$,
$$min(alpha,delta)=min(alpha,delta).$$
By symmetry other cases hold.
edited 8 mins ago
answered 26 mins ago
Yves Daoust
115k667210
115k667210
add a comment |Â
add a comment |Â
up vote
2
down vote
Let $x = gcd(a,d)$ and $y= gcd(b,c)$, then $xymid ac$ and $xymid bd$ so $boxedxymid z$ where $z=gcd(ac,bd)$.
Vice versa:
We can write $a=xa'$ and $d=xd'$ where $gcd(a',d')=1$ and $b=yb'$ and $c=yc'$ where $gcd(b',c')=1$
Now since $zmid ac = xya'c'$ and $zmid bd = xyb'd'$
Now if there is prime $p$ such that $pmid z$ and $gcd(xy,p)=1$ then $pmid a'c'$ and $pmid b'd'$. If $pmid a'$ then $pmid b'$ since $gcd(a',d')=1$. But then $pmid a$ and $pmid b$ so $pmid gcd(a,b)=1$ a contradiction. So there is no such $p$ and thus $boxedzmid xy$
What is the property you are using in the first line where $xy|ac$ and $xy|bd$ so $xy|z$ ?
â Mario G
30 mins ago
$xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them.
â greedoid
28 mins ago
The greatest common divisor is a multiple of every other common divisor.
â PossiblyDakota
26 mins ago
You did not use the fact that $gcd(a,b) = gcd(c,d) = 1$. As your "counterexample" did not satisfy the assumption.
â Hw Chu
25 mins ago
add a comment |Â
up vote
2
down vote
Let $x = gcd(a,d)$ and $y= gcd(b,c)$, then $xymid ac$ and $xymid bd$ so $boxedxymid z$ where $z=gcd(ac,bd)$.
Vice versa:
We can write $a=xa'$ and $d=xd'$ where $gcd(a',d')=1$ and $b=yb'$ and $c=yc'$ where $gcd(b',c')=1$
Now since $zmid ac = xya'c'$ and $zmid bd = xyb'd'$
Now if there is prime $p$ such that $pmid z$ and $gcd(xy,p)=1$ then $pmid a'c'$ and $pmid b'd'$. If $pmid a'$ then $pmid b'$ since $gcd(a',d')=1$. But then $pmid a$ and $pmid b$ so $pmid gcd(a,b)=1$ a contradiction. So there is no such $p$ and thus $boxedzmid xy$
What is the property you are using in the first line where $xy|ac$ and $xy|bd$ so $xy|z$ ?
â Mario G
30 mins ago
$xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them.
â greedoid
28 mins ago
The greatest common divisor is a multiple of every other common divisor.
â PossiblyDakota
26 mins ago
You did not use the fact that $gcd(a,b) = gcd(c,d) = 1$. As your "counterexample" did not satisfy the assumption.
â Hw Chu
25 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Let $x = gcd(a,d)$ and $y= gcd(b,c)$, then $xymid ac$ and $xymid bd$ so $boxedxymid z$ where $z=gcd(ac,bd)$.
Vice versa:
We can write $a=xa'$ and $d=xd'$ where $gcd(a',d')=1$ and $b=yb'$ and $c=yc'$ where $gcd(b',c')=1$
Now since $zmid ac = xya'c'$ and $zmid bd = xyb'd'$
Now if there is prime $p$ such that $pmid z$ and $gcd(xy,p)=1$ then $pmid a'c'$ and $pmid b'd'$. If $pmid a'$ then $pmid b'$ since $gcd(a',d')=1$. But then $pmid a$ and $pmid b$ so $pmid gcd(a,b)=1$ a contradiction. So there is no such $p$ and thus $boxedzmid xy$
Let $x = gcd(a,d)$ and $y= gcd(b,c)$, then $xymid ac$ and $xymid bd$ so $boxedxymid z$ where $z=gcd(ac,bd)$.
Vice versa:
We can write $a=xa'$ and $d=xd'$ where $gcd(a',d')=1$ and $b=yb'$ and $c=yc'$ where $gcd(b',c')=1$
Now since $zmid ac = xya'c'$ and $zmid bd = xyb'd'$
Now if there is prime $p$ such that $pmid z$ and $gcd(xy,p)=1$ then $pmid a'c'$ and $pmid b'd'$. If $pmid a'$ then $pmid b'$ since $gcd(a',d')=1$. But then $pmid a$ and $pmid b$ so $pmid gcd(a,b)=1$ a contradiction. So there is no such $p$ and thus $boxedzmid xy$
edited 22 mins ago
answered 32 mins ago
greedoid
29.1k93879
29.1k93879
What is the property you are using in the first line where $xy|ac$ and $xy|bd$ so $xy|z$ ?
â Mario G
30 mins ago
$xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them.
â greedoid
28 mins ago
The greatest common divisor is a multiple of every other common divisor.
â PossiblyDakota
26 mins ago
You did not use the fact that $gcd(a,b) = gcd(c,d) = 1$. As your "counterexample" did not satisfy the assumption.
â Hw Chu
25 mins ago
add a comment |Â
What is the property you are using in the first line where $xy|ac$ and $xy|bd$ so $xy|z$ ?
â Mario G
30 mins ago
$xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them.
â greedoid
28 mins ago
The greatest common divisor is a multiple of every other common divisor.
â PossiblyDakota
26 mins ago
You did not use the fact that $gcd(a,b) = gcd(c,d) = 1$. As your "counterexample" did not satisfy the assumption.
â Hw Chu
25 mins ago
What is the property you are using in the first line where $xy|ac$ and $xy|bd$ so $xy|z$ ?
â Mario G
30 mins ago
What is the property you are using in the first line where $xy|ac$ and $xy|bd$ so $xy|z$ ?
â Mario G
30 mins ago
$xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them.
â greedoid
28 mins ago
$xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them.
â greedoid
28 mins ago
The greatest common divisor is a multiple of every other common divisor.
â PossiblyDakota
26 mins ago
The greatest common divisor is a multiple of every other common divisor.
â PossiblyDakota
26 mins ago
You did not use the fact that $gcd(a,b) = gcd(c,d) = 1$. As your "counterexample" did not satisfy the assumption.
â Hw Chu
25 mins ago
You did not use the fact that $gcd(a,b) = gcd(c,d) = 1$. As your "counterexample" did not satisfy the assumption.
â Hw Chu
25 mins ago
add a comment |Â
up vote
1
down vote
Let $gcd(a,d) = g$ so that $a = a'g$ and $d = d'g$ and $gcd(a',d') =1$. (why?)
And let $gcd(b,c) = h$ so that $b =b'h$ and $c= c'h$ and $gcd(b',c') =1$ (why?).
Then $gcd(ac,bd) = gcd(a'c'gh, b'd'gh) = gh*gcd(a'c',b'd')$. [$gcd(m*k, n*k) = kgcd(m,n)$. (why?)]
And if you take any prime factor of $a'c'$ then it is a prime factor of $a'$ or $c'$ so it is not a prime factor of either $b'$ or $d'$ (as those both coprime to both $a'$ and $c'$; $a$ and $b$ are coprime, $c$ and $d$ are coprime, and so are $a'$ and $d'$ and so are $b'$ and $c'$). So it is not a prime factor of $b'd'$. Likewise no prime factor of $b'd'$ is a prime factor of $a'c'$. So $gcd(a'c', b'd') = 1$.
So $gcd(ac, bd) = gh = gcd(a,d)gcd(b,c)$.
add a comment |Â
up vote
1
down vote
Let $gcd(a,d) = g$ so that $a = a'g$ and $d = d'g$ and $gcd(a',d') =1$. (why?)
And let $gcd(b,c) = h$ so that $b =b'h$ and $c= c'h$ and $gcd(b',c') =1$ (why?).
Then $gcd(ac,bd) = gcd(a'c'gh, b'd'gh) = gh*gcd(a'c',b'd')$. [$gcd(m*k, n*k) = kgcd(m,n)$. (why?)]
And if you take any prime factor of $a'c'$ then it is a prime factor of $a'$ or $c'$ so it is not a prime factor of either $b'$ or $d'$ (as those both coprime to both $a'$ and $c'$; $a$ and $b$ are coprime, $c$ and $d$ are coprime, and so are $a'$ and $d'$ and so are $b'$ and $c'$). So it is not a prime factor of $b'd'$. Likewise no prime factor of $b'd'$ is a prime factor of $a'c'$. So $gcd(a'c', b'd') = 1$.
So $gcd(ac, bd) = gh = gcd(a,d)gcd(b,c)$.
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let $gcd(a,d) = g$ so that $a = a'g$ and $d = d'g$ and $gcd(a',d') =1$. (why?)
And let $gcd(b,c) = h$ so that $b =b'h$ and $c= c'h$ and $gcd(b',c') =1$ (why?).
Then $gcd(ac,bd) = gcd(a'c'gh, b'd'gh) = gh*gcd(a'c',b'd')$. [$gcd(m*k, n*k) = kgcd(m,n)$. (why?)]
And if you take any prime factor of $a'c'$ then it is a prime factor of $a'$ or $c'$ so it is not a prime factor of either $b'$ or $d'$ (as those both coprime to both $a'$ and $c'$; $a$ and $b$ are coprime, $c$ and $d$ are coprime, and so are $a'$ and $d'$ and so are $b'$ and $c'$). So it is not a prime factor of $b'd'$. Likewise no prime factor of $b'd'$ is a prime factor of $a'c'$. So $gcd(a'c', b'd') = 1$.
So $gcd(ac, bd) = gh = gcd(a,d)gcd(b,c)$.
Let $gcd(a,d) = g$ so that $a = a'g$ and $d = d'g$ and $gcd(a',d') =1$. (why?)
And let $gcd(b,c) = h$ so that $b =b'h$ and $c= c'h$ and $gcd(b',c') =1$ (why?).
Then $gcd(ac,bd) = gcd(a'c'gh, b'd'gh) = gh*gcd(a'c',b'd')$. [$gcd(m*k, n*k) = kgcd(m,n)$. (why?)]
And if you take any prime factor of $a'c'$ then it is a prime factor of $a'$ or $c'$ so it is not a prime factor of either $b'$ or $d'$ (as those both coprime to both $a'$ and $c'$; $a$ and $b$ are coprime, $c$ and $d$ are coprime, and so are $a'$ and $d'$ and so are $b'$ and $c'$). So it is not a prime factor of $b'd'$. Likewise no prime factor of $b'd'$ is a prime factor of $a'c'$. So $gcd(a'c', b'd') = 1$.
So $gcd(ac, bd) = gh = gcd(a,d)gcd(b,c)$.
answered 16 mins ago
fleablood
62.1k22678
62.1k22678
add a comment |Â
add a comment |Â
Mario G is a new contributor. Be nice, and check out our Code of Conduct.
Mario G is a new contributor. Be nice, and check out our Code of Conduct.
Mario G is a new contributor. Be nice, and check out our Code of Conduct.
Mario G is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2930687%2fhow-to-show-gcdac-bd-gcda-d-gcdb-c%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Please consider using MathJax to format your question - it will make your formulas much more readable
â Zubin Mukerjee
47 mins ago