gcd(7, 31) | 5 => 해가 존재한다

gcd(7, 31) = 1 => 유일한 해가 존재한다

유클리드 호제법으로 나타내면 다음과 같다

31 = 4 * 7 + 3

7 = 2 * 3 + 1

이것을 일차 결합으로 나타내면 다음과 같다

1 = 7 - 2 * 3

= 7 - 2 * (31 -4 * 7)

= 9 * 7 - 2 * 31

여기서 양변에 5를 곱하면

5 = 45 * 7 - 10 *31

x = 45 가 된다

x ≡ 14 (mod 31)