DTU-Noter/Diskret Mat/Polynomials and the Extended Euclidean Algorithm/Polynomials and the Extended Euclidean Algorithm.typ

#import("@local/dtu-template:0.5.1"):*

#show: dtu-note.with(
  course: "01017",
  course-name: "Discrete Mathematics",
  title: "Polynomials and the Extended Euclidean Algorithm",
  date: datetime(year: 2025, month: 12, day: 4),
  author: "Rasmus Rosendahl-Kaa",
  semester: "Fall 2025"
)
An example of a polynomial
$
f(x) = x^2 - 4x+3\
g(x)= 2x-3\
h(x) = 7
$
The curve on the graph is called a parabola

What we say for polynomials with real coefficients also applies to the ones with complex coefficients

#definition(title: "Polynomial of degree n")[
$
P(x)=a_0 + a_1 x + a_2 x^2 + dots + a_n x^n, quad a_n eq.not 0, a_i in RR "or" CC
$
- $a_n$ is called the leading term
- $a_0$ is called the constant term.
- $n$ is the degree
]

#definition(title: "Addition of polynomials")[
Same $P(x)$ as before
$
Q(x) = b_0 + b_1 x + dots + b_m x^m, quad m <= n\
$

$
P(x) + Q(x) = (a_0 + b_0) + (a_1 + b_1) x + dots + (a_m + b_m)x^m\ + a_(m+1)x^(m+1) + dots + a_n x^n
$
$
deg(P(x) + Q(x)) <= n "with equality if" m < n
$
]

#definition(title: "Multiplication")[
Same $P(x), Q(x)$ as before
$
P(x) dot Q(x) = a_0 dot b_0 + (a_0 b_1 + a_1 b_0) x + (a_0 b_2 + a_1 b_1 + a_2 b_0) x^2 + dots +\
a_n b_m x^(n+m)
$
$
deg(P(x) dot Q(x)) = n+m = deg(P(x)) + deg(Q(x))
$
When multiplying you basically do:
$
P(x) dot Q(x) = a_0 dot Q(x) + a_1x dot Q(x) + dots + a_n x^n Q(x)
$
]

== Divisible
#definition(title: "Divisible")[
    $M(x)$ divides $N(x)$ (we write $M(x) | N(x)$) if $N(x) = Q(x) dot M(x)$

    $Q(x)$ is some polynomial.

    We have: $deg(N) = deg(Q) + deg(M)$, so $deg(M) <= deg(N)$

    So basically, you need to find a polynomial $Q(x)$ so that $Q(x) dot M(x) = N(x)$, then $M(x)$ divides $N(x)$

    If $M(x) | N(x)$ and $N(x)|M(x)$, then they must have the same degree. And then $deg(Q)$ must have degree 0 and be a constant.

    $exists alpha in RR: N(x) = alpha dot M(x)$
]

=== Common divisor
$D(x)$ is a common divisor of $M(x), N(x)$ if $D(x) | M(x) "and" D(x) | N(x)$

=== Greatest common divisor
#definition()[
$D_1(x)$ is _a_ greatest common divisor (gcd) of $M(x), N(x)$ if and only if $D$ is a common divisor and $D_1(x)$ also satisfies:
$ (D_1(x) | M(x) and D_1(x) | N(x)) => D_1(x) | D(x) $

If $D_1(x)$ is a greatest common divisor, then $D_1(x)$ times a constant is also a greatest common divisor

Suppose $D_2(x)$ is also a $"gcd"(M(x), N(x))$, then $D_2(x) | D_1(x)$ and $D_1(x) | D_2(x)$ so $D_2 = alpha D_1$
]

#note-box()[
There can be more than one greatest common divisor
]

Given $N(x), M(x)$, find a gcd.

#note-box(title: "For integers (repetition)")[

For integers: $n, m,$ find $"gcd"(n,m)$.
==== Euclid
$ n &= q_1 dot m + r_1, quad 0 <= r_1 < r_0 = m\
r_0 &= q_2 dot r_1 + r_2\
r_1 &= q_3 dot r_2 + r_3\
dots.v\
r_(k-3)&= q_(k-1) dot r_(k-2) + r_(k-1)\
r_(k-2)&= q_k dot r_(k-1) + r_k\
r_(k-1)&= q_(k+1) dot r_(k) + 0
$
$r_k$ is the greatest common divisor.

*Why is it a divisor*

It is the divisor because looking at the last line:
$r_k$ divides $r_(k-1), r_k$

We can go a line up: $r_(k-1)$ divides $r_(k-2), r_(k-1)$, but $r_k$ must also divide them.

Can go up a line again: $r_k$ divides $r_(k-3), r_(k-2)$ up until we get $r_k$ divides $n, m$

*Why is it the greatest common divisor*

$r_k$ can be written as a linear combination of $r_(k-2) "and" r_(k-1)$ which coefficients are integers.

You can go a line up and write $r_(k-1)$ as a linear combination, which you can input into $r_k$'s linear combination. Continue until you get:\
$
r_k = A dot N + B dot M
$
]
#definition(title: "GCD for polynomials")[
    $deg(M) = m < n = deg(N)$
    $
        N(x) &= Q_1(x) dot M(x) + R_1(x), quad deg(R_1) < deg(M)\
        M(x) &= Q_2(x) dot R_1(x) + R_2(x), quad deg(R_2) < deg(R_1)\
        &dots.v\
        R_(k-2)(x)&=Q_k (x) dot R_(k-1)(x)+R_k (x), quad deg(R_k) = 0\
        R_(k-1)(x)&=Q_(k+1)(x) dot R_(k) (x)+0
    $

    $R_k (x) = A(x) dot N(x) + B(x) dot M(x)$

    $A(x), B(x)$ are some polynomials.

    $deg(R_k (x)) = deg(N(x)) - deg(M(x))$

]

#example()[
    Find the greatest common divisor of
    $
    N(x) &= x^4 + x^3 - 2x^2 + 2x - 2 "and"\
    M(x) &= x^2 + 2x -3
    $

    Divide:

    $
    underline(x^2+2x-3 |) x^4+3x^3-2x^2+2x-2 &underline(| x^2-x+3)\
    underline(x^4 + 2x^3 -3x^2) &\
    -x^3+x^2+2x-2&\
    underline(-x^3-2x^2+3x)&\
    3x^2-x-2&\
    underline(3x^2+6x-9)&\
    -7x+7
    $

    So:
    $
    N(x)=(x^2-x+3)M(x) + (-7x+7)
    $

    Now continue with the two new polynomials you found:
    $
    underline(-7x+7|) x^2+2x-3 &underline(|-1/7x-3/7)\
    underline(x^2 - x)\
    3x-3\
    underline(3x-3)\
    0
    $

    So:
    $
    M(x) = (-1/7 x - 3/7) dot (-7x+7) + 0
    $

    Now we're finished as we have 0. The greatest common divisor is $-7x+7$
    We can write:
    $
    D(x)=-7x +7 = N(x) - (x^2-x+3) dot M(x)
    $

    To find $D_1(x)$ (a divisor of $D(x)$:
    Remember: $D_1(x) = D(x) dot alpha$ where $alpha$ is a constant
    $
    D_1(x) = -x+1
    $
    #note-box()[
    Both $D(x)$ and $D_1(x)$ are greatest common divisors of $N(x), M(x)$. as $D(x) = 1 dot D(x)$ (constant here is just $1$).
    ]
]

= Roots of polynomials
For the polynomial $a x^2 + b x + c$, the roots are: $(-b plus.minus sqrt(b^2 - 4 a c))/(2 a)$

Let's assume $"gcd"(N(x), M(x)) = D(x)$ then $alpha$ is a common root of $N(x), M(x) <=> alpha$ is a root in $D(x)$

$
N(x)=D(x) dot Q_1 (x)\
M(x)=D(x) dot Q_2 (x)
$
If $alpha$ is a root in $D(x)$, then it must also be a root in $M(x)$ and $N(x)$. The reason is that we can write $N, M$ as above

$
D(x) = A(x) N(x) + B(x) M(x)
$

$alpha$ is a root of $P(x) <=> (x- alpha)| P(x)$ which means $exists Q(x): P(x) = Q(x)(x-alpha) + beta$ where $beta$ is a constant

We can find $beta$ by calculating $P(alpha)$:
$
P(alpha) = Q(alpha)(alpha-alpha) + beta\
P(alpha) = Q(alpha)(0) + beta\
P(alpha) = beta
$

$x^2 +1= (x-i) dot (x+i)$