### 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)

It's quiet in here...