잉여역수 구하기
면접 대비시간 제한1초메모리 제한512 MB
서로소인 양의 정수 a와 m이 주어질 때, a*x를 m으로 나눈 나머지가 1이 되는 가장 작은 양의 정수 x를 구한다.
문제
지민이는 대학교에서 "잉여역수 구하기"라는 강의를 듣고 있는데, 정수론을 싫어해서 수업 시간에 그냥 졸다 나왔다. 그래서 혁주에게 "오늘 숙제 뭐야?"라고 물었더니, 혁주가 "서로소인 두 자연수 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 등이 있다.