Question

Q1. Using Euclideanalgorithm find GCD(21, 1500). Show you work

.Q2. Using Extended Euclidean algorithm find the multiplicative inverse of 8 in mod 45 domain .Show your work including the table.

Q3. Determine φ(2200). (Note that 1,2,3,5, 7, ... etc.are the primes). Show your work.

Q4. Find the multiplicative inverse of 14 in GF(31) domain using Fermat’s little theorem. Show your work

Q5. Using Euler’s theorem to find the following exponential: 4200mod 27. Show how you have employed Euler’s theorem here

Answer 1

1)

Set up a division problem where a is larger than b.
a ÷ b = c with remainder R. Do the division. Then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.

1500 ÷ 21 = 71 R 9    (1500 = 71 × 21 + 9)

21 ÷ 9 = 2 R 3    (21 = 2 × 9 + 3)

9 ÷ 3 = 3 R 0    (9 = 3 × 3 + 0)

When remainder R = 0, the GCF is the divisor, b, in the last equation. GCF = 3

2)

a	b	q	r	s1	s2	s3	t1	t2	t3
8	45	0	8	1	0	1	0	1	0
45	8	5	5	0	1	-5	1	0	1
8	5	1	3	1	-5	6	0	1	-1
5	3	1	2	-5	6	-11	1	-1	2
3	2	1	1	6	-11	17	-1	2	-3
2	1	2	0	-11	17	-45	2	-3	8

So we found the following:

• gcd(8, 45) = 1
• s = 17
• t=-3

Verification
s × a + t × b = 17 × 8 + -3 × 45 = 1
This is equal to the gcd we calculated.

3)

2200=2^3 x 5^2 x 11^1

Phi(2200)=(2^3-2^2)*(5^2-5^1)*(11-1)

=4*20*10=800