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~.
~m \le 100~
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
No such integer exists.