Mixing
If gcd(a,b) = 1, can any integer be written as a linear combination of a,b?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am thinking about this in the context of the two water jugs problem. I know that a jug of capacity n can be filled if gcd(a,b) | n. Does this have the corollary that any integer can be written as a linear combination of a and b if gcd(a,b) = 1.
combinatorics number-theory elementary-number-theory puzzle
asked 35 mins ago
taurus
82
New contributor
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
I am thinking about this in the context of the two water jugs problem. I know that a jug of capacity n can be filled if gcd(a,b) | n. Does this have the corollary that any integer can be written as a linear combination of a and b if gcd(a,b) = 1.
combinatorics number-theory elementary-number-theory puzzle
asked 35 mins ago
taurus
82
New contributor
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Yes, that is right
– DonAntonio
34 mins ago
If $gcd(a,b) = 1$ then there are $c,d $ such that $ac+bd = 1$ and hence if $p$ is an integer we can write $p = (cp)a + (dp)b$.
– copper.hat
32 mins ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am thinking about this in the context of the two water jugs problem. I know that a jug of capacity n can be filled if gcd(a,b) | n. Does this have the corollary that any integer can be written as a linear combination of a and b if gcd(a,b) = 1.
combinatorics number-theory elementary-number-theory puzzle
asked 35 mins ago
taurus
82
New contributor
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I am thinking about this in the context of the two water jugs problem. I know that a jug of capacity n can be filled if gcd(a,b) | n. Does this have the corollary that any integer can be written as a linear combination of a and b if gcd(a,b) = 1.
combinatorics number-theory elementary-number-theory puzzle
combinatorics number-theory elementary-number-theory puzzle
asked 35 mins ago
taurus
82
New contributor
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 35 mins ago
taurus
82
New contributor
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 35 mins ago
taurus
82
New contributor
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 35 mins ago
taurus
82
asked 35 mins ago
taurus
82
82
New contributor
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
taurus is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Yes, that is right
– DonAntonio
34 mins ago
If $gcd(a,b) = 1$ then there are $c,d $ such that $ac+bd = 1$ and hence if $p$ is an integer we can write $p = (cp)a + (dp)b$.
– copper.hat
32 mins ago
add a comment |Â
Yes, that is right
– DonAntonio
34 mins ago
If $gcd(a,b) = 1$ then there are $c,d $ such that $ac+bd = 1$ and hence if $p$ is an integer we can write $p = (cp)a + (dp)b$.
– copper.hat
32 mins ago
Yes, that is right
– DonAntonio
34 mins ago
Yes, that is right
– DonAntonio
34 mins ago
If $gcd(a,b) = 1$ then there are $c,d $ such that $ac+bd = 1$ and hence if $p$ is an integer we can write $p = (cp)a + (dp)b$.
– copper.hat
32 mins ago
If $gcd(a,b) = 1$ then there are $c,d $ such that $ac+bd = 1$ and hence if $p$ is an integer we can write $p = (cp)a + (dp)b$.
– copper.hat
32 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
4
down vote
accepted
Yes that's a consequence of Bézout's identity which can be proved by Euclidean algorithm and which states that
$$forall a,bin mathbbZquad gcd(a,b)=1 iff exists x,yin mathbbZquad ax+by=1$$
from which we obtain that
$$acdot nx+bcdot ny=n$$
answered 32 mins ago
gimusi
78.1k73889
@copper.hat Thanks for the editing, the fact is that I've also encountered that as "Bezout's theorem" but "Bezout's identity" seems to be the official name.
– gimusi
28 mins ago
Bézout's theorem is usually interpreted in the context of algebraic geometry,
– copper.hat
27 mins ago
@copper.hat Indeed I'm completely unaware about algebraic geometry :)
– gimusi
25 mins ago
Thank you very much!
– taurus
23 mins ago
add a comment |Â
up vote
0
down vote
In general, if $d=gcd(a,b)$, then any integer of the form $nd$ for some integer $n$ can be expressed as a linear combination of $a$ and $b$. This is because we can write $a=da_1$ and $b=db_1$ for integers $a_1,b_1$ so that $gcd(a_1,b_1)=1$. By the euclidean algorithm this leads us to the fact that there exists $k_1,k_2$ such that
$$1=k_1a_1+k_2b_1$$
for all $a_1,b_1$. Multiplying both sides of the equation by $nd$, we get
$$nd=nk_1(da_1)+nk_2(db_1)=nk_1a+nk_2b$$
Which gives us a way to find anything of the form $nd$ as a linear combination of $a,b$.
answered 19 mins ago
user496634
8661110
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
Yes that's a consequence of Bézout's identity which can be proved by Euclidean algorithm and which states that
$$forall a,bin mathbbZquad gcd(a,b)=1 iff exists x,yin mathbbZquad ax+by=1$$
from which we obtain that
$$acdot nx+bcdot ny=n$$
answered 32 mins ago
gimusi
78.1k73889
@copper.hat Thanks for the editing, the fact is that I've also encountered that as "Bezout's theorem" but "Bezout's identity" seems to be the official name.
– gimusi
28 mins ago
Bézout's theorem is usually interpreted in the context of algebraic geometry,
– copper.hat
27 mins ago
@copper.hat Indeed I'm completely unaware about algebraic geometry :)
– gimusi
25 mins ago
Thank you very much!
– taurus
23 mins ago
add a comment |Â
up vote
4
down vote
accepted
Yes that's a consequence of Bézout's identity which can be proved by Euclidean algorithm and which states that
$$forall a,bin mathbbZquad gcd(a,b)=1 iff exists x,yin mathbbZquad ax+by=1$$
from which we obtain that
$$acdot nx+bcdot ny=n$$
answered 32 mins ago
gimusi
78.1k73889
@copper.hat Thanks for the editing, the fact is that I've also encountered that as "Bezout's theorem" but "Bezout's identity" seems to be the official name.
– gimusi
28 mins ago
Bézout's theorem is usually interpreted in the context of algebraic geometry,
– copper.hat
27 mins ago
@copper.hat Indeed I'm completely unaware about algebraic geometry :)
– gimusi
25 mins ago
Thank you very much!
– taurus
23 mins ago
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
Yes that's a consequence of Bézout's identity which can be proved by Euclidean algorithm and which states that
$$forall a,bin mathbbZquad gcd(a,b)=1 iff exists x,yin mathbbZquad ax+by=1$$
from which we obtain that
$$acdot nx+bcdot ny=n$$
answered 32 mins ago
gimusi
78.1k73889
Yes that's a consequence of Bézout's identity which can be proved by Euclidean algorithm and which states that
$$forall a,bin mathbbZquad gcd(a,b)=1 iff exists x,yin mathbbZquad ax+by=1$$
from which we obtain that
$$acdot nx+bcdot ny=n$$
answered 32 mins ago
gimusi
78.1k73889
edited 30 mins ago
answered 32 mins ago
gimusi
78.1k73889
answered 32 mins ago
gimusi
78.1k73889
answered 32 mins ago
gimusi
78.1k73889
78.1k73889
@copper.hat Thanks for the editing, the fact is that I've also encountered that as "Bezout's theorem" but "Bezout's identity" seems to be the official name.
– gimusi
28 mins ago
Bézout's theorem is usually interpreted in the context of algebraic geometry,
– copper.hat
27 mins ago
@copper.hat Indeed I'm completely unaware about algebraic geometry :)
– gimusi
25 mins ago
Thank you very much!
– taurus
23 mins ago
add a comment |Â
@copper.hat Thanks for the editing, the fact is that I've also encountered that as "Bezout's theorem" but "Bezout's identity" seems to be the official name.
– gimusi
28 mins ago
Bézout's theorem is usually interpreted in the context of algebraic geometry,
– copper.hat
27 mins ago
@copper.hat Indeed I'm completely unaware about algebraic geometry :)
– gimusi
25 mins ago
Thank you very much!
– taurus
23 mins ago
@copper.hat Thanks for the editing, the fact is that I've also encountered that as "Bezout's theorem" but "Bezout's identity" seems to be the official name.
– gimusi
28 mins ago
@copper.hat Thanks for the editing, the fact is that I've also encountered that as "Bezout's theorem" but "Bezout's identity" seems to be the official name.
– gimusi
28 mins ago
Bézout's theorem is usually interpreted in the context of algebraic geometry,
– copper.hat
27 mins ago
Bézout's theorem is usually interpreted in the context of algebraic geometry,
– copper.hat
27 mins ago
@copper.hat Indeed I'm completely unaware about algebraic geometry :)
– gimusi
25 mins ago
@copper.hat Indeed I'm completely unaware about algebraic geometry :)
– gimusi
25 mins ago
Thank you very much!
– taurus
23 mins ago
Thank you very much!
– taurus
23 mins ago
add a comment |Â
up vote
0
down vote
In general, if $d=gcd(a,b)$, then any integer of the form $nd$ for some integer $n$ can be expressed as a linear combination of $a$ and $b$. This is because we can write $a=da_1$ and $b=db_1$ for integers $a_1,b_1$ so that $gcd(a_1,b_1)=1$. By the euclidean algorithm this leads us to the fact that there exists $k_1,k_2$ such that
$$1=k_1a_1+k_2b_1$$
for all $a_1,b_1$. Multiplying both sides of the equation by $nd$, we get
$$nd=nk_1(da_1)+nk_2(db_1)=nk_1a+nk_2b$$
Which gives us a way to find anything of the form $nd$ as a linear combination of $a,b$.
answered 19 mins ago
user496634
8661110
add a comment |Â
up vote
0
down vote
In general, if $d=gcd(a,b)$, then any integer of the form $nd$ for some integer $n$ can be expressed as a linear combination of $a$ and $b$. This is because we can write $a=da_1$ and $b=db_1$ for integers $a_1,b_1$ so that $gcd(a_1,b_1)=1$. By the euclidean algorithm this leads us to the fact that there exists $k_1,k_2$ such that
$$1=k_1a_1+k_2b_1$$
for all $a_1,b_1$. Multiplying both sides of the equation by $nd$, we get
$$nd=nk_1(da_1)+nk_2(db_1)=nk_1a+nk_2b$$
Which gives us a way to find anything of the form $nd$ as a linear combination of $a,b$.
answered 19 mins ago
user496634
8661110
add a comment |Â
up vote
0
down vote
up vote
0
down vote
In general, if $d=gcd(a,b)$, then any integer of the form $nd$ for some integer $n$ can be expressed as a linear combination of $a$ and $b$. This is because we can write $a=da_1$ and $b=db_1$ for integers $a_1,b_1$ so that $gcd(a_1,b_1)=1$. By the euclidean algorithm this leads us to the fact that there exists $k_1,k_2$ such that
$$1=k_1a_1+k_2b_1$$
for all $a_1,b_1$. Multiplying both sides of the equation by $nd$, we get
$$nd=nk_1(da_1)+nk_2(db_1)=nk_1a+nk_2b$$
Which gives us a way to find anything of the form $nd$ as a linear combination of $a,b$.
answered 19 mins ago
user496634
8661110
In general, if $d=gcd(a,b)$, then any integer of the form $nd$ for some integer $n$ can be expressed as a linear combination of $a$ and $b$. This is because we can write $a=da_1$ and $b=db_1$ for integers $a_1,b_1$ so that $gcd(a_1,b_1)=1$. By the euclidean algorithm this leads us to the fact that there exists $k_1,k_2$ such that
$$1=k_1a_1+k_2b_1$$
for all $a_1,b_1$. Multiplying both sides of the equation by $nd$, we get
$$nd=nk_1(da_1)+nk_2(db_1)=nk_1a+nk_2b$$
Which gives us a way to find anything of the form $nd$ as a linear combination of $a,b$.
answered 19 mins ago
user496634
8661110
answered 19 mins ago
user496634
8661110
answered 19 mins ago
user496634
8661110
answered 19 mins ago
user496634
8661110
8661110
add a comment |Â
add a comment |Â
taurus is a new contributor. Be nice, and check out our Code of Conduct.
taurus is a new contributor. Be nice, and check out our Code of Conduct.
taurus is a new contributor. Be nice, and check out our Code of Conduct.
taurus 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%2f2965188%2fif-gcda-b-1-can-any-integer-be-written-as-a-linear-combination-of-a-b%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
Yes, that is right
– DonAntonio
34 mins ago
If $gcd(a,b) = 1$ then there are $c,d $ such that $ac+bd = 1$ and hence if $p$ is an integer we can write $p = (cp)a + (dp)b$.
– copper.hat
32 mins ago