[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
×
@jemoka / Jemoka Knowledge Base / raw/concept/kbheuclidean_algorithm.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Euclidean Algorithm" source: https://www.jemoka.com/posts/kbheuclidean_algorithm/ --- 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.