6930번 - Mod Inverse 다국어

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$