Modular Multiplicative Inverse

PHOTO EMBED

Sun Feb 06 2022 02:13:52 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #mathematics #gfg #geeksforgeeks #modularmultiplicativeinverse

import java.io.*;
import java.util.*;

class Solution
{
    
  public int modInverse(int a, int m)
    {
        for(int i=1; i<m; i++){
            if(a*i%m == 1)
                return i;
        }
        return -1;
    }
}

class Main {
	public static void main (String[] args) {
	    
	    //taking input using Scanner class
		Scanner sc=new Scanner(System.in);
		
		//taking testcases
		int T=sc.nextInt();
		
		while(T-->0)
		{
		    Solution  obj=new Solution ();
		    int a,m;
		      
            //taking input a and m
		    a=sc.nextInt();
		    m=sc.nextInt();
		  
            //calling function modInverse()
		    System.out.println(obj.modInverse(a,m));
		}
		
	}
}
content_copyCOPY

11. Modular Multiplicative Inverse Given two integers ‘a’ and ‘m’. The task is to find the smallest modular multiplicative inverse of ‘a’ under modulo ‘m’. Example 1: Input: a = 3 m = 11 Output: 4 Explanation: Since (4*3) mod 11 = 1, 4 is modulo inverse of 3. One might think, 15 also as a valid output as "(15*3) mod 11" is also 1, but 15 is not in ring {0, 1, 2, ... 10}, so not valid. Example 2: Input: a = 10 m = 17 Output: 12 Explanation: Since (12*10) mod 17 = 1, 12 is the modulo inverse of 10. Your Task: You don't need to read input or print anything. Your task is to complete the function modInverse() that takes a and m as input parameters and returns modular multiplicative inverse of ‘a’ under modulo ‘m’. If the modular multiplicative inverse doesn't exist return -1. Expected Time Complexity: O(m) Expected Auxilliary Space: O(1) Constraints: 1 <= a <= 10^4 1 <= m <= 10^4

https://practice.geeksforgeeks.org/problems/modular-multiplicative-inverse-1587115620/1/?track=DSASP-Mathematics&batchId=190