Examples on GCD Properties

In this class, We discuss Examples on GCD Properties.

The reader should have prior knowledge of GCD properties. Click Here.

Examples:

1) Find integers U and V such that GCD( 615, 1080) = 615u + 1080v

1080 = 1 * 615 + 465

615 = 1 * 465 + 150

465 = 3 * 150 + 15

150 = 10 * 15 + 0

GCD(615, 1080) = 15

Now to identify U and Vvalues we move in reverse.

15 = 465 – 3 * 150 from the above equations.

15 = 465 – 3*(615 – 465)

15 = 4 * 465 – 3 * 615

15 = 4*(1080 – 615) – 3* 615

15 = 615 * (-7) + 1080 * 4

U = -7 and v = 4