Multiplicative Group, Euclid Algorithm for GCD
Multiplicative Group
this is the multiplicative group of mod 15
We can guarantee that
we can guarantee this because the
We can guarantee that
Coprime
a and m are coprime iff gcd(a,m) = 1
the statement above forms the group of multiplication modulo m
Euclidean Algorithm
Example
Finding the
Therefore:
From this we can get a linear combination, by substituting in the variable at each step.
Now do back substitution:
Computing inverse y = (when GCD(m,a) = 1)
The main idea:
Construct
Then:
which provides:
Since
we adjust
Then we conclude:
Concrete Examples
Find y
First, we find
Thus:
Find GCD linear combination
Express all remainders recursively:
Now compute
Check:
Now compute
Thus:
Also:
Check:
Hence:
Find x
From the previous question
Now compute
Check:
Find result
We know that:
Thus:
Find x
Check that
Now write:
Thus:
Now check:
Now compute
Check that