Multiplicative Group, Euclid Algorithm for GCD

math

group theory

Author

Passawis

Published

October 27, 2020

Multiplicative Group

$2^{20} m o d 15$

$G 15 = {1, 2, 4, 7, 8, 11, 13, 14}$

this is the multiplicative group of mod 15

We can guarantee that $2^{8} = 1 m o d 15$

we can guarantee this because the $| G 15 | = 8$ , so powering 8 will return to the same position in G15

$2^{20} = 2^{2 * 8 + 4} = 1 * 16 = 1 m o d 15$

$2^{20} m o d 17$

$G 17 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16$

We can guarantee that $2^{16} = 1 m o d 17$

$2^{20} = 2^{16 + 4} = 1 * 16 = 16 m o d 17$

Coprime

a and m are coprime iff gcd(a,m) = 1

$G m = {a | 1 \leq a < m \land (g c d (a, m) = 1)}$

the statement above forms the group of multiplication modulo m

Euclidean Algorithm

$\begin{array}{r} g c d (m, a) \\ m = q 0 * a + r 1 \\ a = q 1 * r 1 + r 2 \\ r 1 = q 2 * r 2 + r 3 \\ r 2 = q 3 * r 3 + r 4 \end{array}$

Example

Finding the $G C D (90, 32)$

$\begin{aligned} 90 & = 2 \cdot 32 + 26 \\ 32 & = 1 \cdot 26 + 6 \\ 26 & = 4 \cdot 6 + 2 \\ 6 & = 3 \cdot 2 + 0 \end{aligned}$

$\begin{aligned} m & = 2 \cdot a + r_{1} \\ a & = 1 \cdot r_{1} + r_{2} \\ r_{1} & = 4 \cdot r_{2} + r_{3} \\ 6 & = 3 \cdot r_{3} + 0 \end{aligned}$

Therefore:

$gcd (90, 32) = r_{3} = 2$

From this we can get a linear combination, by substituting in the variable at each step.

$\begin{aligned} m & = 2 \cdot a + r_{1} \\ a & = 1 \cdot r_{1} + r_{2} \\ r_{1} & = 4 \cdot r_{2} + r_{3} \\ 6 & = 3 \cdot r_{3} + 0 \end{aligned}$

Now do back substitution:

$\begin{aligned} r_{1} & = m - 2 a \\ r_{2} & = a - r_{1} \\ r_{3} & = r_{1} - 4 r_{2} \end{aligned}$

$\begin{aligned} r_{3} & = m - 2 a - 4 (a - r_{1}) \\ = m - 2 a - 4 a + 4 r_{1} \\ = m - 6 a + 4 (m - 2 a) \\ = m - 6 a + 4 m - 8 a \\ = 5 m - 14 a \end{aligned}$

Computing inverse y = $a^{- 1} m o d m$ (when GCD(m,a) = 1)

$\begin{matrix} (1) & a * y = 1 (\mod m) \end{matrix}$

The main idea:

Construct $k_{1}$ and $k_{2}$ to get a linear combination of the form:

$1 = gcd (m, a) = k_{1} a + k_{2} m$

Then:

$k_{1} a = 1 - k_{2} m$

which provides:

$a * k_{1} = 1 (\mod m)$

Since $k_{1}$ is a good candidate for $y$ in (1),
we adjust $y$ modulo $m$ as follows:

$y = k_{1} (\mod m)$

Then we conclude:

$a * y = a * k_{1} = 1 (\mod m)$

Concrete Examples

$y = a^{- 1} (\mod m)$ Find y

$y = 13^{- 1} (\mod 34)$

$13 * y = 1 (\mod 34)$

First, we find $gcd (34, 13)$ :

$\begin{aligned} 34 & = 2 \cdot 13 + 8 \\ 13 & = 1 \cdot 8 + 5 \\ 8 & = 1 \cdot 5 + 3 \\ 5 & = 1 \cdot 3 + 2 \\ 3 & = 1 \cdot 2 + 1 \\ 2 & = 2 \cdot 1 + 0 \end{aligned}$

Thus:

$gcd (34, 13) = 1$

Find GCD linear combination

Express all remainders recursively:

$\begin{aligned} r_{1} & = m - 2 a \\ r_{2} & = a - r_{1} \\ r_{3} & = r_{1} - r_{2} \\ r_{4} & = r_{2} - r_{3} \\ r_{5} & = r_{3} - r_{4} \end{aligned}$

Now compute

$\begin{aligned} 1 & = r_{5} = r_{3} - r_{4} = r_{3} - (r_{2} - r_{3}) \\ = 2 r_{3} - r_{2} \\ = 2 r_{3} - (a - r_{1}) \\ = 2 r_{3} - (a - (m - 2 a)) \\ = 2 r_{3} - (a - m + 2 a) \\ = 2 r_{3} - (- m + 3 a) \\ = 2 (r_{1} - r_{2}) - (- m + 3 a) \\ = 2 ((m - 2 a) - (a - (m - 2 a))) - (- m + 3 a) \\ = 2 ((m - 2 a) - (a - m + 2 a)) - (- m + 3 a) \\ = 2 ((2 m - 5 a)) - (- m + 3 a) \\ = 4 m - 10 a + m - 3 a \\ = 5 m - 13 a \end{aligned}$

Check:

$5 \cdot 34 - 13 \cdot 13 = 1$

$r_{1} = - 13 r_{2} = 5$

$gcd (34, 13) = 1 = k_{1} a + k_{2} m$

Now compute $y$

$y = k_{1} (\mod m) = (- 13) (\mod 34) = 21 (since - 13 + 34 = 21)$

Thus:

$a * y = a * k_{1} (\mod m)$

Also:

$a * k_{1} = (1 - k_{2} m) = 1 (\mod m)$

Check:

$a * y = 13 \cdot 21 = 273 = 8 \cdot 34 + 1 = 1 (\mod 34)$

Hence:

$y = 21$

$a * x = b (\mod m)$ Find x

$a * x = b (\mod m)$

$13 * x = 6 (\mod 34)$

From the previous question

$13^{- 1} = 21 (\mod 34) (from previous question)$

Now compute $x$

$x = 21 * 6 (\mod 34) = 126 - 3 \times 34 = 24 (\mod 34)$

Check:

$126 mod 34 = 6$

$a^{n} (\mod m)$ Find result

$2^{1024} (\mod 15)$

We know that:

$2^{8} = 1 (\mod 15)$

Thus:

$2^{8 \cdot 128} = 2^{1024} = 1 (\mod 15)$

$x^{a} = b (\mod m)$ Find x

$x^{3} = 2 (\mod 11)$

Check that $gcd (a, φ (m)) = 1$ :

$φ (11) = 10$

$3 * y = 1 (\mod 10)$

$10 = 3 \cdot 3 + 1 3 = 3 \cdot 1 + 0$

Now write:

$m = 3 a + r_{1} r_{1} = m - 3 a$

Thus:

$k_{1} = - 3 (\mod 10) = 7$

Now check:

$3 * 7 = 21 = 1 (\mod φ (11))$

Now compute $x$ :

$x = b^{y} = 2^{7} = 128 = 7 (\mod 11)$

Check that $gcd (2, 11) = 1$ :

$11 = 5 \cdot 2 + 1$

$7^{3} = 49 * 7 = 5 * 7 = 35 = 2 (\mod 11)$

Multiplicative Group

Coprime

Euclidean Algorithm

Example

Computing inverse y = a−1mod m (when GCD(m,a) = 1)

The main idea:

Concrete Examples

y=a−1(modm) Find y

Find GCD linear combination

a∗x=b (mod m) Find x

an(mod m) Find result

xa=b(mod m) Find x

Computing inverse y = $a^{- 1} m o d m$ (when GCD(m,a) = 1)

$y = a^{- 1} (\mod m)$ Find y

$a * x = b (\mod m)$ Find x

$a^{n} (\mod m)$ Find result

$x^{a} = b (\mod m)$ Find x