2001 Canadian Computing Competition, Stage 1
Problem J2: Mod Inverse
In many cryptographic applications the Modular Inverse is a key operation. This question involves finding the modular inverse of a number.
Given 0 < x < m, where x and m are integers, the modular inverse of x is the unique integer n, 0 < n < m, such that the remainder upon dividing x × n by m is 1.
For example, 4 x 13 = 52 = 17 x 3 + 1, so the remainder when 52 is divided by 17 is 1, and thus 13 is the inverse of 4 modulo 17.
You are to write a program which accepts as input the two integers x and m, and outputs either the modular inverse n, or the statement "No such integer exists." if there is no such integer n.
You may assume that m ≤ 100.
Sample Input 1
4
17
Sample Output 1
13
Sample Input 2
6
10
Sample Output 2
No such integer exists.
All Submissions
Best Solutions
Point Value: 3
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 27, 2008
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
The question didnt explain.
It only gave a example.
Can someone explain this for me?