[일반] 나머지 연산 곱셈 역원 질문

[익명(124.57)]

https://www.acmicpc.net/blog/view/29

(p*q) 합동 1 (mod m)

일 때 

q를 p (mod m)의 역원 이라고 하는걸로 알고있는데, 단 p,q는 정수

즉, 5는 3 (mod 7)의 역원 인데

이걸 가지고 어떻게 유리수의 나머지 연산을 구한다는 것인가요...?

다른 포스트도 많이 읽어봤는 데 (a * b^-1) % m을 구할려고 할 때

a (mod m)의 역원을 구한다고 하는데 이걸 왜 구하는지 모르겠습니다.

[익명(58.143)]

유리수의 나머지를 구하는게 아니고 곱셈같은경우는 p*q의 나머지를 구한다하면 (p의 나머지)*(q의 나머지)의 나머지로 쉽게 계산할수 있는데 나눗셈은(나누어 떨어질때만) p/q의 나머지를 구할때 (p의 나머지)/(q의 나머지)로 하면 안되니깐 곱셈꼴로 바꿔주고자 (p의 나머지)*(q의 역원)으로 계산하기 위해서 역원을 구하는거임

[익명(124.57)]

정말 정말 감사합나다. oo님

[karasuta(songj722)]

a/b를 할 때 a에다가 b의 역원을 곱해 줘서 나누기를 대신하는 겁니다. (1/b)×b=1 이고, (b의 역원)×b=1 이니까 b의 역원이 1/b를 대신할 수 있는 것이죠

[익명(124.57)]

정말 정말 감사합니다. karasuta님

[redbin0471(wjdals0471)]

AB^-1 에다가 Bx 를 곱하면 Ax 가됨 즉 AB^-1 랑 Ax 나머지 에 대해서 합동임

[익명(124.57)]

정말 정말 감사합니다. redbin0471님