## CCC '01 J2 - Mod Inverse

View as PDF

Points: 3
Time limit: 2.0s
Memory limit: 64M

Problem type
##### Canadian Computing Competition: 2001 Stage 1, Junior #2

In many cryptographic applications the Modular Inverse is a key point. This question involves finding the modular inverse of a number.

Given , where and are integers, the modular inverse of is the unique integer , , such that the remainder upon dividing by is .

For example, , so the remainder when is divided by is , and thus is the inverse of modulo .

You are to write a program which accepts as input the two integers and , and outputs either the modular inverse , or the statement No such integer exists. if there is no such integer .

#### Sample Input 1

4
17

#### Sample Output 1

13

#### Sample Input 2

6
10

#### Sample Output 2

No such integer exists.