Greatest Common Divisor using Extended Euclid's Algorithm

[sdlt85]

Hi,
Can someone help me with an idea on how to start writing a C++ code
for generating
greatest common divisor and the linear combination of two intergers
represented as gcd(m, n)= mx + ny and adding them it will give us the
greatest common divisor and I need to use the extended Euclidean
algorithm.
I already have the code for the greatest common divisor but I dont
know how to do the linear combination.

This is what I have:

#include <iostream>
#include <iomanip>
using namespace std;

void gcd(int, int);
void extended_gcd(int, int, int, int);

int main()
{
int m=0, n=0;


cout<<"Welcome to the Greatest Common Divisor Program\n\n";
cout<<"Enter the first number: ";
cin>>m;
cout<<endl;
cout<<"Enter the second number: ";
cin>>n;
cout<<endl;
cout<<"gcd("<<m<<", "<<n<<") = ";
gcd(m, n);
return 0;
}

void gcd(int m, int n)
{
int r, q, d;
while (n!=0)
{
r = m % n;
q = m / n;
r = m - n * q; // I was thinking on put it
on the stack
// but I dont know how
m = n;
n = r;
}

d = m;
cout<<d<<endl; //then pop the stack as d=r-q*n
}

 

[Bernd Strieder]

Hello,

Hi,
Can someone help me with an idea on how to start writing a C++ code
for generating
greatest common divisor and the linear combination of two intergers
represented as gcd(m, n)= mx + ny and adding them it will give us the
greatest common divisor and I need to use the extended Euclidean
algorithm.
I already have the code for the greatest common divisor but I dont
know how to do the linear combination.

It's not easy to find on your own, but it is easy to code.

Use your favourite textbooks on computer algebra as a starting point, or
start reading with the Wikipedia article, I think there are example
implementations referenced easily adaptable to C++.

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Bernd Strieder

 

[Gianni Mariani]

Hi,
Can someone help me with an idea on how to start writing a C++ code
for generating
greatest common divisor and the linear combination of two intergers
represented as gcd(m, n)= mx + ny

gcd(m, n)= mx + ny ???

It makes no sense to me.

gcd( m, n ) is always going to be less than or equal to m or n.

mx + ny will be larger than either of m or n.

What exactly is it you are trying to do ?