ریاضیات

مراحل الگوریتم:

1. ورودی: چندجمله‌ای f(x) ∈ F[x] و چندجمله‌ای کمینه p(x) با deg(p(x)) = n.

2. اجرای تقسیم اقلیدسی: تقسیم f(x) بر p(x) در F[x] جهت یافتن خارج‌قسمت q(x) و باقی‌مانده r(x):

   f(x) = q(x) · p(x) + r(x)   ,   deg(r(x)) < n

3. ارزیابی روی ریشه (α): چون p(α) = 0 است، داریم:

   f(α) = q(α) · p(α) + r(α) = q(α) · 0 + r(α) = r(α)

4. خروجی: بسط یکتای r(α) به صورت ترکیب خطی اعضای پایه:

   r(α) = c₀ + c₁α + c₂α² + ... + c_n-1α^n-1    (c_i ∈ F)

مراحل الگوریتم:

1. ورودی: چندجمله‌ای g(x) به طوری که g(α) ≠ 0 (یعنی p(x) شمارنده‌ی g(x) نیست).

2. بررسی اول بودن متقابل: چون p(x) در F[x] تحویل‌ناپذیر است و p(x) ∤ g(x)، بنابراین بزرگ‌ترین مقسوم‌علیه مشترک آن‌ها برابر ۱ است:

   gcd(g(x), p(x)) = 1

3. همانی بزو (Bezout's Identity): با اعمال الگوریتم اقلیدس تعمیم‌یافته، چندجمله‌ای‌های u(x) و v(x) در F[x] یافت می‌شوند به طوری که:

   u(x) · g(x) + v(x) · p(x) = 1

4. ارزیابی روی α: با جایگذاری α، چون p(α) = 0 است، جمله دوم حذف می‌شود:

   u(α) · g(α) + v(α) · 0 = 1 ⇒ u(α) · g(α) = 1

5. خروجی: عنصر وارون به دست می‌آید:

   [g(α)]^-1 = u(α)

نتیجه ساختاری و جبری:

این دو الگوریتم اثبات می‌کنند که عمل جمع، ضرب و وارون‌سازی در جبر F(α) کاملاً الگوریتمیک بوده و با استفاده از حساب پیمانه‌ای در حلقه خارج‌قسمتی F[x]/⟨p(x)⟩ انجام می‌پذیرد. همچنین بعد این فضا به عنوان فضای برداری روی F متناهی و برابر است با:

[F(α) : F] = deg(p(x)) = n