# Python Program for Modular Multiplicative Inverse from 1 to n

In the previous article, we have discussed Python Program to Find Value of y Mod (2 raised to power x)

Given two numbers n and a prime number, the task is to find the modular multiplicative inverse from 1 to the given number n

The modular multiplicative inverse of an is an integer ‘x’ in such a way that

a x ≡ 1 (mod prime)

Examples:

Example1:

Input:

Given number = 5
Given prime number = 7

Output:

The modular multiplicative inverse from 1 to the given number{ 5 } :
1 4 5 2 3

Explanation:

For 1, modular inverse is 1 as (1 * 1)%7 is 1
For 2, modular inverse is 4 as (2 * 4)%7 is 1
For 3, modular inverse is 6 as (3 * 5)%7 is 1
..
..

Example2:

Input:

Given number = 9
Given prime number = 11

Output:

The modular multiplicative inverse from 1 to the given number{ 9 } :
1 6 4 3 9 2 8 7 5

## Program for Modular Multiplicative Inverse from 1 to n in Python

Below are the ways to find the modular multiplicative inverse from 1 to the given number n in python:

### Method #1: Using For Loop (Static Input)

Approach:

• Give the number as static input and store it in a variable.
• Give the prime number as static input and store it in another variable.
• Create a function to say modularmultInverse() which takes the iterator value and the given number as the arguments and returns the modular multiplicative inverse from 1 to the given number n.
• Inside the function, calculate the iterator value modulus given prime number and store it in the same variable iterator value.
• Loop from 1 to the given prime number using the for loop.
• Check if the iterator value multiplied by k (where k is the iterator value of for loop) modulus given prime number is equal to 1 using the if conditional statement.
• If it is true, return the value of k.
• Return -1.
• Loop from 1 to the given number using the for loop.
• Pass the iterator value and the given prime number to the modularmultInverse() function and print it.
• The Exit of the Program.

Below is the implementation:

# Create a function to say modularmultInverse() which takes the iterator value and the
# given number as the arguments and returns the modular multiplicative inverse from 1
# to the given number n.

# Inside the function, calculate the iterator value modulus given prime number and
# store it in the same variable iterator value.
# Loop from 1 to the given prime number using the for loop.
# Check if the iterator value multiplied by k (where k is the iterator value of for loop)
# modulus given prime number is equal to 1 using the if conditional statement.
if ((itrvl*k) % gvn_primenum == 1):
# If it is true, return the value of k.
return k
#Return -1.
return -1

# Give the number as static input and store it in a variable.
gvn_numb = 5
# Give the prime number as static input and store it in another variable.
# Loop from 1 to the given number using the for loop.
print(
"The modular multiplicative inverse from 1 to the given number{", gvn_numb, "} :")
for itr in range(1, gvn_numb+1):
# Pass the iterator value and the given prime number to the modularmultInverse() function
# and print it.


Output:

The modular multiplicative inverse from 1 to the given number{ 5 } :
1 4 5 2 3

### Method #2: Using For loop (User Input)

Approach:

• Give the number as user input using the int(input()) function and store it in a variable.
• Give the prime number as user input using the int(input()) function and store it in another variable.
• Create a function to say modularmultInverse() which takes the iterator value and the given number as the arguments and returns the modular multiplicative inverse from 1 to the given number n.
• Inside the function, calculate the iterator value modulus given prime number and store it in the same variable iterator value.
• Loop from 1 to the given prime number using the for loop.
• Check if the iterator value multiplied by k (where k is the iterator value of for loop) modulus given prime number is equal to 1 using the if conditional statement.
• If it is true, return the value of k.
• Return -1.
• Loop from 1 to the given number using the for loop.
• Pass the iterator value and the given prime number to the modularmultInverse() function and print it.
• The Exit of the Program.

Below is the implementation:

# Create a function to say modularmultInverse() which takes the iterator value and the
# given number as the arguments and returns the modular multiplicative inverse from 1
# to the given number n.

# Inside the function, calculate the iterator value modulus given prime number and
# store it in the same variable iterator value.
# Loop from 1 to the given prime number using the for loop.
# Check if the iterator value multiplied by k (where k is the iterator value of for loop)
# modulus given prime number is equal to 1 using the if conditional statement.
if ((itrvl*k) % gvn_primenum == 1):
# If it is true, return the value of k.
return k
#Return -1.
return -1

# Give the number as user input using the int(input()) function and store it in a variable.
gvn_numb = int(input("Enter some random number = "))
# Give the prime number as user input using the int(input()) function and
# store it in another variable.
gvn_primenum = int(input("Enter some random number = "))
# Loop from 1 to the given number using the for loop.
print(
"The modular multiplicative inverse from 1 to the given number{", gvn_numb, "} :")
for itr in range(1, gvn_numb+1):
# Pass the iterator value and the given prime number to the modularmultInverse() function
# and print it.

Enter some random number = 9
1 6 4 3 9 2 8 7 5