excersice 1

show that EEA is an algorithm

1. we work with positive integers
2. on each step positive integer $e_1$ has to get smaller
3. EEA can't be infinite

Show that the output is correct, i.e., a triple with the claimed properties.

TODO

exercise 2

Let p be a prime and let Fp = Z/pZ be the finite field with p elements. Explain how the Extended Euclidean Algorithm can be used to compute the inverse of a unit in Fp.

Filed Z is such filed, that any nonzero element (called a unit) has a multiplicative inverse - meaning that for any a != 0 exists x such that

Inverse of a unit

If we have some a != 0, the inverse is another x such that $$ a * x = 1 mod p $$

$$ a * x = 1 mod p $$

the EEA finds integers x and y such that:

$$ a * x + p * y = gcd(a, p) $$

but p is prime and a != 0, their greatest common divisor (gcd) is 1 $$ gcd(a, p) = 1 $$ so $$ a * x + p * y = 1 $$ now we take modulo (остаток) of p $$ mod(p * y) = 0 $$ $$ => mod(a * x + p * y) = a * x $$

$$ => a * x = 1\ \ mod\ p $$

exercise 3

(a) show that I is an ideal of P = $K[x]$

we need to check that I is closed under addition and under multiplication by any polynomials from P to prove that I is ideal of P

1. closed ander addition

take two elemets of I: $g_1f_1 + g_2f_2$ and $h_1f_1 + h_2f_2$

their sum = $(g_1 + h_1)f_1 + (g_2+ h_2)f_2$

$g_1 + h_1$ is $\in$ P and $g_2 + h_2$ is $\in$ P since P is a ring, so sum has to be in I

__(rings are closed ander addition and multiplication)__

2. take any p $\in$ P

$p * (g_1f_1 + g_2f_2) = p * (g_1 * f_1) + (p * g_2) * f_2$

so lets call $q_1 = p * (g_1 * f_1)$, $q_2 = (p * g_2) * f_2$, so we get $q_1 + q_2$, where $q_1,\ q_2 \in P$, so closed under multiplication

(b) we want to prove that $I = gcd(f_1, f_2)$ where h = Ph is the ideal generated by h.

$ d = gcd(f_1, f_2)$

we need to show:

1. I ⊆ Pd

by EEA there exist polynomials a, b $\in$ P such that: $ af_1 + bf_2 = d$

now, since d divides both $f_1$ and $f_2$, we can write:

$f_1 = df'_1$ and $f_2 = df'_2$ for some $f'_2, f'_1 \in P$

thus:

$g_1f_1 + g_2f_2 = g_1(df'_1) + g_2(df'_2) = d(g_1f'_1 + g_2f'_2)$

thus:

$g_1f_1 + g_2f_2 \in Pd$

2. Pd ⊆ I

every element in $ Pd $ looks like $ p d $ for some $ p \in P $.

but we know:

$ d = af_1 + bf_2 $

so:

$ p d = p(af_1 + bf_2) = (pa)f_1 + (pb)f_2 $

and since $ pa, pb \in P $, $ p d \in I $.

what is Pd

$ P d $ is the ideal generated by $ d $.
it consists of all polynomials that are multiples of $ d $.

exercise 4

__derivative - производная__

1. The finite field $F_p$, the derivative of a ponynomial is computed just like normal, but with one key difference: all arithmetics is done modulo p

$F_p$ is finite filed with p elements where:

• p is prime number
• the elements are {0, 1, ..., p-1}
• all operations are done modulo p

• in $F_p$ the derivative of $x^k$ is given by

$$ d / dx * x^k = kx^{k-1} $$

but modulo p! This means if k >= p, k is reduced modulo p. so __if p is prime, then for any k >= p we have:

$$ \frac{d}{dx} x^p = 0\ \ mod\ p $$

2. if f' = 0, then $f = g^p$ for some $g \in P$

Now, assume f' = 0. this means that the derivative of f is zero, which implies that f must have following propperty:

$$ f(x) = \sum_ {i=0}^na_ix^i $$

and $$ f'(x) = \sum_ {i=0}^nia_ix^{i-i} $$

if we need f'(x) to be a zero, we need $ia_i = 0$ for any i. Here is an error: we dont need all $a_i$: it's applied only for i != p, cause multiplyers of p are ok and steel gives zero, cause we are in mod p

This implies that $a_i = 0$ for all i != 0 because in Fp we cant get a zero in multiplication unless one of multiplyers is zero. So the only surviving constant term is $a_0$, and the polynomial looks like $f(x) = c$, where c is const in $F_p$

Now , if $f(x) = c_p$ for some const c, then $f'(x) = 0$. Specifically, if $f(x) = c^p$, then f(x) is a power of g. Here is an error again: last sentence should be proven

3. now, we can conclude that f' = 0, then f is one of the form $g^p$ for some polynomial $g \in P = F_p$