State fermat’s little theorem (FLT) and Euler’s theorem. Illustrate with an example how FLT can be used to find modular inverse.

Mumbai university > Electronics and telecommunication Engineering > Sem 7 > Data compression and Encryption

Marks: 4

Years: May 2016

Fermat’s theorem:

It states that if p is a prime no. and a is a positive integer not divisible by p then

ap-1 = I mod p

If p is a prime no. and n is a positive integer not divisible by p then according to the modular arithmetic the set of numbers {0 mod p, a mod p, 2a mod p,…., (p-1)a mod p} is identical to set {0, 1, 2, …., p-1}

Since 0 mod p = 0, the first element of two sets are equal.

Now, multiplying the remaining elements of two sets and taking modulus, we get

[(1a mod p)(2a mod p)….((p-1)a mod p)]

Using product rule on RHS

ap-1 (p-1) 1 mod p = (p-1) 1 mod p

Cancelling (p-1) 1 on both sides

ap-1 mod p = 1 mod p

or

ap-1 ≡ 1 mod p

Euler’s theorem:

It states that for every a and n that are relatively prime

aϕ(n) ≡ 1 mod n

e.g. a = 3, n = 10, ϕ(n) = 4

34 = 1 mod 10

81 = 1 mod 10