CCC '01 J2 - Mod Inverse

View as PDF

Submit solution

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


  • -6
    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.


  • 2
    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.