.

# Euclidean Algorithm Assignment Help

The Euclidean Algorithm is usually a technique for easily choosing the GCD (Greatest Common Divisor) associated with two integers.

## The Algorithm

The Euclidean Algorithm with regard to obtaining GCD(A, B) is really as comes after:

- If A = 0 then GCD(A, B) = B,
- Since the GCD(0, B) = B, and we can stop.

- If B = 0 then GCD(A, B) = A,
- Since the GCD(A, 0) = A, and we can stop.

- Write A in quotient remainder form (A = B⋅Q + R)
- Find GCD(B, R) using the Euclidean Algorithm
- Since GCD(A, B) = GCD(B, R)

### Example: Find the GCD of 270 and 192

- A = 270, B = 192
- A ≠ 0 (A not equal to 0)
- B ≠ 0 (B not equal to 0)
- Make use of long division to get in which 270/192 = 1 with a remainder of 78. We can write this as: 270 = 192 * 1 + 78
- Find GCD(192, 78), since GCD(270, 192) = GCD(192, 78)

**A = 192, B = 78**

- A ≠ 0 (A not equal to 0)
- B ≠ 0 (B not equal to 0)
- Make use of long division to get in which 192/78 = 2 with a remainder of 36. We can write this as:
- 192 = 78 * 2 + 36
- Find GCD(78, 36), since GCD(192, 78) = GCD(78, 36)

**A = 78, B = 36**

- A ≠ 0 (A not equal to 0)
- B ≠ 0 (B not equal to 0)
- Make use of long division to get in which 78/36 = 2 with a remainder of 6. We could compose this kind of since:
- 78 = 36 * 2 + 6
- Find GCD(36, 6), since GCD(78, 36) = GCD(36, 6)

**A = 36, B = 6**

- A ≠ 0 (A not equal to 0)
- B ≠ 0 (B not equal to 0)
- Make use of long division to get in which 36/6 = 6 with a remainder of 0. We can write this as:
- 36 = 6 * 6 + 0
- Find GCD(6, 0), since GCD(36, 6) = GCD(6, 0)

**A = 6, B = 0**

- A ≠ 0 (A not equal to 0)
- B =0 (B equal to 0)
- GCD(6, 0) = 6

**And so we have now found:**

GCD(270, 192) = GCD(192, 78) = GCD(78, 36) = GCD(36, 6) = GCD(6, 0) = 6 GCD(270, 192) = 6

.