# Thread: Help With Euclids Extended Algorithim ( Integer division by zero Error )

1. ## Help With Euclids Extended Algorithim ( Integer division by zero Error )

so im doing a program on euclids algorithim, and im having problems with the last function,

i made a menu to allow the user to choose between the normal gcd calculator or
to view the extended algorithim which displays the steps, unfortunatly i am having a problem with the extended part. help would be much appreciated, thanks

Code:
```#include<iostream>
#include<iomanip>

using namespace std;

int Normal_GCD();
int Extended_Euclidian_Algorithim();

int main()         // Main Program Scope
{

int arraycounter = 0;

cout << "-----Select a option-----\n";
cout << " 0 GCD Calculator\n";
cout << " 1 Extended Euclidian Algorithim\n";
cout << " 2 Quit\n";

Normal_GCD();

if ( menuvalue == 1 )
Extended_Euclidian_Algorithim();

return 0;

}

//---------------------------------------------------------------------------------------------------------------------------//

int Normal_GCD()
{
int dividend, divisor, remainder, number1, number2 = 0;  // Declaring Variables

cout << " This Function Will Find The GCD Of 2 Numbers " << endl << endl; // States What The Program Will Do

cout << "Plese Enter The First Number: ";                                     // Enters First Number And
cin >> number1;                                                               // Assigns It To The First
cout << endl << endl;                                                         // Variable Slot .

cout << "Please Enter The Second Number: ";                                   // Enters Second Number And
cin >> number2;                                                               // Assigns It To The Second
cout << endl << endl;                                                         // Variable Slot .

if (number1 > number2)                                                        // If The First Number Was The Bigger Number Then
{																			  // It Was Placed As The Dividend
dividend = number1;
divisor = number2;
}

else                                                                          // If The Second Number Was The Bigger Number Then
{																			  // It Was Placed As The Dividend
dividend = number2;
divisor = number1;
}

do{
remainder = dividend % divisor;

if(remainder !=0)
{
dividend = divisor;
divisor = remainder;
}

}
while(remainder != 0); //Loops Until The Remainder Is 0

cout << " The GCD OF " << number1 << " And " << number2 << " is: " << divisor << endl << endl;    // Calls The Details And Places Them Into A Sentence
cout << setw(15) << "Proof: " << endl << endl;

cout << "GCD" << endl;
cout << setw(2) << divisor << " * " << number1 / divisor << " = " << (number1 / divisor) * divisor << endl;
cout << setw(2) << divisor << " * " << number2 / divisor << " = " << (number2 / divisor) * divisor << endl << endl;

system("PAUSE");
return 0;
}

//---------------------------------------------------------------------------------------------------------------------------//

int Extended_Euclidian_Algorithim()
{
int a;
int b;

cout << "Please Enter The First Number : ";
cin >> a;
cout << endl << endl;

cout << "Please Enter The Second Number : ";
cin >> b;
cout << endl << endl;

int x[3];
int y[3];
int quotient  = a / b;
int remainder = a % b;

x[0] = 0;
y[0] = 1;
x[1] = 1;
y[1] = quotient * -1;

int i = 2;
for (; (b % (a%b)) != 0; i++)
{
a = b;
b = remainder;
quotient = a / b;
remainder = a % b;
x[i % 3] = (quotient * -1 * x[(i - 1) % 3]) + x[(i - 2) % 3];

cout << x [i % 3] << " = " << " ( " << (quotient * -1 * x[(i - 1) % 3]) << "  + " << x[(i - 2) % 3] << endl;

y[i % 3] = (quotient * -1 * y[(i - 1) % 3]) + y[(i - 2) % 3];

cout << x [i % 3] << " = " << " ( " << (quotient * -1 * x[(i - 1) % 3]) << "  + " << x[(i - 2) % 3] << endl;

}

//x[i — 1 % 3] is inverse of a
//y[i — 1 % 3] is inverse of b
return x[(i - 1) % 3];

}```

2. Have you tried using a debugger to step through your code? It'll show you where the error occurs. Debuggers are very useful - get to know yours well!

3. Code:
`for (; (b % (a%b)) != 0; i++)`
If 'a' starts out as 4 and 'b' starts out as 2, what do you expect the value of b % (a%b) to be?Or even simpler, what about just a%b?