Question

Find the greatest common divisor d = gcd(527, 341). Show all calculation steps.

We assume that the modulus is a positive integer. But the definition of the
expression a mod n also makes perfect sense if n is negative. Determine the following:

a. 7 mod 4
b. 7 mod -4
c. -7 mod 4
d. -7 mod -4

Answer 1

We can use the Euclidean Algorithm here to find GCD of two numbers.

• If X = 0 then GCD(X,Y)=Y, since the GCD(0,Y)=Y, stop.
• If B = 0 then GCD(X,Y)=X, since the GCD(X,0)=X, stop.
  • Write X in quotient remainder form (X= Y⋅P + D) where P is quotient and D is remainder
• Find GCD(Y,R) using the Euclidean Algorithm since GCD(X,Y) = GCD(Y,R)

GCD(527,341) =
X = 527, Y = 341
X ≠ 0 , Y ≠ 0
527 = 341 * 1 + 186
GCD(527,341) = GCD(341,186)

Again,
GCD(341,186)
X = 341, Y = 186
X ≠ 0 , Y ≠ 0
341 = 186 * 1 + 155
GCD(341,186) = GCD(186,155)

GCD(186, 155)
X = 186, Y = 155
X ≠ 0 , Y ≠ 0
186 = 151 * 1 + 31
GCD(186,155) = GCD(155,31)

GCD(155,31)
X = 155, Y = 31
X ≠ 0 , Y ≠ 0
155 = 31 * 5 + 0
GCD(155,31) = GCD(31,0)

And by Euclidean algorithm GCD(31, 0 ) = 31

Hence GCD(527, 341 ) = 31.

The modulus of the follwing:

X mod Y : X = Y*A + R (where A is quotient and R is remainder) R is the answer
But if Y is negative then X mod Y = M , X mod -Y = -(Y-M)
a) 7 mod 4 -> 7 = 4 * 1 + 3 = 3
b) 7 mod -4 -> 7 mod 4 = 3 , Using above -(4-3) = -1
c) -7 mod 4 -> -7 = 4*-2 + 1 = 1
d) -7 mod -4 -> -7 = -4 *1 +(-3) = -3