ComputerAlgebra/sem_02_may.md

sheet 1

ex 1

we have to show that the EEA algorithm is finite.

(a)

1. steps (1), (2), (3), (5) are finite
2. in every iteration of step (4) we have 0 <= $e_2 < e_1$. due to this the value of $e_1$ is strictly decreasing. eventually $e_1$ will be 0.

(b)

$ac_0 + bd_0 = e_0$ and $ac_1 + bd_1 = e_1$. (*)

in steps 1, 2 and 3, (*) clearly holds.

in steps 4.1 and 4.2 we have $ac_2 + bd_2 = a(c_0 - qc_1) + b(d_0 - qd_1) = (ac_0 + bd+0) - q(ac_1 + db_1) = e_0 - qe_1 = e_2$.

in step 4.3. we just swap values of $e_1$ and $e_2$ and the equation (*) holds.

in step (3) we have gcd$(e_0, e_1) = gcd(a, b)$ and $e_0 >= e_1$

frobenius endomorphism