CCC '01 J2 - Mod Inverse

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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


  • -3
    Renegades  commented on April 2, 2020, 9:32 a.m.

    Is this a looping problem?


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


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


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

      Your solution runs in O(\sqrt M) time though


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


    • 5
      Aaeria  commented on Oct. 27, 2019, 11:11 p.m.

      Yes, see the problem https://dmoj.ca/problem/modinv


    • -7
      hxxr  commented on Oct. 19, 2019, 5:41 p.m.

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


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


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