MA5.101 - Discrete Structures | DS Lecture 31

with Prof. Ashok Kumar Das
Nov 28, 2020 - Saturday
Written by: Abhinav S Menon

Greatest Common Divisor

Definition

The greatest common divisor, or gcd, of two numbers $a$ and $b$ is the only number $d$ such that

  1. $d|a$ and $d|b$, and

  2. $c|a$ and $c|b \Rightarrow d|c$.

Note that:
gcd$(a,0) = a$
gcd$(0,0)$ is not defined
gcd$(a,b) =$ gcd$(-a,b) =$ gcd$(a,-b) =$ gcd$(-a,-b) =$ gcd$(|a|,|b|)$

Euclid’s Algorithm

For any two integers $a$ and $b$, we carry out the following series of computations to find gcd$(a,b)$:

$$a = r_0, b = r_1$$ $$r_0 = q_1r_1 + r_2, 0 \leq r_2 < r_1$$ $$r_1 = q_2r_2 + r_3, 0 \leq r_3 < r_2$$ $$r_2 = q_3r_3 + r_4, 0 \leq r_4 < r_3$$ $$\vdots$$ $$r_{k-2} = q_{k-1}r_{k-1} + r_k, 0 \leq r_k < r_{k-1}$$ $$r_{k-1} = q_kr_k + 0$$

Since the $r_i$ form a strictly decreasing sequence, the algorithm must eventually stop. It can be proved that gcd$(a,b) =$ gcd$(b,r_1) =$ gcd$(r_1,r_2) = \cdots =$ gcd$(r_{k-1},r_k) = r_k$.

The pseudocode for Euclid’s algorithm is as follows:
gcd$(a,b)$

  1. $A = a$, $B = b$
  2. if $(B == 0)$ then return A
  3. $R = A$ mod $B$
  4. $A = B$, $B = R$
  5. return gcd$(A,B)$

The number of steps $n$ required to complete Euclid’s algorithm in this form is less than $\lfloor{3}$ln(min{$a,b$})$\rfloor$.

If $d =$ gcd$(a,b)$, then there exists integers $s$ and $t$ (called the multipliers of $a$ and $b$ respectively) such that $as + bt = d$.

Euclid’s Extended Algorithm

As a corollary of the last statement in the previous section, if gcd$(a,b) = 1$, then $s$ and $t$ are such that $as + bt = 1$. Therefore, $as = 1$ (mod $b$), i.e., $s$ is the multiplicative inverse of $a$ in the group $Z_b$. If $b$ is prime, then $s$ is the multiplicative inverse of $a$ in the field $GF(b)$.

Euler’s extended algorithm yields the multiplicative inverse of $a$ mod $b$. To describe it, we first rearrange the equations in Euclid’s algorithm:

$$r_0 = a, r_1 = b$$ $$r_2 = r_0 - q_1r_1, 0 \leq r_2 < b$$ $$r_3 = r_1 - q_2r_2, 0 \leq r_3 < r_2$$ $$r_4 = r_2 - q_3r_3, 0 \leq r_4 < r_3$$ $$\vdots$$ $$r_{k} = r_{k-2} - q_{k-1}r_{k-1}, 0 \leq r_k < r_{k-1}$$

Hence, for all $i \geq 1$, we can see that the relation $r_{i+1} = r_{i-1} - q_ir_i$ holds. We will augment the equations with the sequences $s_i$ and $t_i$ as follows:

$$r_0 = a, r_1 = b; s_0 = 1, s_1 = 0; t_0 = 0, t_1 = 1$$ $$r_{i+1} = r_{i-1} - q_ir_i$$ $$s_{i+1} = s_{i-1} - q_is_i$$ $$t_{i+1} = t_{i-1} - q_it_i$$

We claim that $s_i$ and $t_i$ are such that $r_i = as_i + bt_i$. This can be proved inductively:
Base. $as_0 + bt_0 = a \cdot 1 + b \cdot 0 = a = r_0$ and $as_1 + bt_1 = a \cdot 0 + b \cdot 1 = b = r_1$.
Inductive Step. Suppose that $r_i = as_i + bt_i$ holds for all $i < k$. Now,

$$r_{k} = r_{k-2} - q_{k-1}r_{k-1} = (as_{k-2} + bt{k-2}) - q_{k-1}(as_{k-1} + bt_{k-1})$$ $$ = a(s_{k-2} -q_{k-1}s_{k-1}) + b(t_{k-2} - q_{k-1}t_{k-1}) = as_k + bt_k$$

Hence, if $r_k =$ gcd$(a,b)$, then $s_k$ is the multiplicative inverse of $a$ mod $b$.

The pseudocode for Euclid’s extended algorithm is as follows:

inverse$(a,b)$

  1. $A_1 = 1, A_2 = 0, A_3 = b$ and $B_1 = 0, B_2 = 1, B_3 = a$
  2. if $(B_3 == 0)$ then return error
  3. if $(B_3 == 1)$ then return $B_2$
  4. $Q = \lfloor\frac{A_3}{B_3}\rfloor$
  5. $R_1 = A_1 - QB_1, R_2 = A_2 - QB_2, R_3 = A_3 - QB_3$
  6. $A_1 = B_1, A_2 = B_2, A_3 = B_3$
  7. $B_1 = R_1, B_2 = R_2, B_3 = R_3$
  8. return inverse($A_3,B_3$)

At the end, $B_3 =$ gcd$(a,b)$, and $aB_2 + bA_2 = 1$.

Polynomials over Rings

Definition

A polynomial $f(x)$ over a ring $R$ is defined as a formal expression of the form $f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$, where $a_i \in R$, $i = 0, 1, … , n$, and $a_n \neq 0$.
The highest exponent of $x$ is called the degree of $f(x)$, denoted as deg $f = n$. $x$ is called the indeterminate of $f$.
The set of all polynomials over $R$ also forms a ring, under the operations of R and following the laws of exponents for $x$. This ring is called the polynomial ring over $R$, and is denoted by $R[X]$ (if $x$ is the indeterminate).

Irreducibility

A polynomial $f$ of degree $> 0$ over a field $K$ is said to be irreducible iff there do not exist polynomials $g, h \in K[X]$ such that deg $g > 0$, deg $h > 0$, and $f(x) = g(x) \cdot h(x)$.
Two equivalent statements of the above definition are:

  1. $f$ is irreducible if it cannot be factored into non-trivial polynomials over $K$ (the trivial factors of $f$ are 1 and $f$).
  2. $f$ is irreducible iff there does not exists a polynomial $d \in K[X]$ such that $0 <$ deg $d <$ deg $f$, and $d(x)|f(x)$.