15995번 - 잉여역수 구하기

문제

지민이는 대학교에서 "잉여역수 구하기"라는 강의를 듣고 있는데, 지민이는 정수론을 싫어해서 수업 시간에 그냥 졸다 나왔다. 그래서 혁주에게 "오늘 숙제 뭐야?"라고 물었더니, 혁주가 "서로소인 두 자연수 a와 m의 값이 주어지면 a의 법 m에 대한 잉여역수 a*를 구하는 거야."라고 말했다. 지민이는 수업을 듣지 않아서 잉여역수의 정의를 모른다. 지민이의 숙제를 우리가 대신해 주자.

입력

첫째 줄에 서로소인 두 자연수 a와 m이 사이에 공백을 두고 주어진다. (2 ≤ a, m ≤ 10,000)

출력

첫째 줄에 a의 법 m에 대한 잉여역수 a*를 출력한다. 단, 잉여역수는 무한히 많기 때문에 그 중 자연수이며, 최소인 값을 출력하도록 한다.

제한

힌트

a의 법 m에 대한 잉여역수 a*의 정의는 다음과 같다. (a와 m이 서로소일 때)

정수 x에 대한 합동방정식 ax≡1 (mod m)이 성립할 때, x를 a의 법 m에 대한 잉여역수라고 하며, a*와 같이 표기한다. 예를 들어 법 4에 대한 3의 잉여역수는 3, 7, 11, 15 등이 있다.