모듈러 역원 Modular Inverse

모듈러 연산

모듈러 연산은 어떤 수 $a$를 $0$ 아닌 수 $b$로 나누었을 때의 나머지를 구하는 연산이다.

 

예를 들어 $17\;mod\;5=2$이며

 

모듈러 연산에서는 동치 표현을 $\equiv$로 표시한다.

 

$7\equiv 2\;mod\;5$로 표현할 수 있다.

 

모듈러 연산은 프로그래밍에서 $%$ 기호로 표시된다.

 

모듈러 덧셈 역원

모듈러 덧셈 역원이란 어떤 수 $a$와 $b$에 대해 $(a+b)mod\;N=0$을 만족하는 쌍을 의미한다.

 

$n=5$일 때 $2$의 덧셈 역원은 $5k+3$으로 나타낼 수 있다.

 

모듈러 곱셈 역원 

모듈러 곱셈 역원이란 어떤 수 $a$에 대해 $a\cdot a^{-1}\;mod\;N=1$로 표현할 수 있으며

 

곱셈 역원을 $a^{-1}$로 표현한다.

 

곱셈 역원은 덧셈 역원과는 다르게 없을 수도 있다.

 

곱셈 역원 구하기

배경 지식

 

먼저 곱셈 역원의 식을 보게 되면

 

$ax=kN+1$ 형태인데 정리하면 베주항등식과 매우 유사하다는 사실을 알 수 있다.

 

$ax-kN=1$

 

$ax+Ny=1$

 

베주 항등식의 성질에 의해 정수해 $(x,y)$를 구하려면 $a$와 $N$이 서로소여야 구할 수 있다.

 

정수해 $(x,y)$는 확장 유클리드 알고리즘에 의해 구할 수 있으며

 

코드는 다음과 같다. 

 

p.s. 페르마의 소정리에 의해 $a^{-1}\equiv a^{N-2}\;\;mod\;N$ 이다.

 

이때 $N$은 소수이다.

 

백준 14565 역원\(Inverse\) 구하기

 

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

pair<ll,pair<ll,ll>> xGCD(ll a, ll b){
    if(b==0) return {a,{1,0}};
    pair<ll,pair<ll,ll>> ret=xGCD(b,a%b);
    ll g,x,y;
    g=ret.first;
    tie(x,y)=ret.second;
    return {g,{y,x-(a/b)*y}};
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll a,n;
    cin >> n >> a;
    cout << n-a << ' ';
    auto p=xGCD(a,n);
    if(p.first==1){
        ll ans=p.second.first;
        if(ans<0) ans+=(-ans/n+1)*n;
        cout << ans;
    }
    else cout << -1;
    return 0;
}