{"id":20747,"date":"2021-09-21T09:00:18","date_gmt":"2021-09-21T03:30:18","guid":{"rendered":"https:\/\/python-programs.com\/?p=20747"},"modified":"2021-11-22T18:36:16","modified_gmt":"2021-11-22T13:06:16","slug":"python-program-for-modular-multiplicative-inverse-from-1-to-n","status":"publish","type":"post","link":"https:\/\/python-programs.com\/python-program-for-modular-multiplicative-inverse-from-1-to-n\/","title":{"rendered":"Python Program for Modular Multiplicative Inverse from 1 to n"},"content":{"rendered":"

In the previous article, we have discussed Python Program to Find Value of y Mod (2 raised to power x)<\/a><\/p>\n

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

The modular multiplicative inverse of an is an integer \u2018x’ in such a way that<\/p>\n

a x \u2261 1 (mod prime)<\/p>\n

Examples:<\/strong><\/p>\n

Example1:<\/strong><\/p>\n

Input:<\/strong><\/p>\n

Given number = 5\r\nGiven prime number = 7<\/pre>\n

Output:<\/strong><\/p>\n

The modular multiplicative inverse from 1 to the given number{ 5 } :\r\n1 4 5 2 3<\/pre>\n

Explanation:<\/strong><\/p>\n

For 1, modular inverse is 1 as (1 * 1)%7 is 1\r\nFor 2, modular inverse is 4 as (2 * 4)%7 is 1\r\nFor 3, modular inverse is 6 as (3 * 5)%7 is 1\r\n..\r\n..<\/pre>\n

Example2:<\/strong><\/p>\n

Input:<\/strong><\/p>\n

Given number = 9\r\nGiven prime number = 11<\/pre>\n

Output:<\/strong><\/p>\n

The modular multiplicative inverse from 1 to the given number{ 9 } :\r\n1 6 4 3 9 2 8 7 5<\/pre>\n

Program for Modular Multiplicative Inverse from 1 to n in Python<\/h2>\n

Below are the ways to find the modular multiplicative inverse from 1 to the given number n in python:<\/p>\n