Unit 2 - Modular Arithmetic

on
Unit 2 - Modular Arithmetic

Topics

Modular Arithmetic, Euclidean and Extended Euclidean algorithm, Prime numbers, Fermat and Euler’s Theorem

Modular Arithmetic

  • Computation of “mod” or “modulus” or “%” operation of expressions.
  • Which is defined as the remainder after dividing one number by another.
  • a mod b = c, c is the remainder
  • Example: 10 mod 9 equals 1. Because 1 is remainder after dividing 9 by 10.

Operations

Modular Addition, Subtraction, Multiplication, Exponentiation

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m)) mod m
(a x b) mod m = ((a mod m) x (b mod m)) mod m
(a ^ b) mod m = ((a mod m) x (a mod m) ... b times) mod m

Quotient Remainder

States that for any pair of integers a and b (b is positive), there exists two unique integers q and r such that:

a = b x q + r
where 0 <= r < b

Modular Inverse

if (a x b) mod m = 1 then b is the modular inverse of a.
Given that a, m are prime i.e gcd(a,m) = 1 and 'a' in range {1, 2, 3 ... m-1}
Example : (4*3) mod 11 = 1

Modular Division

It doesn’t always exist.

(a / b) mod m is not equal to ((a mod m) / (b mod m)) mod m.
(a / b) mod m = (a x (inverse of b if exists)) mod m

Congruent

a, b and m are integers with m > 0

a ≡ b (mod m); remainder of a/m
a = mk + b
a mod m = b mod m

Properties

(Write as it is in Addition, Multiplication in Commutative, Associative, Distributive) mod m
Identities for ➕(0) , ✖️(1)
Inverse makes remainder 0

enter image description here

Euclidean Algorithm

Basic

GCD – Greatest Common Divisor = HCF - Highest Common Factor
LCM – Least Common Multiple
List all factors always.

enter image description here

  • If we subtract a smaller number from a larger one (we reduce a larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of the two, we end up with GCD.

enter image description here

  • Now instead of subtraction, if we divide the smaller number, the algorithm stops when we find the remainder 0.
gcd(a,b) = gcd(b, a mod b)
gcd(a, 0) = a

enter image description here

Extended

Make table and try it here Watch this

Table - Basic + 120, 1001
s = s1 - q.s2
t = t1 - q.t2
s1 & t1 of last becomes s, t
s*a + t*b = gcd(a,b)

Prime numbers

Prime Number : Whole numbers greater than 1 that are only divisible/have factors 1 and itself.

Semi-Prime : Numbers whose factors are only prime numbers, excluding 1 and the number itself.
🔥 Product of two primes are always semi-prime.
Example : 21 - 1, 3, 7, 21, here 7 and 3

Relatively/Co-Prime/Mutual Primes : When only common factor is 1. GCD(a, b) = 1 | LCM(a, b) = a × b

  • It doesn’t matter if a, b is either or both are composite or prime.
  • Example: 4, 15.

Euler’s Theorem

Euler’s Totient Function

Number (Count) of positive integers less than ‘n’ that are relatively prime to ‘n’

φ(n)
  • If ‘n’ is prime, then φ(n) = n-1
  • If ‘n’ = p × q is product of primes(these are numbers are called semi-prime), then φ(n) = (p-1) x (q-1).
  • Else φ(n) = n x ( 1 - 1/p1) x ( 1 - 1/p2), p1, p2 … are distinct prime factors of n.

enter image description here

Euler Theorem

  • E for Euler and E for Exponent, hence Exponent Totient.
  • For any two positive integer ‘a’ & ‘n’, which are relatively prime.
  • Example a = 3, n = 10

enter image description here

Fermat’s Theorem

  • If ‘p’ is a prime number and ‘a’ is a positive integer not divisible by ‘p’ OR ‘a’ not a multiple of P.
  • Example a = 2, p = 5

enter image description here

👁️ Structure is same, p & n differs.

Comments

Post a Comment