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:

Using For Loop (Static Input)
Using For loop (User Input)

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.


def modularmultInverse(itrvl, gvn_primenum):
  # Inside the function, calculate the iterator value modulus given prime number and
  # store it in the same variable iterator value.
    itrvl = itrvl % gvn_primenum
    # Loop from 1 to the given prime number using the for loop.
    for k in range(1, gvn_primenum):
     # 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.
gvn_primenum = 7
# 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.
    print(modularmultInverse(itr, gvn_primenum), end=" ")

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.


def modularmultInverse(itrvl, gvn_primenum):
  # Inside the function, calculate the iterator value modulus given prime number and
  # store it in the same variable iterator value.
    itrvl = itrvl % gvn_primenum
    # Loop from 1 to the given prime number using the for loop.
    for k in range(1, gvn_primenum):
     # 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.
    print(modularmultInverse(itr, gvn_primenum), end=" ")

Output:

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

If you are learning Python then the Python Programming Example is for you and gives you a thorough description of concepts for beginners, experienced programmers.