Euclidean Algorithm
Euclidean Algorithm is the linear programing . Prime numbers are integers . This is the contradiction, but you keep expanding (Λ). [m|a Λ m|b]⇒[m|b-qa = rem(b,a) Λ m|a] rem is the remainder. You can also write this. gcd(a,b)=gcd(rem(b,a),a) gcd is the greatest common divisor. The direction of a and b is crossing over ⇔. gcd(105,224)=gcd(rem(224,105),105)=gcd(14,105) =gcd(rem(105,14),14)=gcd(7,14)=gcd(rem(14,7),7) =gcd(0,7)=7 gcd(135,59)=gcd(17,59)=gcd(rem(59,17),17) =gcd(8,17)=gcd(rem(17,8),8)=gcd(1,8) =gcd(rem(8,1),1)=gcd(0,1)=1 Then you find X and Y which is gcd. 135X+59Y=1 135=59*2+17 59=17*3+8 17=8*2+1 This is upside down. 1=17-8*2 8=59-17*3 17=135-59*2 ∴ 1=17-(59-17*3)*2=17+17*6-59*2=17*7-59*2=(135-59*2)*7-59*2=135*7-59*14-59*2=135*7-59*16 You see X=7 and Y=-16 Therefore 135(X-7)+59(Y+16)=0 X-7=59m and Y+16=-135m (X,Y)=(59m+7,-135m-16)