{"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 Output:<\/strong><\/p>\n Explanation:<\/strong><\/p>\n Example2:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\n Below are the ways to find the modular multiplicative inverse from 1 to the given number n in python:<\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n If you are learning Python then the Python Programming Example<\/a> is for you and gives you a thorough description of concepts for beginners, experienced programmers.<\/p>\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 \u2018x’ in …<\/p>\nGiven number = 5\r\nGiven prime number = 7<\/pre>\n
The modular multiplicative inverse from 1 to the given number{ 5 } :\r\n1 4 5 2 3<\/pre>\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
Given number = 9\r\nGiven prime number = 11<\/pre>\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
\n
Method #1: Using For Loop (Static Input)<\/h3>\n
\n
# Create a function to say modularmultInverse() which takes the iterator value and the\r\n# given number as the arguments and returns the modular multiplicative inverse from 1\r\n# to the given number n.\r\n\r\n\r\ndef modularmultInverse(itrvl, gvn_primenum):\r\n # Inside the function, calculate the iterator value modulus given prime number and\r\n # store it in the same variable iterator value.\r\n itrvl = itrvl % gvn_primenum\r\n # Loop from 1 to the given prime number using the for loop.\r\n for k in range(1, gvn_primenum):\r\n # Check if the iterator value multiplied by k (where k is the iterator value of for loop)\r\n # modulus given prime number is equal to 1 using the if conditional statement.\r\n if ((itrvl*k) % gvn_primenum == 1):\r\n # If it is true, return the value of k.\r\n return k\r\n #Return -1.\r\n return -1\r\n\r\n\r\n# Give the number as static input and store it in a variable.\r\ngvn_numb = 5\r\n# Give the prime number as static input and store it in another variable.\r\ngvn_primenum = 7\r\n# Loop from 1 to the given number using the for loop.\r\nprint(\r\n \"The modular multiplicative inverse from 1 to the given number{\", gvn_numb, \"} :\")\r\nfor itr in range(1, gvn_numb+1):\r\n # Pass the iterator value and the given prime number to the\u00a0modularmultInverse() function\r\n # and print it.\r\n print(modularmultInverse(itr, gvn_primenum), end=\" \")\r\n<\/pre>\n
The modular multiplicative inverse from 1 to the given number{ 5 } :\r\n1 4 5 2 3<\/pre>\n
Method #2: Using For loop (User Input)<\/h3>\n
\n
# Create a function to say modularmultInverse() which takes the iterator value and the\r\n# given number as the arguments and returns the modular multiplicative inverse from 1\r\n# to the given number n.\r\n\r\n\r\ndef modularmultInverse(itrvl, gvn_primenum):\r\n # Inside the function, calculate the iterator value modulus given prime number and\r\n # store it in the same variable iterator value.\r\n itrvl = itrvl % gvn_primenum\r\n # Loop from 1 to the given prime number using the for loop.\r\n for k in range(1, gvn_primenum):\r\n # Check if the iterator value multiplied by k (where k is the iterator value of for loop)\r\n # modulus given prime number is equal to 1 using the if conditional statement.\r\n if ((itrvl*k) % gvn_primenum == 1):\r\n # If it is true, return the value of k.\r\n return k\r\n #Return -1.\r\n return -1\r\n \r\n \r\n# Give the number as user input using the int(input()) function and store it in a variable.\r\ngvn_numb = int(input(\"Enter some random number = \"))\r\n# Give the prime number as user input using the int(input()) function and \r\n# store it in another variable.\r\ngvn_primenum = int(input(\"Enter some random number = \"))\r\n# Loop from 1 to the given number using the for loop.\r\nprint(\r\n \"The modular multiplicative inverse from 1 to the given number{\", gvn_numb, \"} :\")\r\nfor itr in range(1, gvn_numb+1):\r\n # Pass the iterator value and the given prime number to the\u00a0modularmultInverse() function\r\n # and print it.\r\n print(modularmultInverse(itr, gvn_primenum), end=\" \")\r\n<\/pre>\n
Enter some random number = 9\r\nEnter some random number = 11\r\nThe modular multiplicative inverse from 1 to the given number{ 9 } :\r\n1 6 4 3 9 2 8 7 5<\/pre>\n
\n