Scribd
Upload
12 views3 pages

Euler's Totient and Modular Inverses Guide

The document covers various concepts related to Euler's Totient Function, modular arithmetic, and the Extended Euclidean Algorithm. It includes calculations for coprimes, inverses, and GCDs, as well as examples of solving congruences and using the Chinese Remainder Theorem. Additionally, it discusses field arithmetic in GF(2^4) and finding square roots modulo composite numbers.

Uploaded by

Harshit Tripathi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views3 pages

Euler's Totient and Modular Inverses Guide

The document covers various concepts related to Euler's Totient Function, modular arithmetic, and the Extended Euclidean Algorithm. It includes calculations for coprimes, inverses, and GCDs, as well as examples of solving congruences and using the Chinese Remainder Theorem. Additionally, it discusses field arithmetic in GF(2^4) and finding square roots modulo composite numbers.

Uploaded by

Harshit Tripathi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1) Euler's Totient Function (phi):

N = 17 -> Coprimes: 1 to 16 -> phi(17) = 16 (since 17 is prime)

N = 42 -> Coprimes: numbers less than 42 and not divisible by 2, 3, 7 -> phi(42) =

42*(1-1/2)*(1-1/3)*(1-1/7) = 12

N = 25 -> phi(25) = 25*(1 - 1/5) = 20

2)

a) Additive inverse of 27 in Z_100 is 100 - 27 = 73

Multiplicative inverse: Find x such that 27x === 1 mod 100 -> x = 63 (since 27*63 = 1701 === 1

mod 100)

b) Euler Totients:

phi(101) = 100 (prime)

phi(102) = 102*(1 - 1/2)*(1 - 1/3) = 34

phi(500) = 500*(1 - 1/2)*(1 - 1/5) = 200

3) Modular inverses in Z*_9 using Euler's theorem (a^phi(n) === 1 mod n):

phi(9) = 6

1^5 === 1, 2^5 === 5, 4^5 === 7, 5^5 === 2, 7^5 === 4, 8^5 === 8 (mod 9)

4)

a) 6^5 === 6 (mod 7) -> Inverse = 6

b) GCD(7,15) = 1 -> Use Extended Euclidean Algorithm -> Inverse = 13

c) 19^99 === 64 (mod 101)

d) GCD(97,100) = 1 -> Inverse of 97 mod 100 is 97 (since 97^99 mod 100 = 1)

5)

a) x === 4100 mod 7 -> 4100 mod 7 = 2 -> x = 2


b) 9x === 13 mod 17 -> x = 3

c) 5x === 13 mod 17 -> x = 11

d) 7x === 11 mod 13 -> x = 2

6) Over GF(2^4) with irreducible polynomial x^4 + x + 1:

a) Find inverses using field arithmetic tables or polynomial division

b) Use long division in GF(2^4)

c) Similar to (b), result is a polynomial modulo f(x)

(Exact answers need field setup)

7)

a) GCD(726, 1144) = 22

b) GCD(2184, 16170) = 6

c) GCD(113, 13) = 1

8) Extended Euclidean Algorithm:

GCD(654, 123) = 3

Find u, v such that 654u + 123v = 3 -> u = -7, v = 37

9)

a) 13^-1 mod 31 = 12 (since 13*12 = 156 === 1 mod 31)

b) 111^-1 mod 4111 = 3535

10)

a) y^2 === 3 mod 143 -> Try values -> y = 25, 118

b) y^2 === 421 mod 693 -> Use Tonelli-Shanks or trial -> y = 127, 566
11) Solve using Chinese Remainder Theorem:

x === 3 mod 5

x === 1 mod 7

x === 6 mod 8

Solution: x === 103 mod 280

You might also like