# Euclids algorithm

#### cs1632

Find two different pairs of integers (r,s) such that 27r + 19s =1. In the first case r should be positive; in the second case s should be positive.
Can anyone help?
Thanks

#### johng

Since your user name is cs, I assume you know some programming. Here's the extended Euclidean algorithm in C; it finds the d=gcd(a,b) and also integers m and n with ma+nb=d.

Code:
/* Uses the Euclidean algorithm to compute d=gcd(a,b).  Here, a and b MUST be
positive. Also finds m and n with ma+nb=d.  In the code below,
a1=m0*a+n0*b and b1=m1*a+n1*b is a loop invariant of the while loop.  So
the correct return is m0,n0.
*/
int gcd(int* m,int *n,int a,int b) {
int a1=a;
int b1=b;
int m0=1,n0=0,m1=0,n1=1,r,q,m2,n2;
while (b1!=0) {
r=a1%b1;
q=a1/b1;
m2=m0-m1*q;
n2=n0-n1*q;
m0=m1;
n0=n1;
m1=m2;
n1=n2;
a1=b1;
b1=r;
}
*m=m0;
*n=n0;
return(a1);
}
For a=27 and b=19, the above computes m=-7 and n=19. So 27(-7)+19(10)=1. Now for any diophantine equation $ax+by=d$, for $x_0$ and $y_0$ one solution, any solution is of the form $x_0-bt$ and $y_0+at$ where $t$ is an arbitrary integer. So from the particular solution, you can easily find requested solutions.

#### HallsofIvy

MHF Helper
19 divides into 27 once with remainder 8: 27- 19= 8.
8 divides into 19 twice with remainder 3: 19- 2(8)= 3
3 divides into 8 twice with remainder 2: 8- 2(3)= 2
Finally, 2 divides into 3 once with remainder 1: 3- 2= 1.
(That's the "Euclidean algorithm" part.)

Replace that "2" with 8- 2(3): 3- (8- 2(3))= 3(3)- 8= 1.
Replace that "3" with 19- 2(8): 3(19- 2(8))- 8= 3(19)- 7(8)= 1.
Repace that "8" with 27- 19: 3(19)- 7(27- 19)= 10(19)- 7(27)= 1.

So one solution to "27r + 19s =1" is s= 10, r= -7. Check: 27(-7)+ 19(10)= -189+ 190= 1.

But if r and s are solutions so are r+ 19n and s- 27n for any integer r: 27(r+ 19n)+ 19(s- 27n)= 27r+ (19)(27)n+ 19r- (19)(27)n= 27r+ 19s= 1.

Taking n= 1 gives r= -7+ 19= 12, s= 10- 27= -17. Check: 27(12)+ 19(-17)= 324- 323= 1.

#### DenisB

74 solutions in range -999 to 999.
High:
696, -989
-691, 982