Modular multiplicative inverse
Modular multiplicative inverse is a fundamental concept in number theory and modular arithmetic. Given two positive integers a and m, the modular multiplicative inverse of a modulo m is an integer x such that:
a * x ≡ 1 (mod m)
In other words, x is the inverse of a modulo m, and the product of a and x (mod m) is equal to 1. This means that x is the number which when multiplied by a and reduced modulo m, gives the remainder of 1.
The modular multiplicative inverse of a modulo m exists only when a and m are relatively prime (i.e., they have no common factors other than 1). In such cases, the modular multiplicative inverse can be found using the Extended Euclidean Algorithm, which is a recursive algorithm for finding the greatest common divisor (GCD) of two numbers and their corresponding Bezout coefficients.
The modular multiplicative inverse of a modulo m can be used to solve various problems in number theory and cryptography, including RSA encryption, Chinese remainder theorem, and primality testing.
Here given code implementation process.
// C Program
// Modular multiplicative inverse
#include <stdio.h>
// This function find the inverse of a (a^-1) under m
void invert_modulo(int a, int m)
{
int num = a % m;
//Loop controlling variable
int i = 1;
//result variable
int result = -1;
//Display given data information
printf("\n Number [a] : %d", a);
printf("\n Modular [m] : %d", m);
while (i < m && result == -1)
{
if ((num * i) % m == 1)
{
//When get result
result = i;
}
i++;
}
if (result == -1)
{
//When result are not possible
printf("\n Inverse are not found\n");
}
else
{
printf("\n Result %d\n", result);
}
}
int main()
{
printf("\n Test Modular multiplicative inverse\n");
//Test function
invert_modulo(7, 34);
invert_modulo(9, 28);
invert_modulo(28, 9);
return 0;
}
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
// Java program
// Modular multiplicative inverse
class ModularInverse
{
// This function find the inverse of a (a^-1) under m
public void invert_modulo(int a, int m)
{
int num = a % m;
//Loop controlling variable
int i = 1;
//result variable
int result = -1;
//Display given data information
System.out.print("\n Number [a] : " + a);
System.out.print("\n Modular [m] : " + m);
while (i < m && result == -1)
{
if ((num * i) % m == 1)
{
//When get result
result = i;
}
i++;
}
if (result == -1)
{
//When result are not possible
System.out.print("\n Inverse are not found\n");
}
else
{
System.out.print("\n Result " + result + "\n");
}
}
public static void main(String[] args)
{
ModularInverse obj = new ModularInverse();
System.out.print("\n Test Modular multiplicative inverse\n");
// Test Case
obj.invert_modulo(7, 34);
obj.invert_modulo(9, 28);
obj.invert_modulo(28, 9);
}
}
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
//Include header file
#include <iostream>
using namespace std;
// C++ program
// Modular multiplicative inverse
class ModularInverse
{
public:
// This function find the inverse of a (a^-1) under m
void invert_modulo(int a, int m)
{
int num = a % m;
//Loop controlling variable
int i = 1;
//result variable
int result = -1;
//Display given data information
cout << "\n Number [a] : " << a;
cout << "\n Modular [m] : " << m;
while (i < m && result == -1)
{
if ((num * i) % m == 1)
{
//When get result
result = i;
}
i++;
}
if (result == -1)
{
//When result are not possible
cout << "\n Inverse are not found\n";
}
else
{
cout << "\n Result " << result << "\n";
}
}
};
int main()
{
ModularInverse obj = ModularInverse();
cout << "\n Test Modular multiplicative inverse\n";
// Test Case
obj.invert_modulo(7, 34);
obj.invert_modulo(9, 28);
obj.invert_modulo(28, 9);
return 0;
}
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
//Include namespace system
using System;
// C# program
// Modular multiplicative inverse
class ModularInverse
{
// This function find the inverse of a (a^-1) under m
public void invert_modulo(int a, int m)
{
int num = a % m;
//Loop controlling variable
int i = 1;
//result variable
int result = -1;
//Display given data information
Console.Write("\n Number [a] : " + a);
Console.Write("\n Modular [m] : " + m);
while (i < m && result == -1)
{
if ((num * i) % m == 1)
{
//When get result
result = i;
}
i++;
}
if (result == -1)
{
//When result are not possible
Console.Write("\n Inverse are not found\n");
}
else
{
Console.Write("\n Result " + result + "\n");
}
}
public static void Main(String[] args)
{
ModularInverse obj = new ModularInverse();
Console.Write("\n Test Modular multiplicative inverse\n");
// Test Case
obj.invert_modulo(7, 34);
obj.invert_modulo(9, 28);
obj.invert_modulo(28, 9);
}
}
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
<?php
// Php program
// Modular multiplicative inverse
class ModularInverse
{
// This function find the inverse of a (a^-1) under m
public function invert_modulo($a, $m)
{
$num = $a % $m;
//Loop controlling variable
$i = 1;
//result variable
$result = -1;
//Display given data information
echo "\n Number [a] : ". $a;
echo "\n Modular [m] : ". $m;
while ($i < $m && $result == -1)
{
if (($num * $i) % $m == 1)
{
//When get result
$result = $i;
}
$i++;
}
if ($result == -1)
{
//When result are not possible
echo "\n Inverse are not found\n";
}
else
{
echo "\n Result ". $result ."\n";
}
}
}
function main()
{
$obj = new ModularInverse();
echo "\n Test Modular multiplicative inverse\n";
// Test Case
$obj->invert_modulo(7, 34);
$obj->invert_modulo(9, 28);
$obj->invert_modulo(28, 9);
}
main();
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
// Node Js program
// Modular multiplicative inverse
class ModularInverse
{
// This function find the inverse of a (a^-1) under m
invert_modulo(a, m)
{
var num = a % m;
//Loop controlling variable
var i = 1;
//result variable
var result = -1;
//Display given data information
process.stdout.write("\n Number [a] : " + a);
process.stdout.write("\n Modular [m] : " + m);
while (i < m && result == -1)
{
if ((num * i) % m == 1)
{
//When get result
result = i;
}
i++;
}
if (result == -1)
{
//When result are not possible
process.stdout.write("\n Inverse are not found\n");
}
else
{
process.stdout.write("\n Result " + result + "\n");
}
}
}
function main()
{
var obj = new ModularInverse();
process.stdout.write("\n Test Modular multiplicative inverse\n");
// Test Case
obj.invert_modulo(7, 34);
obj.invert_modulo(9, 28);
obj.invert_modulo(28, 9);
}
main();
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
# Python 3 program
# Modular multiplicative inverse
class ModularInverse :
# This function find the inverse of a (a^-1) under m
def invert_modulo(self, a, m) :
num = a % m
# Loop controlling variable
i = 1
# result variable
result = -1
# Display given data information
print("\n Number [a] : ", a, end = "")
print("\n Modular [m] : ", m, end = "")
while (i < m and result == -1) :
if ((num * i) % m == 1) :
# When get result
result = i
i += 1
if (result == -1) :
# When result are not possible
print("\n Inverse are not found\n", end = "")
else :
print("\n Result ", result ,"\n", end = "")
def main() :
obj = ModularInverse()
print("\n Test Modular multiplicative inverse\n", end = "")
# Test Case
obj.invert_modulo(7, 34)
obj.invert_modulo(9, 28)
obj.invert_modulo(28, 9)
if __name__ == "__main__": main()
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
# Ruby program
# Modular multiplicative inverse
class ModularInverse
# This function find the inverse of a (a^-1) under m
def invert_modulo(a, m)
num = a % m
# Loop controlling variable
i = 1
# result variable
result = -1
# Display given data information
print("\n Number [a] : ", a)
print("\n Modular [m] : ", m)
while (i < m && result == -1)
if ((num * i) % m == 1)
# When get result
result = i
end
i += 1
end
if (result == -1)
# When result are not possible
print("\n Inverse are not found\n")
else
print("\n Result ", result ,"\n")
end
end
end
def main()
obj = ModularInverse.new()
print("\n Test Modular multiplicative inverse\n")
# Test Case
obj.invert_modulo(7, 34)
obj.invert_modulo(9, 28)
obj.invert_modulo(28, 9)
end
main()
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
// Scala program
// Modular multiplicative inverse
class ModularInverse
{
// This function find the inverse of a (a^-1) under m
def invert_modulo(a: Int, m: Int): Unit = {
var num: Int = a % m;
//Loop controlling variable
var i: Int = 1;
//result variable
var result: Int = -1;
//Display given data information
print("\n Number [a] : " + a);
print("\n Modular [m] : " + m);
while (i < m && result == -1)
{
if ((num * i) % m == 1)
{
//When get result
result = i;
}
i += 1;
}
if (result == -1)
{
//When result are not possible
print("\n Inverse are not found\n");
}
else
{
print("\n Result " + result + "\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: ModularInverse = new ModularInverse();
print("\n Test Modular multiplicative inverse\n");
// Test Case
obj.invert_modulo(7, 34);
obj.invert_modulo(9, 28);
obj.invert_modulo(28, 9);
}
}
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
// Swift program
// Modular multiplicative inverse
class ModularInverse
{
// This function find the inverse of a (a^-1) under m
func invert_modulo(_ a: Int, _ m: Int)
{
let num: Int = a % m;
//Loop controlling variable
var i: Int = 1;
//result variable
var result: Int = -1;
//Display given data information
print("\n Number [a] : ", a, terminator: "");
print("\n Modular [m] : ", m, terminator: "");
while (i < m && result == -1)
{
if ((num * i) % m == 1)
{
//When get result
result = i;
}
i += 1;
}
if (result == -1)
{
//When result are not possible
print("\n Inverse are not found\n", terminator: "");
}
else
{
print("\n Result ", result ,"\n", terminator: "");
}
}
}
func main()
{
let obj: ModularInverse = ModularInverse();
print("\n Test Modular multiplicative inverse\n", terminator: "");
// Test Case
obj.invert_modulo(7, 34);
obj.invert_modulo(9, 28);
obj.invert_modulo(28, 9);
}
main();
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
fn main()
{
print!("\n Test Modular multiplicative inverse\n");
//Test function
invert_modulo(7, 34);
invert_modulo(9, 28);
invert_modulo(28, 9);
}
fn invert_modulo(a: i32, m: i32)
{
let num: i32 = a % m;
//Loop controlling variable
let mut i: i32 = 1;
//result variable
let mut result: i32 = -1;
//Display given data information
print!("\n Number [a] : {}", a);
print!("\n Modular [m] : {}", m);
while i < m && result == -1
{
if (num * i) % m == 1
{
//When get result
result = i;
}
i += 1;
}
if result == -1
{
//When result are not possible
print!("\n Inverse are not found\n");
}
else
{
print!("\n Result {}\n", result);
}
}
Output
Test Modular multiplicative inverse
Number [a] : 7
Modular [m] : 34
Result 5
Number [a] : 9
Modular [m] : 28
Result 25
Number [a] : 28
Modular [m] : 9
Result 1
This C program finds the modular multiplicative inverse of a given number 'a' with respect to a given modulus 'm'. The modular multiplicative inverse of a number 'a' is another number 'b' such that their product is congruent to 1 modulo m, i.e., (a * b) ≡ 1 (mod m). If 'b' exists, then 'a' is said to be invertible modulo 'm'.
The program defines a function called 'invert_modulo' that takes two integer arguments 'a' and 'm'. Inside the function, it first calculates the residue of 'a' modulo 'm' using the modulus operator '%'. Then, it initializes a loop controlling variable 'i' to 1 and a result variable 'result' to -1. The loop runs from 1 to 'm' (exclusive) and checks if the product of 'num' and 'i' modulo 'm' is equal to 1. If it is, then it sets the 'result' variable to 'i' and breaks out of the loop. If the loop completes without finding a suitable 'i', then the 'result' variable remains as -1, indicating that the modular inverse does not exist. Finally, the function prints the given values of 'a' and 'm' and the computed modular inverse value (if it exists) using printf statements.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment