toy wrote:

Ok I changed the code to decrement i and j as opposed to

increment...the for loops will also execute until i and j are their

NEGATIVE values.

i still am not generating a solution. can u help?

Sure. Here is a simple version of Euclids algorithm:

#include <iostream>

#include <algorithm>

unsigned long gcd_euclid ( unsigned long a, unsigned long b ) {

if ( b < a ) {

std::swap( a, b );

}

while ( a != 0 ) {

// now b = a*q + r for some q and r. (division with remainder)

unsigned long q = b / a;

unsigned long r = b % a;

std::cout << r << " = " << b << " - " << a << "*" << q << '\n';

b = a;

a = r;

}

return ( b );

}

int main ( void ) {

std::cout <<gcd_euclid( 65537, 3551 ) << '\n';

}

If you run this, you find: the output

1619 = 65537 - 3551*18

313 = 3551 - 1619*2

54 = 1619 - 313*5

43 = 313 - 54*5

11 = 54 - 43*1

10 = 43 - 11*3

1 = 11 - 10*1 <--- important information

0 = 10 - 1*10

The magic of the algorithm is that all these equations are actually true.

Now, you can work backwards:

1 = 11 - 10 * 1;

= 11 - ( 43 - 11 * 3 ) * 1 = 11 * 4 - 43

= ( 54 - 43 ) * 4 - 43 = 54*4 - 43*5

= 54*4 - ( 313 - 54*5) * 5 = 313*(-5) + 54*29

= ...

Another way is working forward:

1619 = 65537 - 3551*18

313 = 3551 - 1619*2 = 3551 - ( 65537-3551*18 ) * 2

= 65537*(-2) + 3551*37

54 = 1619 - 313*5

= ( 65537-3551*18 ) - ( 65537*(-2) + 3551*37 ) * 5

= 65537*someting + 3551*something_else

....

keep going until you get

....

1 = 65537*something + 3551*something_else

These ideas should get you started.

Best

Kai-Uwe Bux