CCC '01 J2 - Mod Inverse

View as PDF
Submit solution
Points: 3
Time limit: 2.0s
Memory limit: 256M
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 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 \times n by m is 1.

For example, 4 \times 13 = 52 = 17 \times 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.

Constraints

m \le 100

Sample Input 1

4
17

Sample Output 1

13

Sample Input 2

6
10

Sample Output 2

No such integer exists.

Comments


  • 0
    20220680  commented on Sept. 12, 2022, 10:37 a.m.

    For me how did I forget there might be a multiple of outputs lol


  • 28
    Subway_Man  commented on Nov. 15, 2019, 1:08 a.m.

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


  • -4
    harry7557558  commented on Oct. 19, 2019, 7:35 p.m.

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