Euclidean Algorithm is used to find the #Greatest Common Divisor (GCD) between the number \(a\) and \(b\), typically denoted as \(EUCLID(a, n)\). It uses the modulo nature# of two numbers, where \(a = qn + b\), \(b\) as the remainder of \(a \mod n\), following the steps:
- Apply the formula \(a = qn + b\),
- If \(b = 0\), then \(n = GCD(a, n)\),
- Replace the value of \(a\) with \(n\) and the value of \(n\) with \(b\) in the equation,
- Repeat step 1.