TOPICS
Search

Euclidean Algorithm

Explore EuclideanAlgorithm on MathWorld


The Euclidean algorithm is an algorithm for finding the greatest common divisor of two numbers.

Euclidean algorithm is a college-level concept that would be first encountered in a number theory course.

Prerequisites

Congruence: A congruence is an equation in modular arithmetic, i.e., one in which only the remainders relative to some base, known as the "modulus," are significant.
Greatest Common Divisor: The greatest common divisor of a set of integers is the largest integer that divides all of them.

Classroom Articles on Number Theory (Up to College Level)

  • Continued Fraction
    		•
  • Perfect Number
    		•
  • Convergent
    		•
  • Prime Counting Function
    		•
  • Diophantine Equation
    		•
  • Prime Factorization Algorithms
    		•
  • Divisor Function
    		•
  • Prime Number Theorem
    		•
  • Euler-Mascheroni Constant
    		•
  • Quadratic Reciprocity Theorem
    		•
  • Fermat's Last Theorem
    		•
  • Squarefree
    		•
  • Number Theory
    		•
  • Totient Function
    		•
  • Partition
    		•
  • Transcendental Number
    		•