Mixing
Greatest common denominator: $xmid a$ and $xmid b$ iff $xmidgcd(a,b)$
$begingroup$
For $a,b$ in the natural numbers. How do I prove that $x$ divides $a$ and $x$ divides $b$ iff $x$ divides $gcd(a,b)$.
Please no proofs using theorems.
elementary-number-theory divisibility greatest-common-divisor
edited Jan 27 at 11:01
Martin Sleziak
44.9k10122276
asked Sep 29 '16 at 8:51
johnjohn
946415
$endgroup$
|
show 2 more comments
$begingroup$
For $a,b$ in the natural numbers. How do I prove that $x$ divides $a$ and $x$ divides $b$ iff $x$ divides $gcd(a,b)$.
Please no proofs using theorems.
elementary-number-theory divisibility greatest-common-divisor
edited Jan 27 at 11:01
Martin Sleziak
44.9k10122276
asked Sep 29 '16 at 8:51
johnjohn
946415
$endgroup$
1
$begingroup$
See Greatest common divisor : "the gcd of two numbers $a$ and $b$ is the largest positive integer that divides the numbers."
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 8:54
$begingroup$
@MauroALLEGRANZA if it is so trivial to you would you mind helping me out?
$endgroup$
– john
Sep 29 '16 at 9:02
$begingroup$
You can see this post : concise-proof-that-every-common-divisor-divides-gcd-without-bezouts-identity
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:02
$begingroup$
The side : if it divides GCD then it divides both is trivial ...
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:03
$begingroup$
That's the definition of gcd of course.
$endgroup$
– Yoshua Yonatan
Sep 29 '16 at 9:10
|
show 2 more comments
$begingroup$
For $a,b$ in the natural numbers. How do I prove that $x$ divides $a$ and $x$ divides $b$ iff $x$ divides $gcd(a,b)$.
Please no proofs using theorems.
elementary-number-theory divisibility greatest-common-divisor
edited Jan 27 at 11:01
Martin Sleziak
44.9k10122276
asked Sep 29 '16 at 8:51
johnjohn
946415
$endgroup$
For $a,b$ in the natural numbers. How do I prove that $x$ divides $a$ and $x$ divides $b$ iff $x$ divides $gcd(a,b)$.
Please no proofs using theorems.
elementary-number-theory divisibility greatest-common-divisor
elementary-number-theory divisibility greatest-common-divisor
edited Jan 27 at 11:01
Martin Sleziak
44.9k10122276
asked Sep 29 '16 at 8:51
johnjohn
946415
edited Jan 27 at 11:01
Martin Sleziak
44.9k10122276
asked Sep 29 '16 at 8:51
johnjohn
946415
edited Jan 27 at 11:01
Martin Sleziak
44.9k10122276
edited Jan 27 at 11:01
Martin Sleziak
44.9k10122276
edited Jan 27 at 11:01
Martin Sleziak
44.9k10122276
44.9k10122276
asked Sep 29 '16 at 8:51
johnjohn
946415
asked Sep 29 '16 at 8:51
johnjohn
946415
asked Sep 29 '16 at 8:51
johnjohn
946415
946415
1
$begingroup$
See Greatest common divisor : "the gcd of two numbers $a$ and $b$ is the largest positive integer that divides the numbers."
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 8:54
$begingroup$
@MauroALLEGRANZA if it is so trivial to you would you mind helping me out?
$endgroup$
– john
Sep 29 '16 at 9:02
$begingroup$
You can see this post : concise-proof-that-every-common-divisor-divides-gcd-without-bezouts-identity
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:02
$begingroup$
The side : if it divides GCD then it divides both is trivial ...
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:03
$begingroup$
That's the definition of gcd of course.
$endgroup$
– Yoshua Yonatan
Sep 29 '16 at 9:10
|
show 2 more comments
1
$begingroup$
See Greatest common divisor : "the gcd of two numbers $a$ and $b$ is the largest positive integer that divides the numbers."
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 8:54
$begingroup$
@MauroALLEGRANZA if it is so trivial to you would you mind helping me out?
$endgroup$
– john
Sep 29 '16 at 9:02
$begingroup$
You can see this post : concise-proof-that-every-common-divisor-divides-gcd-without-bezouts-identity
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:02
$begingroup$
The side : if it divides GCD then it divides both is trivial ...
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:03
$begingroup$
That's the definition of gcd of course.
$endgroup$
– Yoshua Yonatan
Sep 29 '16 at 9:10
1
1
$begingroup$
See Greatest common divisor : "the gcd of two numbers $a$ and $b$ is the largest positive integer that divides the numbers."
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 8:54
$begingroup$
See Greatest common divisor : "the gcd of two numbers $a$ and $b$ is the largest positive integer that divides the numbers."
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 8:54
$begingroup$
@MauroALLEGRANZA if it is so trivial to you would you mind helping me out?
$endgroup$
– john
Sep 29 '16 at 9:02
$begingroup$
@MauroALLEGRANZA if it is so trivial to you would you mind helping me out?
$endgroup$
– john
Sep 29 '16 at 9:02
$begingroup$
You can see this post : concise-proof-that-every-common-divisor-divides-gcd-without-bezouts-identity
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:02
$begingroup$
You can see this post : concise-proof-that-every-common-divisor-divides-gcd-without-bezouts-identity
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:02
$begingroup$
The side : if it divides GCD then it divides both is trivial ...
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:03
$begingroup$
The side : if it divides GCD then it divides both is trivial ...
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:03
$begingroup$
That's the definition of gcd of course.
$endgroup$
– Yoshua Yonatan
Sep 29 '16 at 9:10
$begingroup$
That's the definition of gcd of course.
$endgroup$
– Yoshua Yonatan
Sep 29 '16 at 9:10
|
show 2 more comments
3 Answers
3
active
oldest
votes
$begingroup$
$x|a $. let $a=a'x $. Let $d=gcd (a,b) $. Let $a=Ad=a'x $. By unique factorization we can "break" this up to $a =(A)(d)=(A'x')(d'x")=(A'd')(x'x")=a'x$.
In other words $A'$ is a common factor of $A$ and $a'$, $x'$ is a common factor of $A $ and $x $, etc.
$x|b $. Let $b=b'x $. Let $b=Bd=b'x $.
So $b=B (d'x")=b'(x'x")$. By unique factoization, we can break this to: $b=(B'x')(d'x")=(b"d')(x'x") $.
Notice $d'x'x"=x'd $ is a common factor of $a$ and $b $.
But $d$ is the greatest common divisor. So $dx'le d$ so $x' =1$ and $x"=x $ $A'=1$ and $B'=1$.
So $a=Ad=Ad'x$ and $b=Bd=d'x$ and $d =d'x $ and $x|d=gcd (a,b)$
====
If $x|gcd (a,b) $ and $gcd (a,b)|a $ then $x|a $. As $gcd (a,b)|b $, $x|b $.
answered Sep 29 '16 at 12:04
fleabloodfleablood
73.2k22790
$endgroup$
add a comment |
$begingroup$
You have to translate the word 'divide' into the language of ideals. We say that $a$ divides $b$ if $I_a supset I_b$ (e.g. the set of multiples of $5$ contains the set of multiples of $15$). So for every common divisor $c$ of $a$ and $b$ we have $I_c supset I_a$ and $I_c supset I_b$ so that $I_c supset I_a cup I_b$. The smallest ideal that contains $I_a cup I_b$ is $I_{gcd(a,b)}$. This can be proved by using the property $I_{uv} = I_u cup I_v$ and taking the intersection over all common factors of $a$ and $b$. Viewed like this what you have to prove is $I_x supset I_a, I_x supset I_b iff I_x supset I_{gcd(a,b)}$.
Example $a = 30, b = 20 $: $I_a = {0, 30, 60, 90, ldots}$, $I_b = {0, 20, 40, 60, ldots}$. Then $2$ and $5$ being the common divisors of $a$ and $b$ : $I_{gcd(a,b)} = {0, 2, 4, 6, 8, ldots} cap {0, 5, 10, 15, 20, ldots} = {0, 10, 20, 30, 40, ldots}$. The proposition now sounds like $I_x supset {0, 30, 60, 90, ldots}, I_x supset {0, 20, 40, 60, ldots} iff I_x supset {0, 10, 20, 30, 40, ldots}$.
answered Oct 1 '16 at 20:20
Marc BogaertsMarc Bogaerts
4,14311021
$endgroup$
add a comment |
$begingroup$
Using fundamental theorem of arithmetic
$$displaystyle a = prod_{i=1}^{k}p_i^{alpha_i} ,, , quad b = prod_{i=1}^{k}p_i^{beta_i}$$
We have : $displaystylegcd(a,b)=prod_{i=1}^{k}p_i^{min(alpha_i, beta_i)}$
If $x | a$ and $x | b$ then $x = displaystyle prod_{i=1}^{k}p_i^{gamma_i}$ , with $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq alpha_i text{ and } gamma_i leq beta_i$
Then $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq min(alpha_i, beta_i)$
Then $x$ devide $gcd(a, b)$
And we have $gcd(a,b)$ devide $a$ and $b$, then if $x$ devide $gcd(a,b)$, $x$ will devide $a$ and $b$.
conclusion:
$$d = gcd(a,b) iff left{begin{matrix}d | a , text{ and } , d | b \ x | a , text{et} , x | b implies x | dend{matrix}right.$$
answered Jan 27 at 11:26
LAGRIDALAGRIDA
295111
$endgroup$
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%2f1946246%2fgreatest-common-denominator-x-mid-a-and-x-mid-b-iff-x-mid-gcda-b%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$x|a $. let $a=a'x $. Let $d=gcd (a,b) $. Let $a=Ad=a'x $. By unique factorization we can "break" this up to $a =(A)(d)=(A'x')(d'x")=(A'd')(x'x")=a'x$.
In other words $A'$ is a common factor of $A$ and $a'$, $x'$ is a common factor of $A $ and $x $, etc.
$x|b $. Let $b=b'x $. Let $b=Bd=b'x $.
So $b=B (d'x")=b'(x'x")$. By unique factoization, we can break this to: $b=(B'x')(d'x")=(b"d')(x'x") $.
Notice $d'x'x"=x'd $ is a common factor of $a$ and $b $.
But $d$ is the greatest common divisor. So $dx'le d$ so $x' =1$ and $x"=x $ $A'=1$ and $B'=1$.
So $a=Ad=Ad'x$ and $b=Bd=d'x$ and $d =d'x $ and $x|d=gcd (a,b)$
====
If $x|gcd (a,b) $ and $gcd (a,b)|a $ then $x|a $. As $gcd (a,b)|b $, $x|b $.
answered Sep 29 '16 at 12:04
fleabloodfleablood
73.2k22790
$endgroup$
add a comment |
$begingroup$
$x|a $. let $a=a'x $. Let $d=gcd (a,b) $. Let $a=Ad=a'x $. By unique factorization we can "break" this up to $a =(A)(d)=(A'x')(d'x")=(A'd')(x'x")=a'x$.
In other words $A'$ is a common factor of $A$ and $a'$, $x'$ is a common factor of $A $ and $x $, etc.
$x|b $. Let $b=b'x $. Let $b=Bd=b'x $.
So $b=B (d'x")=b'(x'x")$. By unique factoization, we can break this to: $b=(B'x')(d'x")=(b"d')(x'x") $.
Notice $d'x'x"=x'd $ is a common factor of $a$ and $b $.
But $d$ is the greatest common divisor. So $dx'le d$ so $x' =1$ and $x"=x $ $A'=1$ and $B'=1$.
So $a=Ad=Ad'x$ and $b=Bd=d'x$ and $d =d'x $ and $x|d=gcd (a,b)$
====
If $x|gcd (a,b) $ and $gcd (a,b)|a $ then $x|a $. As $gcd (a,b)|b $, $x|b $.
answered Sep 29 '16 at 12:04
fleabloodfleablood
73.2k22790
$endgroup$
add a comment |
$begingroup$
$x|a $. let $a=a'x $. Let $d=gcd (a,b) $. Let $a=Ad=a'x $. By unique factorization we can "break" this up to $a =(A)(d)=(A'x')(d'x")=(A'd')(x'x")=a'x$.
In other words $A'$ is a common factor of $A$ and $a'$, $x'$ is a common factor of $A $ and $x $, etc.
$x|b $. Let $b=b'x $. Let $b=Bd=b'x $.
So $b=B (d'x")=b'(x'x")$. By unique factoization, we can break this to: $b=(B'x')(d'x")=(b"d')(x'x") $.
Notice $d'x'x"=x'd $ is a common factor of $a$ and $b $.
But $d$ is the greatest common divisor. So $dx'le d$ so $x' =1$ and $x"=x $ $A'=1$ and $B'=1$.
So $a=Ad=Ad'x$ and $b=Bd=d'x$ and $d =d'x $ and $x|d=gcd (a,b)$
====
If $x|gcd (a,b) $ and $gcd (a,b)|a $ then $x|a $. As $gcd (a,b)|b $, $x|b $.
answered Sep 29 '16 at 12:04
fleabloodfleablood
73.2k22790
$endgroup$
$x|a $. let $a=a'x $. Let $d=gcd (a,b) $. Let $a=Ad=a'x $. By unique factorization we can "break" this up to $a =(A)(d)=(A'x')(d'x")=(A'd')(x'x")=a'x$.
In other words $A'$ is a common factor of $A$ and $a'$, $x'$ is a common factor of $A $ and $x $, etc.
$x|b $. Let $b=b'x $. Let $b=Bd=b'x $.
So $b=B (d'x")=b'(x'x")$. By unique factoization, we can break this to: $b=(B'x')(d'x")=(b"d')(x'x") $.
Notice $d'x'x"=x'd $ is a common factor of $a$ and $b $.
But $d$ is the greatest common divisor. So $dx'le d$ so $x' =1$ and $x"=x $ $A'=1$ and $B'=1$.
So $a=Ad=Ad'x$ and $b=Bd=d'x$ and $d =d'x $ and $x|d=gcd (a,b)$
====
If $x|gcd (a,b) $ and $gcd (a,b)|a $ then $x|a $. As $gcd (a,b)|b $, $x|b $.
answered Sep 29 '16 at 12:04
fleabloodfleablood
73.2k22790
answered Sep 29 '16 at 12:04
fleabloodfleablood
73.2k22790
answered Sep 29 '16 at 12:04
fleabloodfleablood
73.2k22790
answered Sep 29 '16 at 12:04
fleabloodfleablood
73.2k22790
73.2k22790
add a comment |
add a comment |
$begingroup$
You have to translate the word 'divide' into the language of ideals. We say that $a$ divides $b$ if $I_a supset I_b$ (e.g. the set of multiples of $5$ contains the set of multiples of $15$). So for every common divisor $c$ of $a$ and $b$ we have $I_c supset I_a$ and $I_c supset I_b$ so that $I_c supset I_a cup I_b$. The smallest ideal that contains $I_a cup I_b$ is $I_{gcd(a,b)}$. This can be proved by using the property $I_{uv} = I_u cup I_v$ and taking the intersection over all common factors of $a$ and $b$. Viewed like this what you have to prove is $I_x supset I_a, I_x supset I_b iff I_x supset I_{gcd(a,b)}$.
Example $a = 30, b = 20 $: $I_a = {0, 30, 60, 90, ldots}$, $I_b = {0, 20, 40, 60, ldots}$. Then $2$ and $5$ being the common divisors of $a$ and $b$ : $I_{gcd(a,b)} = {0, 2, 4, 6, 8, ldots} cap {0, 5, 10, 15, 20, ldots} = {0, 10, 20, 30, 40, ldots}$. The proposition now sounds like $I_x supset {0, 30, 60, 90, ldots}, I_x supset {0, 20, 40, 60, ldots} iff I_x supset {0, 10, 20, 30, 40, ldots}$.
answered Oct 1 '16 at 20:20
Marc BogaertsMarc Bogaerts
4,14311021
$endgroup$
add a comment |
$begingroup$
You have to translate the word 'divide' into the language of ideals. We say that $a$ divides $b$ if $I_a supset I_b$ (e.g. the set of multiples of $5$ contains the set of multiples of $15$). So for every common divisor $c$ of $a$ and $b$ we have $I_c supset I_a$ and $I_c supset I_b$ so that $I_c supset I_a cup I_b$. The smallest ideal that contains $I_a cup I_b$ is $I_{gcd(a,b)}$. This can be proved by using the property $I_{uv} = I_u cup I_v$ and taking the intersection over all common factors of $a$ and $b$. Viewed like this what you have to prove is $I_x supset I_a, I_x supset I_b iff I_x supset I_{gcd(a,b)}$.
Example $a = 30, b = 20 $: $I_a = {0, 30, 60, 90, ldots}$, $I_b = {0, 20, 40, 60, ldots}$. Then $2$ and $5$ being the common divisors of $a$ and $b$ : $I_{gcd(a,b)} = {0, 2, 4, 6, 8, ldots} cap {0, 5, 10, 15, 20, ldots} = {0, 10, 20, 30, 40, ldots}$. The proposition now sounds like $I_x supset {0, 30, 60, 90, ldots}, I_x supset {0, 20, 40, 60, ldots} iff I_x supset {0, 10, 20, 30, 40, ldots}$.
answered Oct 1 '16 at 20:20
Marc BogaertsMarc Bogaerts
4,14311021
$endgroup$
add a comment |
$begingroup$
You have to translate the word 'divide' into the language of ideals. We say that $a$ divides $b$ if $I_a supset I_b$ (e.g. the set of multiples of $5$ contains the set of multiples of $15$). So for every common divisor $c$ of $a$ and $b$ we have $I_c supset I_a$ and $I_c supset I_b$ so that $I_c supset I_a cup I_b$. The smallest ideal that contains $I_a cup I_b$ is $I_{gcd(a,b)}$. This can be proved by using the property $I_{uv} = I_u cup I_v$ and taking the intersection over all common factors of $a$ and $b$. Viewed like this what you have to prove is $I_x supset I_a, I_x supset I_b iff I_x supset I_{gcd(a,b)}$.
Example $a = 30, b = 20 $: $I_a = {0, 30, 60, 90, ldots}$, $I_b = {0, 20, 40, 60, ldots}$. Then $2$ and $5$ being the common divisors of $a$ and $b$ : $I_{gcd(a,b)} = {0, 2, 4, 6, 8, ldots} cap {0, 5, 10, 15, 20, ldots} = {0, 10, 20, 30, 40, ldots}$. The proposition now sounds like $I_x supset {0, 30, 60, 90, ldots}, I_x supset {0, 20, 40, 60, ldots} iff I_x supset {0, 10, 20, 30, 40, ldots}$.
answered Oct 1 '16 at 20:20
Marc BogaertsMarc Bogaerts
4,14311021
$endgroup$
You have to translate the word 'divide' into the language of ideals. We say that $a$ divides $b$ if $I_a supset I_b$ (e.g. the set of multiples of $5$ contains the set of multiples of $15$). So for every common divisor $c$ of $a$ and $b$ we have $I_c supset I_a$ and $I_c supset I_b$ so that $I_c supset I_a cup I_b$. The smallest ideal that contains $I_a cup I_b$ is $I_{gcd(a,b)}$. This can be proved by using the property $I_{uv} = I_u cup I_v$ and taking the intersection over all common factors of $a$ and $b$. Viewed like this what you have to prove is $I_x supset I_a, I_x supset I_b iff I_x supset I_{gcd(a,b)}$.
Example $a = 30, b = 20 $: $I_a = {0, 30, 60, 90, ldots}$, $I_b = {0, 20, 40, 60, ldots}$. Then $2$ and $5$ being the common divisors of $a$ and $b$ : $I_{gcd(a,b)} = {0, 2, 4, 6, 8, ldots} cap {0, 5, 10, 15, 20, ldots} = {0, 10, 20, 30, 40, ldots}$. The proposition now sounds like $I_x supset {0, 30, 60, 90, ldots}, I_x supset {0, 20, 40, 60, ldots} iff I_x supset {0, 10, 20, 30, 40, ldots}$.
answered Oct 1 '16 at 20:20
Marc BogaertsMarc Bogaerts
4,14311021
answered Oct 1 '16 at 20:20
Marc BogaertsMarc Bogaerts
4,14311021
answered Oct 1 '16 at 20:20
Marc BogaertsMarc Bogaerts
4,14311021
answered Oct 1 '16 at 20:20
Marc BogaertsMarc Bogaerts
4,14311021
4,14311021
add a comment |
add a comment |
$begingroup$
Using fundamental theorem of arithmetic
$$displaystyle a = prod_{i=1}^{k}p_i^{alpha_i} ,, , quad b = prod_{i=1}^{k}p_i^{beta_i}$$
We have : $displaystylegcd(a,b)=prod_{i=1}^{k}p_i^{min(alpha_i, beta_i)}$
If $x | a$ and $x | b$ then $x = displaystyle prod_{i=1}^{k}p_i^{gamma_i}$ , with $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq alpha_i text{ and } gamma_i leq beta_i$
Then $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq min(alpha_i, beta_i)$
Then $x$ devide $gcd(a, b)$
And we have $gcd(a,b)$ devide $a$ and $b$, then if $x$ devide $gcd(a,b)$, $x$ will devide $a$ and $b$.
conclusion:
$$d = gcd(a,b) iff left{begin{matrix}d | a , text{ and } , d | b \ x | a , text{et} , x | b implies x | dend{matrix}right.$$
answered Jan 27 at 11:26
LAGRIDALAGRIDA
295111
$endgroup$
add a comment |
$begingroup$
Using fundamental theorem of arithmetic
$$displaystyle a = prod_{i=1}^{k}p_i^{alpha_i} ,, , quad b = prod_{i=1}^{k}p_i^{beta_i}$$
We have : $displaystylegcd(a,b)=prod_{i=1}^{k}p_i^{min(alpha_i, beta_i)}$
If $x | a$ and $x | b$ then $x = displaystyle prod_{i=1}^{k}p_i^{gamma_i}$ , with $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq alpha_i text{ and } gamma_i leq beta_i$
Then $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq min(alpha_i, beta_i)$
Then $x$ devide $gcd(a, b)$
And we have $gcd(a,b)$ devide $a$ and $b$, then if $x$ devide $gcd(a,b)$, $x$ will devide $a$ and $b$.
conclusion:
$$d = gcd(a,b) iff left{begin{matrix}d | a , text{ and } , d | b \ x | a , text{et} , x | b implies x | dend{matrix}right.$$
answered Jan 27 at 11:26
LAGRIDALAGRIDA
295111
$endgroup$
add a comment |
$begingroup$
Using fundamental theorem of arithmetic
$$displaystyle a = prod_{i=1}^{k}p_i^{alpha_i} ,, , quad b = prod_{i=1}^{k}p_i^{beta_i}$$
We have : $displaystylegcd(a,b)=prod_{i=1}^{k}p_i^{min(alpha_i, beta_i)}$
If $x | a$ and $x | b$ then $x = displaystyle prod_{i=1}^{k}p_i^{gamma_i}$ , with $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq alpha_i text{ and } gamma_i leq beta_i$
Then $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq min(alpha_i, beta_i)$
Then $x$ devide $gcd(a, b)$
And we have $gcd(a,b)$ devide $a$ and $b$, then if $x$ devide $gcd(a,b)$, $x$ will devide $a$ and $b$.
conclusion:
$$d = gcd(a,b) iff left{begin{matrix}d | a , text{ and } , d | b \ x | a , text{et} , x | b implies x | dend{matrix}right.$$
answered Jan 27 at 11:26
LAGRIDALAGRIDA
295111
$endgroup$
Using fundamental theorem of arithmetic
$$displaystyle a = prod_{i=1}^{k}p_i^{alpha_i} ,, , quad b = prod_{i=1}^{k}p_i^{beta_i}$$
We have : $displaystylegcd(a,b)=prod_{i=1}^{k}p_i^{min(alpha_i, beta_i)}$
If $x | a$ and $x | b$ then $x = displaystyle prod_{i=1}^{k}p_i^{gamma_i}$ , with $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq alpha_i text{ and } gamma_i leq beta_i$
Then $forall i in {1,2,cdots,k} ,, : ,, gamma_i leq min(alpha_i, beta_i)$
Then $x$ devide $gcd(a, b)$
And we have $gcd(a,b)$ devide $a$ and $b$, then if $x$ devide $gcd(a,b)$, $x$ will devide $a$ and $b$.
conclusion:
$$d = gcd(a,b) iff left{begin{matrix}d | a , text{ and } , d | b \ x | a , text{et} , x | b implies x | dend{matrix}right.$$
answered Jan 27 at 11:26
LAGRIDALAGRIDA
295111
edited Jan 27 at 11:32
answered Jan 27 at 11:26
LAGRIDALAGRIDA
295111
answered Jan 27 at 11:26
LAGRIDALAGRIDA
295111
answered Jan 27 at 11:26
LAGRIDALAGRIDA
295111
295111
add a comment |
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%2f1946246%2fgreatest-common-denominator-x-mid-a-and-x-mid-b-iff-x-mid-gcda-b%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
1
$begingroup$
See Greatest common divisor : "the gcd of two numbers $a$ and $b$ is the largest positive integer that divides the numbers."
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 8:54
$begingroup$
@MauroALLEGRANZA if it is so trivial to you would you mind helping me out?
$endgroup$
– john
Sep 29 '16 at 9:02
$begingroup$
You can see this post : concise-proof-that-every-common-divisor-divides-gcd-without-bezouts-identity
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:02
$begingroup$
The side : if it divides GCD then it divides both is trivial ...
$endgroup$
– Mauro ALLEGRANZA
Sep 29 '16 at 9:03
$begingroup$
That's the definition of gcd of course.
$endgroup$
– Yoshua Yonatan
Sep 29 '16 at 9:10