euclidian-algorithm.md (1370B)
1 +++ 2 title = 'Euclidian algorithm' 3 template = 'page-math.html' 4 +++ 5 6 # Euclidian algorithm 7 Use this if you want the gcd of two polynomials. 8 9 Iterative, at each step K is the iteration counter, Q is the quotient, and R is the remainder. S and T give you the multiplication factors. 10 11 Let's say we want gcd of f(x) and g(x), with deg(f) ≥ deg(g): 12 13 <table> 14 <tr> <th>K</th> <th>Q</th> <th>R</th> <th>S(x)</th> <th>T(x)</th> </tr> 15 <tr> <td>0</td> <td>-</td> <td>f(x)</td> <td>1</td> <td>0</td> </tr> 16 <tr> <td>1</td> <td>f(x) / g(x)</td> <td>g(x)</td> <td>0</td> <td>1</td> </tr> 17 <tr> <td>2</td> <td>g(x) / R₂</td> <td>rem( f(x)/g(x) )</td> <td>q₁ s₁ + s₀</td> <td>q₁ t₁ + t₀</td> </tr> 18 <tr> <td>3</td> <td>R₂ / R₃</td> <td>rem( g(x)/R₂ )</td> <td>q₂ s₂ + s₁</td> <td>q₂ t₂ + t₁</td> </tr> 19 <tr> <td>4</td> <td>R₃ / R₄</td> <td>rem( R₂/R₃ )</td> <td>q₃ s₃ + s₂</td> <td>q₃ t₃ + t₂</td> </tr> 20 <tr> <td></td> <td></td> <td><b>0</b></td> <td>⇒ R₄ is the gcd</td> <td></td> </tr> 21 </table> 22 23 This solves the equation r(x) = t(x) f(x) + s(x) g(x) as R₄ = t₄ f + s₄ g. 24