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

#### Constraints

#### Sample Input 1

```
4
17
```

#### Sample Output 1

`13`

#### Sample Input 2

```
6
10
```

#### Sample Output 2

`No such integer exists.`

## Comments

Is this a looping problem?

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

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.

Your solution runs in time though

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

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

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

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

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.