1477397 문제와 같은 문제인 것 같습니다. 1477397번에 제가 이미 답을 썼으나, 다른 분이 중복하여 답을 하는 수고를 덜기위해 그 답변을 똑 같이 다시 쓰겠습니다.
---------------------------------------------------------------------------------답변 드리겠습니다.
문제 풀이라기 보다는 질문에서 제시한 풀이에 대한 해설이 되겠군요.
먼저 질문의 전반부는 79와 1080의 최대 공약수를 유클리드 호제법(Euclidean algorithm)을 이용하여 구한 다음에 (최대 공약수가 1이 나왔군요)
41m + 1080n = 1 (최대공약수) 라는 식에서 m, n 을 구하는 과정을 적은 것입니다.
다시 말해서
1080 = 26*41 + 14
41 = 2*14 + 13
14 = 1*13 + 1 따라서, 이 과정을 거꾸로 풀이하면 질문에서 나온 식처럼
1 = 14 - 1*13
1 = 14 - 1*(41 - 2*14)
1 = - 1*41 + 3*14
1 = - 1*41 + 3*(1080 - 26*41)
1 = - 1*41 + 3*1080 - 78*41
1 = -79*41 + 3*1080 -------------------- (1)
이러한 과정을 거쳐서 m = -79 , n = 3 이 됩니다.
--------------------------------------------------------------------------------
k mod 1080 는 "1080 으로 나눈 나머지가 k 이다"를 의미합니다.
따라서,
1 = -79*41 mod 1080 은
식(1)에서 양변을 1080으로 나눈 나머지가 같음을 나타냅니다.
또한, -79 + 1080 = 1001 이므로,
1 = 1001*41 mod 1080 이 됩니다.
그렇다면, 41과 1001은 mod 곱셈에 대해 서로 역원이 됩니다.
그러므로, 41^(-1) mod 1080 = 1001 mod 1080 으로 쓸 수 있는 것입니다.
--------------------------------------------------------------------------------
참고로, mod 가 들어가는 연산에도 덧셈과 곱셈을 정의할 수 있습니다. 어떤 수로 나눈 나머지의 덧셈과 곱셈으로 정의할 수 있기 때문입니다. 단, mod 뒤에 들어가는 수가 소수가 아닌 경우는 0 이 아닌 두 수를 곱해서 0 이 되게끔 하는 수가 존재 합니다. mod 뒤의 수가 소수인 경우는 mod 곱셈의 역원이 항상 존재하게 됩니다.
또한, 결합법칙, 교환법칙, 분배법칙도 모두 성립함을 알 수 있습니다.
대학에서 '정수론(number theory)을 배우면 배경지식에 대해 더욱 많은 것을 알 수 있습니다. 건승하시기 바랍니다.
