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
For me how did I forget there might be a multiple of outputs lol
I spent two hours head scratching before I realised that I had no output for if there was no possible modinverse. Kill me
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