Mixing
If $n,m in mathbb{N}$ then there are $c,d$ such that $cd = (m,n)$, $(c,d) = 1$ and $(m/c,n/d) = 1$.
$begingroup$
Suppose that $m,n in mathbb{N}$. Using the fundamental theorem of arithmetic it is easy to show that there exist $c,d in mathbb{N}$ such that $(c,d) = 1$, $cd = (m,n)$ and $(frac{m}{c},frac{n}{d}) = 1$.
Is there any quick way to prove this without using the prime factorizations of $m$ and $n$, i.e. only the basic properties of the gcd, lcm, etc.?
elementary-number-theory greatest-common-divisor
asked Jan 22 at 13:24
Andrei KhAndrei Kh
1,135818
$endgroup$
add a comment |
$begingroup$
Suppose that $m,n in mathbb{N}$. Using the fundamental theorem of arithmetic it is easy to show that there exist $c,d in mathbb{N}$ such that $(c,d) = 1$, $cd = (m,n)$ and $(frac{m}{c},frac{n}{d}) = 1$.
Is there any quick way to prove this without using the prime factorizations of $m$ and $n$, i.e. only the basic properties of the gcd, lcm, etc.?
elementary-number-theory greatest-common-divisor
asked Jan 22 at 13:24
Andrei KhAndrei Kh
1,135818
$endgroup$
add a comment |
$begingroup$
Suppose that $m,n in mathbb{N}$. Using the fundamental theorem of arithmetic it is easy to show that there exist $c,d in mathbb{N}$ such that $(c,d) = 1$, $cd = (m,n)$ and $(frac{m}{c},frac{n}{d}) = 1$.
Is there any quick way to prove this without using the prime factorizations of $m$ and $n$, i.e. only the basic properties of the gcd, lcm, etc.?
elementary-number-theory greatest-common-divisor
asked Jan 22 at 13:24
Andrei KhAndrei Kh
1,135818
$endgroup$
Suppose that $m,n in mathbb{N}$. Using the fundamental theorem of arithmetic it is easy to show that there exist $c,d in mathbb{N}$ such that $(c,d) = 1$, $cd = (m,n)$ and $(frac{m}{c},frac{n}{d}) = 1$.
Is there any quick way to prove this without using the prime factorizations of $m$ and $n$, i.e. only the basic properties of the gcd, lcm, etc.?
elementary-number-theory greatest-common-divisor
elementary-number-theory greatest-common-divisor
asked Jan 22 at 13:24
Andrei KhAndrei Kh
1,135818
asked Jan 22 at 13:24
Andrei KhAndrei Kh
1,135818
asked Jan 22 at 13:24
Andrei KhAndrei Kh
1,135818
asked Jan 22 at 13:24
Andrei KhAndrei Kh
1,135818
asked Jan 22 at 13:24
Andrei KhAndrei Kh
1,135818
1,135818
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
$c$ consists of all the prime powers in $(m,n)$ that have the same exponent as in $m$ ...
Yes, expensive factorization is not needed. We can compute $,c,$ efficiently by iterated gcds that cancel from $,m,$ all primes that occur to higher power than in $,(m,n).,$ These are exactly the primes in $,m' = m/(m,n),$ and we can cancel them from $m$ by repeatedly cancelling any gcd it has with $,m',,$ yielding the solution $ c = {rm gdc}(m, m'), d = (m,n)/c, $ where
$begin{align}&{rm gdc}(x,y) :=qquad text{// greatest divisisor of $,x,$ that is coprime to $,y$}\
&quad {rm if} , gcd(x,y) = 1 {rm then} x\
&quad {rm else} , {rm gdc}(x/{rm gcd}(x,y),,y)
end{align}$
answered Jan 23 at 22:39
Bill DubuqueBill Dubuque
212k29195650
$endgroup$
add a comment |
$begingroup$
Let $d=(m,n)$ and $c=1$, so the statement is proved trivially
answered Jan 22 at 13:37
ecrinecrin
3477
$endgroup$
$begingroup$
$m=12$, $n=18$, $c=1$, $d=6$ is a counterexample to your approach (giving $frac{m}{c}=12$ and $frac{n}{d}=3$).
$endgroup$
– paw88789
Jan 22 at 13:40
$begingroup$
$c$ consist of all the prime powers in $(m,n)$ that have the same exponent as in $m$ and $d$ consists of all prime powers in $(m,n)$ that have the same exponent as in $n$. Ties are solved arbitrary, so the numbers $c,d$ are in general not unique.
$endgroup$
– Andrei Kh
Jan 22 at 13:59
$begingroup$
It's true, i had a mistake
$endgroup$
– ecrin
Jan 22 at 17:45
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3083157%2fif-n-m-in-mathbbn-then-there-are-c-d-such-that-cd-m-n-c-d-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$c$ consists of all the prime powers in $(m,n)$ that have the same exponent as in $m$ ...
Yes, expensive factorization is not needed. We can compute $,c,$ efficiently by iterated gcds that cancel from $,m,$ all primes that occur to higher power than in $,(m,n).,$ These are exactly the primes in $,m' = m/(m,n),$ and we can cancel them from $m$ by repeatedly cancelling any gcd it has with $,m',,$ yielding the solution $ c = {rm gdc}(m, m'), d = (m,n)/c, $ where
$begin{align}&{rm gdc}(x,y) :=qquad text{// greatest divisisor of $,x,$ that is coprime to $,y$}\
&quad {rm if} , gcd(x,y) = 1 {rm then} x\
&quad {rm else} , {rm gdc}(x/{rm gcd}(x,y),,y)
end{align}$
answered Jan 23 at 22:39
Bill DubuqueBill Dubuque
212k29195650
$endgroup$
add a comment |
$begingroup$
$c$ consists of all the prime powers in $(m,n)$ that have the same exponent as in $m$ ...
Yes, expensive factorization is not needed. We can compute $,c,$ efficiently by iterated gcds that cancel from $,m,$ all primes that occur to higher power than in $,(m,n).,$ These are exactly the primes in $,m' = m/(m,n),$ and we can cancel them from $m$ by repeatedly cancelling any gcd it has with $,m',,$ yielding the solution $ c = {rm gdc}(m, m'), d = (m,n)/c, $ where
$begin{align}&{rm gdc}(x,y) :=qquad text{// greatest divisisor of $,x,$ that is coprime to $,y$}\
&quad {rm if} , gcd(x,y) = 1 {rm then} x\
&quad {rm else} , {rm gdc}(x/{rm gcd}(x,y),,y)
end{align}$
answered Jan 23 at 22:39
Bill DubuqueBill Dubuque
212k29195650
$endgroup$
add a comment |
$begingroup$
$c$ consists of all the prime powers in $(m,n)$ that have the same exponent as in $m$ ...
Yes, expensive factorization is not needed. We can compute $,c,$ efficiently by iterated gcds that cancel from $,m,$ all primes that occur to higher power than in $,(m,n).,$ These are exactly the primes in $,m' = m/(m,n),$ and we can cancel them from $m$ by repeatedly cancelling any gcd it has with $,m',,$ yielding the solution $ c = {rm gdc}(m, m'), d = (m,n)/c, $ where
$begin{align}&{rm gdc}(x,y) :=qquad text{// greatest divisisor of $,x,$ that is coprime to $,y$}\
&quad {rm if} , gcd(x,y) = 1 {rm then} x\
&quad {rm else} , {rm gdc}(x/{rm gcd}(x,y),,y)
end{align}$
answered Jan 23 at 22:39
Bill DubuqueBill Dubuque
212k29195650
$endgroup$
$c$ consists of all the prime powers in $(m,n)$ that have the same exponent as in $m$ ...
Yes, expensive factorization is not needed. We can compute $,c,$ efficiently by iterated gcds that cancel from $,m,$ all primes that occur to higher power than in $,(m,n).,$ These are exactly the primes in $,m' = m/(m,n),$ and we can cancel them from $m$ by repeatedly cancelling any gcd it has with $,m',,$ yielding the solution $ c = {rm gdc}(m, m'), d = (m,n)/c, $ where
$begin{align}&{rm gdc}(x,y) :=qquad text{// greatest divisisor of $,x,$ that is coprime to $,y$}\
&quad {rm if} , gcd(x,y) = 1 {rm then} x\
&quad {rm else} , {rm gdc}(x/{rm gcd}(x,y),,y)
end{align}$
answered Jan 23 at 22:39
Bill DubuqueBill Dubuque
212k29195650
answered Jan 23 at 22:39
Bill DubuqueBill Dubuque
212k29195650
answered Jan 23 at 22:39
Bill DubuqueBill Dubuque
212k29195650
answered Jan 23 at 22:39
Bill DubuqueBill Dubuque
212k29195650
212k29195650
add a comment |
add a comment |
$begingroup$
Let $d=(m,n)$ and $c=1$, so the statement is proved trivially
answered Jan 22 at 13:37
ecrinecrin
3477
$endgroup$
$begingroup$
$m=12$, $n=18$, $c=1$, $d=6$ is a counterexample to your approach (giving $frac{m}{c}=12$ and $frac{n}{d}=3$).
$endgroup$
– paw88789
Jan 22 at 13:40
$begingroup$
$c$ consist of all the prime powers in $(m,n)$ that have the same exponent as in $m$ and $d$ consists of all prime powers in $(m,n)$ that have the same exponent as in $n$. Ties are solved arbitrary, so the numbers $c,d$ are in general not unique.
$endgroup$
– Andrei Kh
Jan 22 at 13:59
$begingroup$
It's true, i had a mistake
$endgroup$
– ecrin
Jan 22 at 17:45
add a comment |
$begingroup$
Let $d=(m,n)$ and $c=1$, so the statement is proved trivially
answered Jan 22 at 13:37
ecrinecrin
3477
$endgroup$
$begingroup$
$m=12$, $n=18$, $c=1$, $d=6$ is a counterexample to your approach (giving $frac{m}{c}=12$ and $frac{n}{d}=3$).
$endgroup$
– paw88789
Jan 22 at 13:40
$begingroup$
$c$ consist of all the prime powers in $(m,n)$ that have the same exponent as in $m$ and $d$ consists of all prime powers in $(m,n)$ that have the same exponent as in $n$. Ties are solved arbitrary, so the numbers $c,d$ are in general not unique.
$endgroup$
– Andrei Kh
Jan 22 at 13:59
$begingroup$
It's true, i had a mistake
$endgroup$
– ecrin
Jan 22 at 17:45
add a comment |
$begingroup$
Let $d=(m,n)$ and $c=1$, so the statement is proved trivially
answered Jan 22 at 13:37
ecrinecrin
3477
$endgroup$
Let $d=(m,n)$ and $c=1$, so the statement is proved trivially
answered Jan 22 at 13:37
ecrinecrin
3477
answered Jan 22 at 13:37
ecrinecrin
3477
answered Jan 22 at 13:37
ecrinecrin
3477
answered Jan 22 at 13:37
ecrinecrin
3477
3477
$begingroup$
$m=12$, $n=18$, $c=1$, $d=6$ is a counterexample to your approach (giving $frac{m}{c}=12$ and $frac{n}{d}=3$).
$endgroup$
– paw88789
Jan 22 at 13:40
$begingroup$
$c$ consist of all the prime powers in $(m,n)$ that have the same exponent as in $m$ and $d$ consists of all prime powers in $(m,n)$ that have the same exponent as in $n$. Ties are solved arbitrary, so the numbers $c,d$ are in general not unique.
$endgroup$
– Andrei Kh
Jan 22 at 13:59
$begingroup$
It's true, i had a mistake
$endgroup$
– ecrin
Jan 22 at 17:45
add a comment |
$begingroup$
$m=12$, $n=18$, $c=1$, $d=6$ is a counterexample to your approach (giving $frac{m}{c}=12$ and $frac{n}{d}=3$).
$endgroup$
– paw88789
Jan 22 at 13:40
$begingroup$
$c$ consist of all the prime powers in $(m,n)$ that have the same exponent as in $m$ and $d$ consists of all prime powers in $(m,n)$ that have the same exponent as in $n$. Ties are solved arbitrary, so the numbers $c,d$ are in general not unique.
$endgroup$
– Andrei Kh
Jan 22 at 13:59
$begingroup$
It's true, i had a mistake
$endgroup$
– ecrin
Jan 22 at 17:45
$begingroup$
$m=12$, $n=18$, $c=1$, $d=6$ is a counterexample to your approach (giving $frac{m}{c}=12$ and $frac{n}{d}=3$).
$endgroup$
– paw88789
Jan 22 at 13:40
$begingroup$
$m=12$, $n=18$, $c=1$, $d=6$ is a counterexample to your approach (giving $frac{m}{c}=12$ and $frac{n}{d}=3$).
$endgroup$
– paw88789
Jan 22 at 13:40
$begingroup$
$c$ consist of all the prime powers in $(m,n)$ that have the same exponent as in $m$ and $d$ consists of all prime powers in $(m,n)$ that have the same exponent as in $n$. Ties are solved arbitrary, so the numbers $c,d$ are in general not unique.
$endgroup$
– Andrei Kh
Jan 22 at 13:59
$begingroup$
$c$ consist of all the prime powers in $(m,n)$ that have the same exponent as in $m$ and $d$ consists of all prime powers in $(m,n)$ that have the same exponent as in $n$. Ties are solved arbitrary, so the numbers $c,d$ are in general not unique.
$endgroup$
– Andrei Kh
Jan 22 at 13:59
$begingroup$
It's true, i had a mistake
$endgroup$
– ecrin
Jan 22 at 17:45
$begingroup$
It's true, i had a mistake
$endgroup$
– ecrin
Jan 22 at 17:45
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3083157%2fif-n-m-in-mathbbn-then-there-are-c-d-such-that-cd-m-n-c-d-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
