Extended Euclid Theorem - Can there be more than one pair of x and y for two numbers A and B [closed]
-5
GCD(A,B) is Ax + By. So can there be more than one pair of x and y. If yes, how can I find all?
c++ math number-theory
asked Nov 13 '18 at 13:08
Vikas RatheeVikas Rathee
617
closed as off-topic by Toby Speight, Rory Daulton, Jon Clements♦ Nov 13 '18 at 14:17
- This question does not appear to be about programming within the scope defined in the help center.
|
show 3 more comments
-5
GCD(A,B) is Ax + By. So can there be more than one pair of x and y. If yes, how can I find all?
c++ math number-theory
asked Nov 13 '18 at 13:08
Vikas RatheeVikas Rathee
617
closed as off-topic by Toby Speight, Rory Daulton, Jon Clements♦ Nov 13 '18 at 14:17
- This question does not appear to be about programming within the scope defined in the help center.
5
this question is about maths and has nothing to do with c++ or programming in general
– user463035818
Nov 13 '18 at 13:12
1
@user463035818: “How can I find…” with the C++ tag is a request for expressing an algorithm in C++ code. If the OP is interested in implementing the algorithm in C++, it is not an unrelated tag.
– Eric Postpischil
Nov 13 '18 at 13:31
1
@user463035818: The question does not ask for a book, tool, library, tutorial, or other off-site resource. It does ask for information. You could answer that with code, or you could answer it with information about what algorithm would solve the problem and how it could be implemented in C++.
– Eric Postpischil
Nov 13 '18 at 13:40
4
I'm voting to close this question as off-topic because it is not about programming but rather belongs on Mathematics Stack Exchange once the questioner has added more of his own work and explained just where he is stuck.
– Rory Daulton
Nov 13 '18 at 14:13
2
@Damien: If the OP modifies the question, it gets bumped to the top of the review queue and more people will look at it. People with enough reputation can vote to reopen the question. Five votes will reopen the question, then more answers may be given. For me to vote to reopen, the OP will need to show how this is a practical programming problem. That will be difficult, since I know the answer to the question and the difficulty is all mathematical--the programming is trivial.
– Rory Daulton
Nov 13 '18 at 14:34
|
show 3 more comments
-5
-5
-5
GCD(A,B) is Ax + By. So can there be more than one pair of x and y. If yes, how can I find all?
c++ math number-theory
asked Nov 13 '18 at 13:08
Vikas RatheeVikas Rathee
617
GCD(A,B) is Ax + By. So can there be more than one pair of x and y. If yes, how can I find all?
c++ math number-theory
c++ math number-theory
asked Nov 13 '18 at 13:08
Vikas RatheeVikas Rathee
617
asked Nov 13 '18 at 13:08
Vikas RatheeVikas Rathee
617
edited Nov 13 '18 at 13:32
Vikas Rathee
asked Nov 13 '18 at 13:08
Vikas RatheeVikas Rathee
617
asked Nov 13 '18 at 13:08
Vikas RatheeVikas Rathee
617
asked Nov 13 '18 at 13:08
Vikas RatheeVikas Rathee
617
617
closed as off-topic by Toby Speight, Rory Daulton, Jon Clements♦ Nov 13 '18 at 14:17
- This question does not appear to be about programming within the scope defined in the help center.
closed as off-topic by Toby Speight, Rory Daulton, Jon Clements♦ Nov 13 '18 at 14:17
- This question does not appear to be about programming within the scope defined in the help center.
5
this question is about maths and has nothing to do with c++ or programming in general
– user463035818
Nov 13 '18 at 13:12
1
@user463035818: “How can I find…” with the C++ tag is a request for expressing an algorithm in C++ code. If the OP is interested in implementing the algorithm in C++, it is not an unrelated tag.
– Eric Postpischil
Nov 13 '18 at 13:31
1
@user463035818: The question does not ask for a book, tool, library, tutorial, or other off-site resource. It does ask for information. You could answer that with code, or you could answer it with information about what algorithm would solve the problem and how it could be implemented in C++.
– Eric Postpischil
Nov 13 '18 at 13:40
4
I'm voting to close this question as off-topic because it is not about programming but rather belongs on Mathematics Stack Exchange once the questioner has added more of his own work and explained just where he is stuck.
– Rory Daulton
Nov 13 '18 at 14:13
2
@Damien: If the OP modifies the question, it gets bumped to the top of the review queue and more people will look at it. People with enough reputation can vote to reopen the question. Five votes will reopen the question, then more answers may be given. For me to vote to reopen, the OP will need to show how this is a practical programming problem. That will be difficult, since I know the answer to the question and the difficulty is all mathematical--the programming is trivial.
– Rory Daulton
Nov 13 '18 at 14:34
|
show 3 more comments
5
this question is about maths and has nothing to do with c++ or programming in general
– user463035818
Nov 13 '18 at 13:12
1
@user463035818: “How can I find…” with the C++ tag is a request for expressing an algorithm in C++ code. If the OP is interested in implementing the algorithm in C++, it is not an unrelated tag.
– Eric Postpischil
Nov 13 '18 at 13:31
1
@user463035818: The question does not ask for a book, tool, library, tutorial, or other off-site resource. It does ask for information. You could answer that with code, or you could answer it with information about what algorithm would solve the problem and how it could be implemented in C++.
– Eric Postpischil
Nov 13 '18 at 13:40
4
I'm voting to close this question as off-topic because it is not about programming but rather belongs on Mathematics Stack Exchange once the questioner has added more of his own work and explained just where he is stuck.
– Rory Daulton
Nov 13 '18 at 14:13
2
@Damien: If the OP modifies the question, it gets bumped to the top of the review queue and more people will look at it. People with enough reputation can vote to reopen the question. Five votes will reopen the question, then more answers may be given. For me to vote to reopen, the OP will need to show how this is a practical programming problem. That will be difficult, since I know the answer to the question and the difficulty is all mathematical--the programming is trivial.
– Rory Daulton
Nov 13 '18 at 14:34
5
5
this question is about maths and has nothing to do with c++ or programming in general
– user463035818
Nov 13 '18 at 13:12
this question is about maths and has nothing to do with c++ or programming in general
– user463035818
Nov 13 '18 at 13:12
1
1
@user463035818: “How can I find…” with the C++ tag is a request for expressing an algorithm in C++ code. If the OP is interested in implementing the algorithm in C++, it is not an unrelated tag.
– Eric Postpischil
Nov 13 '18 at 13:31
@user463035818: “How can I find…” with the C++ tag is a request for expressing an algorithm in C++ code. If the OP is interested in implementing the algorithm in C++, it is not an unrelated tag.
– Eric Postpischil
Nov 13 '18 at 13:31
1
1
@user463035818: The question does not ask for a book, tool, library, tutorial, or other off-site resource. It does ask for information. You could answer that with code, or you could answer it with information about what algorithm would solve the problem and how it could be implemented in C++.
– Eric Postpischil
Nov 13 '18 at 13:40
@user463035818: The question does not ask for a book, tool, library, tutorial, or other off-site resource. It does ask for information. You could answer that with code, or you could answer it with information about what algorithm would solve the problem and how it could be implemented in C++.
– Eric Postpischil
Nov 13 '18 at 13:40
4
4
I'm voting to close this question as off-topic because it is not about programming but rather belongs on Mathematics Stack Exchange once the questioner has added more of his own work and explained just where he is stuck.
– Rory Daulton
Nov 13 '18 at 14:13
I'm voting to close this question as off-topic because it is not about programming but rather belongs on Mathematics Stack Exchange once the questioner has added more of his own work and explained just where he is stuck.
– Rory Daulton
Nov 13 '18 at 14:13
2
2
@Damien: If the OP modifies the question, it gets bumped to the top of the review queue and more people will look at it. People with enough reputation can vote to reopen the question. Five votes will reopen the question, then more answers may be given. For me to vote to reopen, the OP will need to show how this is a practical programming problem. That will be difficult, since I know the answer to the question and the difficulty is all mathematical--the programming is trivial.
– Rory Daulton
Nov 13 '18 at 14:34
@Damien: If the OP modifies the question, it gets bumped to the top of the review queue and more people will look at it. People with enough reputation can vote to reopen the question. Five votes will reopen the question, then more answers may be given. For me to vote to reopen, the OP will need to show how this is a practical programming problem. That will be difficult, since I know the answer to the question and the difficulty is all mathematical--the programming is trivial.
– Rory Daulton
Nov 13 '18 at 14:34
|
show 3 more comments
1 Answer
1
active
oldest
votes
2
This relation corresponds to the Bézout's identity.
All solutions are given by (x + k*b/gcd(a,b), y -k*a/gcd(a,b)), if (x,y) is a particular solution, where k is an arbitrary integer.
The particular (x,y) solution is for example provided by the extended Euclidian algorithm.
The pair (b/gcd(a,b), -a/gcd(a,b)) is the 'smallest' (u,v) pair such that ua + vb = 0.
Source: Wikipedia!
edited Nov 13 '18 at 15:17
James K Polk
30.1k116896
answered Nov 13 '18 at 13:21
DamienDamien
707125
@James K Polk Thank you for editing. Please note that it was a mathematical answer, not a C++ one. In my mathematics classes a very long time ago, the professor was using the term 'couple'. But it was in French, may be different in English. Anyway, as there is a 'C++' tag, better to usepaireffectively.
– Damien
Nov 13 '18 at 15:29
Yes, I went out on a limb in my edit, in my English math classes our instructors always used the word 'pair', however if you prefer 'couple' you can revert the edit or I'll gladly do it.
– James K Polk
Nov 13 '18 at 15:32
1
@James K Polk It is assumed to be an answer in English! Better to use 'pair'. Thank you again for the correction.
– Damien
Nov 13 '18 at 15:36
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
2
This relation corresponds to the Bézout's identity.
All solutions are given by (x + k*b/gcd(a,b), y -k*a/gcd(a,b)), if (x,y) is a particular solution, where k is an arbitrary integer.
The particular (x,y) solution is for example provided by the extended Euclidian algorithm.
The pair (b/gcd(a,b), -a/gcd(a,b)) is the 'smallest' (u,v) pair such that ua + vb = 0.
Source: Wikipedia!
edited Nov 13 '18 at 15:17
James K Polk
30.1k116896
answered Nov 13 '18 at 13:21
DamienDamien
707125
@James K Polk Thank you for editing. Please note that it was a mathematical answer, not a C++ one. In my mathematics classes a very long time ago, the professor was using the term 'couple'. But it was in French, may be different in English. Anyway, as there is a 'C++' tag, better to usepaireffectively.
– Damien
Nov 13 '18 at 15:29
Yes, I went out on a limb in my edit, in my English math classes our instructors always used the word 'pair', however if you prefer 'couple' you can revert the edit or I'll gladly do it.
– James K Polk
Nov 13 '18 at 15:32
1
@James K Polk It is assumed to be an answer in English! Better to use 'pair'. Thank you again for the correction.
– Damien
Nov 13 '18 at 15:36
add a comment |
2
This relation corresponds to the Bézout's identity.
All solutions are given by (x + k*b/gcd(a,b), y -k*a/gcd(a,b)), if (x,y) is a particular solution, where k is an arbitrary integer.
The particular (x,y) solution is for example provided by the extended Euclidian algorithm.
The pair (b/gcd(a,b), -a/gcd(a,b)) is the 'smallest' (u,v) pair such that ua + vb = 0.
Source: Wikipedia!
edited Nov 13 '18 at 15:17
James K Polk
30.1k116896
answered Nov 13 '18 at 13:21
DamienDamien
707125
@James K Polk Thank you for editing. Please note that it was a mathematical answer, not a C++ one. In my mathematics classes a very long time ago, the professor was using the term 'couple'. But it was in French, may be different in English. Anyway, as there is a 'C++' tag, better to usepaireffectively.
– Damien
Nov 13 '18 at 15:29
Yes, I went out on a limb in my edit, in my English math classes our instructors always used the word 'pair', however if you prefer 'couple' you can revert the edit or I'll gladly do it.
– James K Polk
Nov 13 '18 at 15:32
1
@James K Polk It is assumed to be an answer in English! Better to use 'pair'. Thank you again for the correction.
– Damien
Nov 13 '18 at 15:36
add a comment |
2
2
2
This relation corresponds to the Bézout's identity.
All solutions are given by (x + k*b/gcd(a,b), y -k*a/gcd(a,b)), if (x,y) is a particular solution, where k is an arbitrary integer.
The particular (x,y) solution is for example provided by the extended Euclidian algorithm.
The pair (b/gcd(a,b), -a/gcd(a,b)) is the 'smallest' (u,v) pair such that ua + vb = 0.
Source: Wikipedia!
edited Nov 13 '18 at 15:17
James K Polk
30.1k116896
answered Nov 13 '18 at 13:21
DamienDamien
707125
This relation corresponds to the Bézout's identity.
All solutions are given by (x + k*b/gcd(a,b), y -k*a/gcd(a,b)), if (x,y) is a particular solution, where k is an arbitrary integer.
The particular (x,y) solution is for example provided by the extended Euclidian algorithm.
The pair (b/gcd(a,b), -a/gcd(a,b)) is the 'smallest' (u,v) pair such that ua + vb = 0.
Source: Wikipedia!
edited Nov 13 '18 at 15:17
James K Polk
30.1k116896
answered Nov 13 '18 at 13:21
DamienDamien
707125
edited Nov 13 '18 at 15:17
James K Polk
30.1k116896
edited Nov 13 '18 at 15:17
James K Polk
30.1k116896
edited Nov 13 '18 at 15:17
James K Polk
30.1k116896
30.1k116896
answered Nov 13 '18 at 13:21
DamienDamien
707125
answered Nov 13 '18 at 13:21
DamienDamien
707125
answered Nov 13 '18 at 13:21
DamienDamien
707125
707125
@James K Polk Thank you for editing. Please note that it was a mathematical answer, not a C++ one. In my mathematics classes a very long time ago, the professor was using the term 'couple'. But it was in French, may be different in English. Anyway, as there is a 'C++' tag, better to usepaireffectively.
– Damien
Nov 13 '18 at 15:29
Yes, I went out on a limb in my edit, in my English math classes our instructors always used the word 'pair', however if you prefer 'couple' you can revert the edit or I'll gladly do it.
– James K Polk
Nov 13 '18 at 15:32
1
@James K Polk It is assumed to be an answer in English! Better to use 'pair'. Thank you again for the correction.
– Damien
Nov 13 '18 at 15:36
add a comment |
@James K Polk Thank you for editing. Please note that it was a mathematical answer, not a C++ one. In my mathematics classes a very long time ago, the professor was using the term 'couple'. But it was in French, may be different in English. Anyway, as there is a 'C++' tag, better to usepaireffectively.
– Damien
Nov 13 '18 at 15:29
Yes, I went out on a limb in my edit, in my English math classes our instructors always used the word 'pair', however if you prefer 'couple' you can revert the edit or I'll gladly do it.
– James K Polk
Nov 13 '18 at 15:32
1
@James K Polk It is assumed to be an answer in English! Better to use 'pair'. Thank you again for the correction.
– Damien
Nov 13 '18 at 15:36
@James K Polk Thank you for editing. Please note that it was a mathematical answer, not a C++ one. In my mathematics classes a very long time ago, the professor was using the term 'couple'. But it was in French, may be different in English. Anyway, as there is a 'C++' tag, better to use
pair effectively.– Damien
Nov 13 '18 at 15:29
@James K Polk Thank you for editing. Please note that it was a mathematical answer, not a C++ one. In my mathematics classes a very long time ago, the professor was using the term 'couple'. But it was in French, may be different in English. Anyway, as there is a 'C++' tag, better to use
pair effectively.– Damien
Nov 13 '18 at 15:29
Yes, I went out on a limb in my edit, in my English math classes our instructors always used the word 'pair', however if you prefer 'couple' you can revert the edit or I'll gladly do it.
– James K Polk
Nov 13 '18 at 15:32
Yes, I went out on a limb in my edit, in my English math classes our instructors always used the word 'pair', however if you prefer 'couple' you can revert the edit or I'll gladly do it.
– James K Polk
Nov 13 '18 at 15:32
1
1
@James K Polk It is assumed to be an answer in English! Better to use 'pair'. Thank you again for the correction.
– Damien
Nov 13 '18 at 15:36
@James K Polk It is assumed to be an answer in English! Better to use 'pair'. Thank you again for the correction.
– Damien
Nov 13 '18 at 15:36
add a comment |
5
this question is about maths and has nothing to do with c++ or programming in general
– user463035818
Nov 13 '18 at 13:12
1
@user463035818: “How can I find…” with the C++ tag is a request for expressing an algorithm in C++ code. If the OP is interested in implementing the algorithm in C++, it is not an unrelated tag.
– Eric Postpischil
Nov 13 '18 at 13:31
1
@user463035818: The question does not ask for a book, tool, library, tutorial, or other off-site resource. It does ask for information. You could answer that with code, or you could answer it with information about what algorithm would solve the problem and how it could be implemented in C++.
– Eric Postpischil
Nov 13 '18 at 13:40
4
I'm voting to close this question as off-topic because it is not about programming but rather belongs on Mathematics Stack Exchange once the questioner has added more of his own work and explained just where he is stuck.
– Rory Daulton
Nov 13 '18 at 14:13
2
@Damien: If the OP modifies the question, it gets bumped to the top of the review queue and more people will look at it. People with enough reputation can vote to reopen the question. Five votes will reopen the question, then more answers may be given. For me to vote to reopen, the OP will need to show how this is a practical programming problem. That will be difficult, since I know the answer to the question and the difficulty is all mathematical--the programming is trivial.
– Rory Daulton
Nov 13 '18 at 14:34