[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/euclidean_algorithm.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Euclidean Algorithm" type: concept related: [Divide, Greatest Common Divisor] source: https://www.jemoka.com/posts/kbheuclidean_algorithm/ confidence: high status: active --- A corollary of greatest common divisor and division. Say you have some \(b|a\) such that: \begin{equation} a = bq + r \end{equation} Now, \(d|a,b \Leftrightarrow d|b,r\) (because \(d|b,r\) implies there’s some \(x, x’\) such that \(a = (dx)q+dx’\), and so \(a = d(xq + x’)\) and so \(d|a\); the logic goes the other way too). This finally implies that \(\gcd (a,b)= \gcd (b,r)\) because any divisor that works for one works for both.