Euclid's algorithm
Division-based GCD method
Euclid's algorithm is a method for finding the greatest common divisor of two numbers.
You repeatedly divide the larger number by the smaller, then replace the larger with the remainder, until the remainder is zero—the last nonzero remainder is the answer.
Dating to ancient Greece, it remains one of the oldest algorithms still in practical use, appearing in cryptography and computer science.
What's left over
- divisionSplitting into parts
- modulusAbsolute value operation
- iterationRepeated procedural pass
- recursionProcess invoking itself
subtraction · quotient · divisor · dividend · loop · termination · convergence · step-by-step
Science of secure messaging
- RSAPublic-key encryption algorithm
- fractionsParts expressed numerically
- simplificationMaking something less complex
- ratiosComparative numerical relationships
Numbers without fractional components
- primeReadying for action
- factorizationDecomposing into multiplicative parts
- divisibilityAbility to divide evenly
- congruenceState of agreement
composite · irreducible · reduce · simplify · fractions · numerator · denominator
Demonstration of truth
- theoremDemonstrated logical conclusion
- lemmaBase form, or helper theorem
- axiomSelf-evident starting principle
- geometryScience of spatial relationships
Alexandria · proposition · deduction · reasoning · well-ordering · induction · correctness · constructive
remainder
What's left over
recursion · subtraction · quotient · divisor · dividend · loop · termination · convergence · step-by-step · procedure
cryptography
Science of secure messaging
- RSAPublic-key encryption algorithm
- fractionsParts expressed numerically
- simplificationMaking something less complex
integers
Numbers without fractional components
- primeReadying for action
- factorizationDecomposing into multiplicative parts
- divisibilityAbility to divide evenly
congruence · composite · irreducible · reduce · simplify · fractions · numerator · denominator
proof
Demonstration of truth
- theoremDemonstrated logical conclusion
- lemmaBase form, or helper theorem
- axiomSelf-evident starting principle
geometry · Alexandria · proposition · deduction · reasoning · well-ordering · induction · correctness · constructive · deterministic