Euclidean algorithm for greatest common divisor

GPTKB entity

Statements (22)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
gptkbp:application cryptography
modular arithmetic
simplifying fractions
gptkbp:category classical algorithm
deterministic algorithm
gptkbp:complexity O(log n)
gptkbp:field gptkb:mathematics
number theory
gptkbp:generalizes gptkb:extended_Euclidean_algorithm
https://www.w3.org/2000/01/rdf-schema#label Euclidean algorithm for greatest common divisor
gptkbp:input two integers
gptkbp:introducedIn gptkb:Euclid's_Elements
circa 300 BC
gptkbp:method repeated division
gptkbp:namedAfter gptkb:Euclid
gptkbp:output greatest common divisor
gptkbp:purpose compute greatest common divisor
gptkbp:relatedTo gptkb:Bézout's_identity
gptkb:Diophantine_equations
gptkbp:bfsParent gptkb:Euclid_of_Alexandria
gptkbp:bfsLayer 7