gcd(1232,572) &=& gcd(1232 \mod 572, 572) = gcd(572,88) gcd(572,88) &=& gcd(572 \mod 88, 88) = gcd(88,44) gcd(88,44) &=& gcd(88 \mod 44, 44) = gcd(44,0) gcd of p=1232 and q=572 = 44 1232*-6 + 572*13 = 44 gcd(1232,573) &=& gcd(1232 \mod 573, 573) = gcd(573,86) gcd(573,86) &=& gcd(573 \mod 86, 86) = gcd(86,57) gcd(86,57) &=& gcd(86 \mod 57, 57) = gcd(57,29) gcd(57,29) &=& gcd(57 \mod 29, 29) = gcd(29,28) gcd(29,28) &=& gcd(29 \mod 28, 28) = gcd(28,1) gcd(28,1) &=& gcd(28 \mod 1, 1) = gcd(1,0) gcd of p=1232 and q=573 = 1 1232*20 + 573*-43 = 1 gcd(123421389,123421389) &=& gcd(123421389 \mod 123421389, 123421389) = gcd(123421389,0) gcd of p=123421389 and q=123421389 = 123421389 123421389*0 + 123421389*1 = 123421389 gcd(342,324) &=& gcd(342 \mod 324, 324) = gcd(324,18) gcd(324,18) &=& gcd(324 \mod 18, 18) = gcd(18,0) gcd of p=324 and q=342 = 18 324*-1 + 342*1 = 18 gcd(234234,323) &=& gcd(234234 \mod 323, 323) = gcd(323,59) gcd(323,59) &=& gcd(323 \mod 59, 59) = gcd(59,28) gcd(59,28) &=& gcd(59 \mod 28, 28) = gcd(28,3) gcd(28,3) &=& gcd(28 \mod 3, 3) = gcd(3,1) gcd(3,1) &=& gcd(3 \mod 1, 1) = gcd(1,0) gcd of p=234234 and q=323 = 1 234234*-104 + 323*75419 = 1 gcd(34232,1) &=& gcd(34232 \mod 1, 1) = gcd(1,0) gcd of p=34232 and q=1 = 1 34232*0 + 1*1 = 1 gcd of p=234243 and q=0 = 234243 234243*1 + 0*0 = 234243