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







share|improve this question















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.
If this question can be reworded to fit the rules in the help center, please edit the question.











  • 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















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







share|improve this question















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.
If this question can be reworded to fit the rules in the help center, please edit the question.











  • 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








-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







share|improve this question
















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 13 '18 at 13:32







Vikas Rathee

















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.
If this question can be reworded to fit the rules in the help center, please edit the question.







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.
If this question can be reworded to fit the rules in the help center, please edit the question.







  • 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





    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













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!






share|improve this answer

























  • @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






  • 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

















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!






share|improve this answer

























  • @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






  • 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















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!






share|improve this answer

























  • @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






  • 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













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!






share|improve this answer















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!







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 13 '18 at 15:17









James K Polk

30.1k116896




30.1k116896










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 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






  • 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












  • 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





-

Popular posts from this blog

Use pre created SQLite database for Android project in kotlin

Image
0 I am trying to use an already existing sqLite database in my android app. I have verified that it is loaded into the project in the assets folder and I can browse it in DB browser when I open it directly from the project. This is the schema for the table I am trying to query CREATE TABLE "ACTIVITY_LIST_TBL" ( `_ID` INTEGER NOT NULL, `ACT_NAME` VARCHAR NOT NULL, `ACT_CODE` VARCHAR, `IS_ACTIVE` INTEGER DEFAULT -1, PRIMARY KEY(`_ID`) ) Below is the activity that creates the sqlite helper and then on a button click I execute a query on the ACTIVITY_LIST_TBL. When the query is executed this exception is thrown: android.database.sqlite.SQLiteException: no such table: ACTIVITY_LIST_TBL (code 1 SQLITE_ERROR): , while compiling: SELECT * FROM ACTIVITY_LIST_TBL class CalendarActivity : AppCompatActivity() { private var cursor:Cursor? = null override fun onCreate(savedInstanceState:Bundle?) { super.onCreate(savedInstanceState) setContentView(R.layout.calendar_activity...
Read more

Darth Vader #20

Image
Wiki Characters Creators Teams Volumes Issues Publishers Locations Concepts Things Story Arcs Movies Series Episodes New Comics Forums Gen. Discussion Bug Reporting Delete/Combine Pages Artist Show-Off Off-Topic Contests Battles Fan-Fic RPG Comic Book Preview API Developers Editing & Tools Podcast Quests Community Top Users Activity Feed User Lists Community Promos Archives News Reviews Videos Podcasts Previews Login / Sign Up All Wiki     Arcs     Characters     Companies     Concepts     Issues     Locations     Movies     People     Teams     Things     Volumes     Series     Episodes Editorial     Videos     Articles     Reviews     Features ...
Read more

Ondo

Image
Der Titel dieses Artikels ist mehrdeutig. Zu weiteren Bedeutungen siehe Ondo (Begriffsklärung). Ondo Basisdaten Hauptstadt: Akure gegründet: 3. Februar 1976 Gouverneur: Rotimi Akeredolu ISO 3166-2: NG-ON Fläche Fläche: 15.500 km² Rang in Nigeria: 25 Bevölkerung Einwohner: 4.671.700 (2016) Bevölkerungsdichte: 320 Einw./km² (2016) Rang in Nigeria: 18 Lage von Ondo in Nigeria Ondo ist ein Bundesstaat des westafrikanischen Landes Nigeria mit der Hauptstadt Akure, die mit 420.623 Einwohnern (2005) auch die größte Stadt des Bundesstaates ist. Inhaltsverzeichnis 1 Geografie 2 Geschichte 2.1 Liste der Gouverneure und Administratoren 3 Verwaltung 4 Wirtschaft Geografie | Der Bundesstaat liegt im Südwesten des Landes und grenzt im Norden an den Bundesstaat Ekiti, im Nordwesten an den Bundesstaat Osun, im Nordosten an den Bundesstaat Kogi, im Süden an den Atlantik, im Südosten an den Bundesstaat Delta, im Westen an den Bundess...
Read more