Mod Inverse When Coprime
Hard
Computer Mathematics
GCD/LCM & Euclid
32 views
Problem Statement
Given a and m, print inverse of a mod m, or -1 if not exists.
Input Format
Two integers a m.
Output Format
One integer inverse or -1.
Example
3 11
4
Constraints
m>1
Input / Output Format
Input Format
Two integers a m.
Output Format
One integer inverse or -1.
Constraints
m>1
Examples
Input:
3 11
Output:
4
Example Solution (Public)
Compute (g,x,_) from extended Euclid for (a,m). If g!=1 output -1 else inverse=(x%m+m)%m.
Official Solution Code
Compute (g,x,_) from extended Euclid for (a,m). If g!=1 output -1 else inverse=(x%m+m)%m.
Please login to submit solutions.