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

asdflkjhon May 08, 2017 - 11:17:23 pm UTC OMG I HAVE NO IDEA WTF IS MOD INVERSEThe question didnt explain.

It only gave a example.

Can someone explain this for me?

kobortoron May 09, 2017 - 4:08:10 am UTC Re: OMG I HAVE NO IDEA WTF IS MOD INVERSEhezeyu2007on Aug 22, 2017 - 5:38:49 pm UTC Re: OMG I HAVE NO IDEA WTF IS MOD INVERSEhello12on Aug 22, 2017 - 5:41:55 pm UTC Re: OMG I HAVE NO IDEA WTF IS MOD INVERSEhezeyu2007on Aug 22, 2017 - 5:40:15 pm UTC Re: OMG I HAVE NO IDEA WTF IS MOD INVERSEhello12on Aug 22, 2017 - 5:42:13 pm UTC Re: OMG I HAVE NO IDEA WTF IS MOD INVERSE