곱셈의 역원

나머지 연산

modular를 씌울 때 사칙연산 중 다음이 성립합니다.

• 더하기 : 성립함
• 빼기 : 성립함
• 곱하기 : 성립함
• 나누기 : 성립하지 않음

나눗셈이 성립하기 위해서는 곱셈의 역원을 구해서 곱해줘야 합니다.

---

정의

어떤 정수 a가 주어질 때,
a * x % N == 1인 정수 x를 찾는 문제

+) a와 N이 서로소 일 때만 x가 존재

 

example)

N = 11, a = 3 일 때

=> 곱셈의 역원 x = 4

3 * 4 % 11 = 1

---

풀이

1) 반복문

1부터 N-1까지 반복문으로 찾아본다

O(N)

#include <cstdio>

int inverseMul(int N, int a) {
	for (int i = 1; i < N; ++i) {
		if (a * i % N == 1) return i;
	}

	return -1;
}

int main()
{
	int N = 11, a = 3;
	printf("%d\n", inverseMul(N, a)); // 4
}

 

2) 확장 유클리드 알고리즘

https://kdr06006.tistory.com/22

확장 유클리드 알고리즘

 

ax % N == 1을 만족하는 x를 찾아야 함

위의 식은 (ax + Ny) % N == 1 역시 만족함

=> Ny + ax = 1의 정수해 (x, y)를 찾아서 x값을 반환해주면 됨

 

+) a와 N이 서로소가 아니어도 코드 상으로 답을 도출해내긴 함

• 유클리드 알고리즘으로 미리 gcd(N, a) != 1 인 경우를 제외시키거나
• ax % N == 1이 나오는지 직접 x에 값을 대입해 확인해주면 된다

확장 유클리드 알고리즘의 시간 복잡도와 동일

O(max(log N, log a))

#include <cstdio>

struct Pii {
	int A, B;

	Pii operator-(Pii O) {
		return { A - O.A, B - O.B };
	}

	Pii operator*(int m) {
		return { m * A, m * B };
	}
};

int Mod(int x, int N) {
	x %= N;
	return x > 0 ? x : (x + N) % N;
}

int inverseMul(int N, int a) {
	// ax = 1 + Ny
	// => Ny + ax = 1

	Pii number = { N, a };
	Pii old_s = { 1, 0 };
	Pii new_s = { 0, 1 };

	while (number.B) {
		int q = number.A / number.B;
		int r = number.A % number.B;

		number = { number.B, r };

		Pii tmp = new_s;
		new_s = old_s - new_s * q;
		old_s = tmp;
	}

	return Mod(old_s.B, N);
}

int main()
{
	int N = 11, a = 3;
	int ans = inverseMul(N, a);
	printf("%d\n", ans * a % N == 1 ? ans : -1); // 4
}

---

참조

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

나머지 연산의 곱셈 역원