Multiplicative Group, Euclid Algorithm for GCD

math
group theory
Author

Passawis

Published

October 27, 2020

Multiplicative Group

220mod15

G15={1,2,4,7,8,11,13,14}

this is the multiplicative group of mod 15

We can guarantee that 28=1mod15

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

220=228+4=116=1mod15

220mod17

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

We can guarantee that 216=1mod17

220=216+4=116=16mod17

Coprime

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

Gm={a|1a<m(gcd(a,m)=1)}

the statement above forms the group of multiplication modulo m

Euclidean Algorithm

gcd(m,a)m=q0a+r1a=q1r1+r2r1=q2r2+r3r2=q3r3+r4

Example

Finding the GCD(90,32)

90=232+2632=126+626=46+26=32+0

m=2a+r1a=1r1+r2r1=4r2+r36=3r3+0

Therefore:

gcd(90,32)=r3=2

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

m=2a+r1a=1r1+r2r1=4r2+r36=3r3+0

Now do back substitution:

r1=m2ar2=ar1r3=r14r2

r3=m2a4(ar1)=m2a4a+4r1=m6a+4(m2a)=m6a+4m8a=5m14a

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

(1)ay=1(modm)

The main idea:

Construct k1 and k2 to get a linear combination of the form:

1=gcd(m,a)=k1a+k2m

Then:

k1a=1k2m

which provides:

ak1=1(modm)

Since k1 is a good candidate for y in (1),
we adjust y modulo m as follows:

y=k1(modm)

Then we conclude:

ay=ak1=1(modm)

Concrete Examples

y=a1(modm) Find y

y=131(mod34)

13y=1(mod34)

First, we find gcd(34,13):

34=213+813=18+58=15+35=13+23=12+12=21+0

Thus:

gcd(34,13)=1

Find GCD linear combination

Express all remainders recursively:

r1=m2ar2=ar1r3=r1r2r4=r2r3r5=r3r4

Now compute

1=r5=r3r4=r3(r2r3)=2r3r2=2r3(ar1)=2r3(a(m2a))=2r3(am+2a)=2r3(m+3a)=2(r1r2)(m+3a)=2((m2a)(a(m2a)))(m+3a)=2((m2a)(am+2a))(m+3a)=2((2m5a))(m+3a)=4m10a+m3a=5m13a

Check:

5341313=1

r1=13r2=5

gcd(34,13)=1=k1a+k2m

Now compute y

y=k1(modm)=(13)(mod34)=21(since 13+34=21)

Thus:

ay=ak1(modm)

Also:

ak1=(1k2m)=1(modm)

Check:

ay=1321=273=834+1=1(mod34)

Hence:

y=21


ax=b (mod m) Find x

ax=b (mod m)

13x=6(mod34)

From the previous question

131=21(mod34)(from previous question)

Now compute x

x=216(mod34)=1263×34=24(mod34)

Check:

126mod34=6


an(mod m) Find result

21024(mod15)

We know that:

28=1(mod15)

Thus:

28128=21024=1(mod15)


xa=b(mod m) Find x

x3=2(mod11)

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

φ(11)=10

3y=1(mod10)

10=33+13=31+0

Now write:

m=3a+r1r1=m3a

Thus:

k1=3(mod10)=7

Now check:

37=21=1(modφ(11))

Now compute x:

x=by=27=128=7(mod11)

Check that gcd(2,11)=1:

11=52+1

73=497=57=35=2(mod11)