Euclidean Algorithm

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.
Links to this page
  • Greatest Common Divisor (GCD)

    To find \(GCD(a, b)\), one could use Euclidean Algorithm# using the theorem \(GCD(a, b) = GCD(b, a \mod b); a > b\) to find the largest #Divisor that could divide both \(a\) and \(b\). If the GCD between the two numbers is 1, then we could say that \(a\) and \(b\) are relatively prime to each other and a multiplicative inverse# could be found. There are several rules to know:

  • Field

    Thus found the inverse of \(a\) in modular sense. To do that, we utilises the Euclidean Algorithm# and extends its steps on \(a \mod n\) as follows:

#math #algorithm