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

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I dont understand what a modular inverse is.
The question didnt explain.
It only gave a example.
Can someone explain this for me?

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.