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

In the previous article, we have discussed Python Program to Find Square Root Under Modulo k (When k is in Form of 4*i + 3)<\/a><\/p>\n

Given two integers and the task is to find the modular multiplicative inverse of \u2018first number\u2019 under modulo \u2018second number\u2019.<\/p>\n

The modular multiplicative inverse is an integer \u2018x\u2019 such that<\/p>\n

first number x \u2261 1 (mod second number)<\/p>\n

The value of x should be in the range 0 to 1, 2,…second number-1, i.e. in the integer modulo second number ring.<\/p>\n

If and only if the first number and second number are relatively prime (i.e., if gcd( first number, second number) = 1), the multiplicative inverse of “first number modulo second number” exists.<\/p>\n

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

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

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

Given First Number = 10\r\nGiven Second Number = 17<\/pre>\n

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

The modular multiplicative inverse of given first number under modulo second number =  12<\/pre>\n

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

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

Given First Number = 4\r\nGiven Second Number = 9<\/pre>\n

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

The modular multiplicative inverse of given first number under modulo second number =  7<\/pre>\n

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

Below are the ways to find the modular multiplicative inverse of \u2018first number\u2019 under modulo \u2018second number’ in python.<\/p>\n