Modular Division

 


Modular Division

Modular division is a mathematical operation that involves dividing two integers under a specified modulus. It’s particularly useful in number theory, cryptography, and computer science. The goal is to find the remainder of the division (modulo) of one number by another.

Definition

Given three positive integers: a,b, and m, we want to compute a/b under modulo m. In other words, we seek to find a number c such that:

(b⋅c)modm=amodm

When Is Modular Division Defined?
1.Inverse Existence:
  • Modular division is defined when the inverse of the divisor exists.
  • The inverse of an integer x is another integer y such that (x⋅y)modm=1, where m is the modulus.
  • In other words, x and m must be co-prime (i.e., their greatest common divisor is 1).

2.Finding the Inverse:

  • To compute modular division, we need to find the modular multiplicative inverse of b under modulus m.
  • If the inverse doesn’t exist (i.e., GCD(b, m) is not 1), then modular division is not defined.

How to Find Modular Division?

Check for Inverse Existence:
First, check if the inverse of  b under modulus m exists.
If the inverse doesn’t exist (i.e., GCD(b, m) is not 1), then print “Division not defined.”

Compute the Result:
If the inverse exists, compute the result as: 
Result of division=(inverse⋅a)modm

Example:
Let a=8,b=3 and m=5. Compute (83mod5)

Inverse Existence:
The GCD of 3 and 5 is 1, so the inverse exists.

Compute the Result:
The inverse of 3 under modulo 5 is 2 (since (3⋅2mod5=1)).
The result of division is (8⋅2)mod5=1.

Therefore, the solution is 83≡1mod5

Remember that modular division behaves differently from ordinary division
Note: Inverse can be computed easily by using the Extended Euclid Algorithm

Example: University Question
Solve the congruence 17x≡3(mod29)

x=17−1.3(mod29)
x=12.3(mod29)
x=36(mod29)
x=7

Python Code 
from sympy import mod_inverse
print(mod_inverse(17,29))
12

Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func...
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form x21+x22+⋯+x2k, where each xi∈Z, for a given k. Definition: For each integer k≥1, let Sk={n|n=x21+x22+⋯+x2k for some x1,x2,…,xk∈Z} , the set of all sum of k squares. Example: S1={0,1,4,9,…} is the set of all squares. By inspection S2, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set S2 contains, the sum of two squares is closed under multiplication ie; if s,t∈S2 , then st∈S2. Proof:Let s=a21+b21 and t=a22+b22 be the elements of S2, where a1,b1,a2,b2∈Z. Then the identity (a21+b21)(a22+b22)=(a1a2−b1b2)2+(a1b2+b1a2)2 This shows that st∈S2 Example: We have 8=22+22 and 10=32+12 so 8.10=80=(2.3−2.1)2+(2.1+2.3)2=42+82 Note: an equivalent ident...
Read more

Well Ordering Principle

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which x precedes y if and only if  y is either x or the sum of x and some positive integer (other orderings include the ordering 2,4,6; and 1,3,5). The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem". On other occasions it is understood to be the proposition that the set of integers {…,−2,−1,0,1,2,3,…} contains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element. Well-ordering Principle: If S is a non-empty set of non-negative integers, then S has a least element, i.e., there is an integer c∈S such that c≤x for all x∈S. The principle of mathematical induction follows direct...
Read more