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

## Comments

• Subway_Man  commented on Nov. 14, 2019, 8:08 p.m.

I spent two hours head scratching before I realised that I had no output for if there was no possible modinverse. Kill me

• leonzalion  commented on Oct. 19, 2019, 9:23 p.m.

The modular inverse exists only when x and m are coprime. If it exists, the modular inverse is equal to x^(φ(m)-1) % m where φ is Euler's totient function (you can view my submission as an example). The low constraints on this problem make this implementation overkill, however.

• discoverMe  commented on Oct. 19, 2019, 11:41 p.m.

Your solution runs in time though

• harry7557558  commented on Oct. 19, 2019, 3:35 p.m.

I have heard an algorithm to find the mod inverse of a large integer in logarithm time.

• Hecan  commented on July 31, 2018, 9:34 p.m. edit 2

This comment is hidden due to too much negative feedback. Click here to view it.

• m4m3sh1b4  commented on Sept. 25, 2017, 11:36 p.m.

I don't get this problem, is it supposed to say + instead of x? -> such that the remainder upon dividing x×n by m is 11.