What is modular arithmetic?
Modular arithmetic is a system of arithmetic for integers, whose values reset to zero and begin to increase again, after reaching a certain predefined value, called the modulus (modulo). Modular arithmetic is widely used in computer science and cryptography.
where:
- N is a positive integer.
Modular linear equations
Example
Euclid’s algorithm
The gcd algorithms are explained in terms of the Euclid elements. It is written as a recursive algorithm or program based on a and b (positive integers). However, the inputs b and a are non-negative integers.
EUCLID-ALG (a, b)
- if b = 0
- then return a
- else return EUCLID-ALG (b, a mod b)
Example
The running of EUCLID-ALG will consider the calculation of gcd (30, 21)
EUCLID-ALG (30, 21)
= EUCLID-ALG (21, 9)
= EUCLID-ALG (9, 3)
= EUCLID-ALG (3, 0)
= 3
This computation has three different recursive invocations of EUCLID-ALG. The fact that when the EUCLID-ALG algorithm returns a at line 2, then b with 0, whereas, gcd (a, b) = gcd (a, 0) = a. The algorithm cannot recurse indefinitely and the second argument gets decreased in all recursive calls. Therefore, EUCLID -ALG always ends with the exact answer.
Solving modular linear equations
Consider the following problem and find the solution to the given equation,
To solve the equation the following algorithm is used to print the solutions to the given equation. The inputs both n and a are arbitrary positive integers, whereas, b will be an arbitrary integer.
Algorithm
MODULARLINEAREQUATIONSOLVE (a, b, n)
- (d, x′, y′) EXTENDED-EUCLIDALG(a, n)
- if d | b
- then
- for
- do print
- else print "no solutions"
Consider the following examples
Example 1
where b = 30, n = 100, and a = 14. By calling EXTENDED_EUCLIDALG at line 1, then the user can simply obtain (d, x, y) = (2, -7, 1). However, 2 | 30, then the line 3 to 5 are executed. At the line 3, calculate . The loop at line 4 to 5 prints the two different solutions such as 45 and 95.
From Theorem 1, the equation has a solution if and only if gcd (a, n) | b. The solution to the equation is unique if and only if gcd (a, n) = 1.
Example 2: Solve 3x ≡ 5 (mod 6), Note that gcd (3, 6) = 3 and 3 - 5. Thus this equation has no solution.
The procedure of MODULARLINEAREQUATIONSOLVE works as follows,
Line 1 computes the value of d as gcd(a, n) and also other two values like such that while demonstrating, the equation . If d cannot divide b, then will not have any solution. Line 2 verifies if d | b; if not, then line 6 will report that there are no solutions. Otherwise, line 3 calculates the solution . The other d - 1 solution can be obtained by just adding many . The for loop in lines 4 to 5 prints all solutions related to d, beginning with
MODULARLINEAREQUATIONSOLVE performs the arithmetic operations O(lg n + gcd (a, n)) since EXTENDED-EUCLIDALG performs the arithmetic operations O(lg n), and each iteration of the for loop at lines 4 to 5 performs a constant number of arithmetic operations.
Pseudocode for solving modular linear equation
Void solvemodlinear (int m, int n, int k)
{
index I;
int j, I, d;
Euclid (n, m, d, I, j);
If (d | k)
{
For (w = 0; w <= d-1; w++ )
{
Cout<<
}
}
}
In the above solvemodlinear method, an index I along with other integers are declared. The method Euclid (n, m, d, I, j) is called. When the if codition is true then it will execute the for loop to print the value of , when the value of w is less than d-1, then for loop will be terminated.
Time complexity analysis
The running time of the Euclidean algorithm is estimated by Lame's theorem, which establishes a surprising connection between the Euclidean algorithm and the Fibonacci sequence:
If for some n, the Euclidean algorithm performs at most n−2n−2 recursive calls.
Moreover, it is possible to show that the upper bound of this theorem is optimal. When a = Fna = Fn and b = Fn − 1b = Fn − 1, gcd(a,b) will perform exactly n−2n−2 recursive calls. In other words, consecutive Fibonacci numbers are the worst-case input for Euclid's algorithm.
Given that Fibonacci numbers grow exponentially, we get that the Euclidean algorithm works in O(log min(a,b)).
Context and Applications
This topic is important for postgraduate and undergraduate courses, particularly for,
- Bachelors in computer science engineering.
- Masters in computer science.
Practice problems
Question 1: For any n > 1 if gcd( a, n ) =1 then the equation ax ≡ 1 mod n will have
a) No solution
b) Unique solution
c) Same solution
d) None of the above
Answer: Option b is correct.
Explanation: For any n > 1 if gcd( a, n ) =1 then the equation ax ≡ 1 mod n has exactly one unique
solution.
Question 2: What is the time complexity to perform the modular exponentiation of
a) O(m +a)
b) O(gm)
c) O(g)
d) O(ag)
Answer: Option c is correct.
Explanation: The modular exponentiation is based on the operating system environment and its performance. The given method requires a time complexity of O(g) for its completion, where g is a primitive root modulo.
Question 3: How many solutions are there for the equation 35 x ≡ 10 (mod 50).
a) 5
b) 4
c) 3
d) 8
Answer: Option a is correct.
Explanation: When a = 35, b = 10 and n = 50. We know gcd(35, 50) = 5. Thus there are 5 solutions
to the given equation. Since 3 x 35 + (-2) x 50 = 5 we have x' = 3. Thus x0 = x' ( b / d ) mod n = 3 x (10/5) mod 50 = Other solutions are .
Question 4: A modular linear arithmetic group can hold _______property.
a) Closure
b) Identity
c) Associativity
d) All the above
Answer: Option d is correct.
Explanation: A group is a set S together with a binary operation, defined on S for which
holds Inverses, Associativity, Closure, and Identity properties.
Question 5: For any n > 1, if gcd( a, n ) =1 then the equation ax ≡ b mod n, has how many solutions?
a) 2
b) 3
c) 6
d) 1
Answer: Option d is correct.
Explanation: For any n > 1 if gcd( a, n ) =1 then the equation ax ≡ b mod n has exactly one
solution.
Want more help with your computer science homework?
*Response times may vary by subject and question complexity. Median response time is 34 minutes for paid subscribers and may be longer for promotional offers.
Search. Solve. Succeed!
Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.
Search. Solve. Succeed!
Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.