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)