잇창명 개발 블로그

1,000,000,007로 그냥 나눠도 괜찮나요?

• 댓글 달기 문제해결 정수론 추상대수학

이 글의 초안을 검토해 주신 하스켈 학교의 다믜님, Absta님, Ceramif님께 감사드립니다.

백준 온라인 저지에서 분수 계산을 하는 문제를 보면 다음과 같은 출력을 요구하는 문제가 많습니다.

각 \(i\)번째 줄에 \(u_i\)에 대한 결과 값을 기약분수 \(P/Q\)로 표현했을 때, \(Q\)의 \(10^9+7\)에 대한 곱셈 역원 \(Q^{-1}\)에 대해 \(P \times Q^{-1}\)을 \(10^9+7\)로 나눈 나머지를 출력한다. (23313번 "K-계산기")

다각형 넓이의 최댓값이 \(\displaystyle \frac{p}{q}\)(\(p\)와 \(q\)는 서로소인 자연수)일 때, \(q\cdot v\equiv p (\bmod 1\,000\,000\,007\))이 되는 \(0\)이상 \(1\,000\,000\,006\) 이하의 정수 \(v\)를 출력한다. (24892번 "이차 함수")

\(\int_{t_1}^{t_2}f(t)dt\)의 값이 정수 \(m\), 양의 정수 \(n\)에 대하여 기약분수 \(\frac{m}{n}\)일 때, \(m\times n^{-1}\bmod (10^9+7)\)을 출력한다. \(n^{-1}\)은 \(n\)의 모듈러 곱셈에 대한 역원이다. (26519번 "함수와 최소 스패닝 트리")

고인물들은 문장에 담긴 비밀의 힘이 \(0\)이 될 확률 \(p_M / q_M\)에 대해 채팅방의 비밀번호를 \(p_M \times q_M^{-1} \pmod{10^9 + 7}\)로 설정하였다. 채팅방의 비밀번호는 한 번 설정하면 변경할 수 없으며, \(q_M^{-1}\)은 \(q_M\)의 모듈러 곱셈에 대한 역원이고, \(p_M \times q_M^{-1} \pmod{10^9 + 7}\)의 값은 주어진 제약 조건 내에서 유일하게 존재함을 증명할 수 있다. (28093번 "비밀의 채팅방")

Formally, it can be shown that the answer can be represented as a fraction \(p / q\) for some coprime non-negative integers \(p\) and \(q\). You have to print the value \(p \cdot q^{-1} \bmod (10^9 + 7)\). (23144번 "Reasonable Workplace Relationship")

위의 다섯 문제에서 요구하는 것을 요약하면 다음과 같습니다.

문제의 정답은 기약분수 \(\frac{a}{b}\)로 나타낼 수 있다. \(b\)의 모듈로 곱셈의 역원 \(b^{-1}\)에 대해 \(ab^{-1} \bmod (10^9 + 7)\)을 출력하여라.

제가 이런 요구사항을 처음 맞닥뜨렸을 때는 "정수를 출력하라고 하는데 왜 \(q^{-1}\)이 있는 거지?"라는 생각부터 들었습니다. \(q^{-1} = \frac{1}{q}\)는 적어도 유리수에나 취할 수 있는 연산이라는 고정관념이 있었던 시절이었는데, 그 이후 13172번 "Σ"의 지문을 읽고 나서 이 방식을 어느 정도 수긍할 수 있게 되었습니다.

위의 문제 지문을 읽고 나서도 개인적으로 여전히 이해가 되지 않는 점들이 있었는데, 마침 이게 주제로 떠올랐고 검색해도 잘 나오지 않으니 블로그 글로 써보려고 합니다.

"역원"이라는 단어를 남용하는 거 아닌가요?

저도 처음에는 그렇게 생각했는데, 아닙니다.

그동안 이 블로그에서 대수적 구조를 이미 여러 번 언급했었는데, 소수 \(p\)에 대해 모듈로 \(p\) 정수의 집합 \(\mathbb{Z}/p\mathbb{Z}\)1도 역시 대수적 구조를 이룹니다. 이번에는 그냥 군도 그냥 환도 아닌 체입니다.

체는 유리수나 실수 따위의 사칙연산 전부를 일반화한 대수적 구조라고 볼 수 있는데, 다음 두 이항 연산이 다음 성질을 만족하면 됩니다.

뺄셈은 \(a - b = a \oplus -b\)로, 나눗셈은 \(\frac{a}{b} = a \otimes b^{-1}\)로 나타낼 수 있습니다. 사칙연산에 대해 학교에서 배운 웬만한 성질이 전부 공리로 들어가 있는 만큼 다른 대수적 구조에 비해 공리의 개수도 많습니다. 여기서부터는 글 작성의 편의를 위해 \(\oplus\), \(\otimes\) 대신 흔히 사용하는 사칙연산 기호를 사용하겠습니다.

또 한 가지 중요한 것은, \(p\)가 소수이기만 해도 \(\mathbb{Z}/p\mathbb{Z}\)가 체가 되는 데는 충분하다는 것입니다. 즉, 1,000,000,007뿐만 아니라 원하는 아무 소수 \(p\)를 정하고 "\(ab^{-1} \bmod p\)를 출력하여라"라고 해도 문제가 되지 않습니다. 물론 1,000,000,007이 유독 자주 쓰이는 이유가 있긴 합니다.

얘기가 조금 삼천포로 빠지긴 했는데, 지금까지 이 블로그에서 온갖 이상한 대상의 "항등원"과 "역원"을 아무렇지 않게 논했으면서 다른 것도 아니고 체를 이루는 \(\mathbb{Z}/p\mathbb{Z}\)의 곱셈의 역원만 "단어의 남용"이라면서 거부하는 것은 앞뒤가 맞지 않는다고 생각합니다. 모듈로 곱셈의 역원도 엄연한 곱셈의 역원입니다.

페르마의 소정리를 그렇게 비틀어도 되나요?

모듈로 곱셈의 역원을 구할 때는 보통 베주 보조정리를 응용해 확장 유클리드 호제법으로 구하거나, 페르마의 소정리를 응용해 분할 정복을 이용한 거듭제곱 등의 모듈로 거듭제곱으로 구합니다. 이 중 후자의 논리는 다음과 같습니다.

페르마의 소정리에 의해 \(a^p \equiv a \pmod{p}\)니까 양변을 \(a^2\)로 나누면 \(a^{p - 2} \equiv a^{-1} \pmod{p}\) 아니냐?

\(\mathbb{Z}/p\mathbb{Z}\)가 체인(즉, \(a^2\)로 나누는 게 문제가 없는) 것을 아는 지금은 이 논법을 자연스럽게 받아들일 수 있지만, 모듈로 곱셈의 역원이라는 개념을 처음 받아들일 때는 그렇지 못했습니다. 일단 체라는 개념을 무시하고 생각하더라도 가장 작은 소수는 2이므로 일단 \(a^{p - 2}\)가 말이 된다는 것은 수긍하겠는데2 \(a^2\)를 곱해서 \(a\)가 되는 원소가 유일하게 존재한다는 건 어떻게 아나요?

이 글을 쓰기 위해서 조사해본 결과 모듈로 곱셈의 역원의 존재성과 유일성을 페르마의 소정리로 직접 증명하는 게 아니라, 보통 위에서 언급했던 베주 보조정리를 이용해 증명하는 것 같습니다. 베주 보조정리의 내용은 다음과 같습니다.

임의의 정수 \(a\)와 \(b\)에 대해...

  1. 어떤 정수의 쌍 \(x\)와 \(y\)가 존재해서 \(ax + by = \gcd(a, b)\)이다.
  2. 또한, 임의의 정수 \(x\)와 \(y\)에 대해 \(ax + by\) 꼴로 나타낼 수 있는 수는 항상 \(\gcd(a, b)\)의 배수이다.

글 태그로 #정수론을 추가하기는 했는데, 저는 정수론에 정말 약하기 때문에 글에 증명을 싣지 않고 넘어가겠습니다. 혹시 증명이 궁금하시다면 영문 위키백과에서 확인할 수 있습니다.

위의 두 정리 중 1번에 \(0 < a < b = p\)라는 조건을 걸면 \(\gcd(a, p) = 1\)이 됩니다(\(a\)와 \(p\)가 서로소이므로). 이제 \(ax + py = 1\)의 양변에 \(\bmod p\)를 하면 \(ax \equiv 1 \pmod{p}\)가 되고, \(x\)가 곱셈의 역원이 됩니다.

일단 곱셈의 역원의 존재성을 증명했다면 유일성은 체의 다른 공리를 이용해 증명할 수 있습니다. 구체적으로 \(b\)와 \(c\)가 모두 \(a\)의 역원이라면,

\[\begin{align} b &= b \cdot 1 \\ &= b(ac) \\ &= (ba)c \\ &= 1 \cdot c \\ &= c \end{align}\]

이므로 \(b = c\)이고, 즉 \(a\)는 서로 다른 둘 이상의 역원을 가질 수 없습니다. 이제 곱셈의 역원이 유일하게 존재한다는 것을 증명했으니 페르마의 소정리 등식을 위와 같이 조작해도 문제가 없겠습니다.

모듈로 정수끼리 계산하면 값이 어긋나지 않을까요?

예전에는 이런 문제를 보면서 "중간 값에 \(\bmod p\)를 걸고 계산해도 되나? 최종 값이 어긋나지는 않을까?"라는 걱정을 하면서 출제자들이 어떻게 신경을 써두었겠지라는 믿음을 가지고 풀었던 적이 있습니다.

다행히 준동형사상이라는 개념 덕분에 그런 걱정은 하지 않아도 됩니다. 이 글은 예상 독자를 백준 온라인 저지에서 문제를 푸는 사람으로 생각하고 작성했기 때문에 수학적으로 엄밀하지 않아도 전달하기 쉽도록 설명하며, 또한 문제의 답을 계산하는 과정에서 0으로 나누기가 일어나지 않거나 쉽게 피할 수 있음을 가정합니다.

우선 위에서 언급했던 체의 정의를 다시 살펴봅시다.

다르게 정의하는 체

위에서 체는 "두 이항 연산 \(+\)과 \(\times\)이 아홉 가지의 체 공리를 만족하는 대수적 구조"라고 소개한 바가 있습니다. 그런데 여기서 \(+\)와 \(\times\)의 항등원을 각각 무항 연산자, 역원을 각각 단항 연산자로 생각하고 다음과 같은 형태의 체 공리를 제시할 수도 있습니다. 이 관점에서 체는 연산자 6개와 공리 9개로 이루어진 대수적 구조입니다.

체 준동형사상

준동형사상이라는 말을 해석해보자면, "사상"은 함수를 더 유식하게 이르는 말이고3 "준동형"은 "비슷한 모양", 즉 "구조를 보존한다"는 의미입니다.4

위에서 풀어 쓴 의미를 생각해 보면, 체 준동형사상은 "체의 구조를 보존하는 함수"라고 생각할 수 있습니다. 조금 더 엄밀하게는 체 \(F\)에서 체 \(G\)로 가는 함수 \(f\)가 다음과 같이 체의 연산자 6개 모두에 대해 아래 "보존 법칙"이 성립하면 \(f\)를 체 준동형사상이라고 합니다. \(f\)의 정의역과 공역이 다르고, 이에 따라 체 연산도 \(f\) 안팎에서 다른 것을 사용함에 유의해 주세요.

  1. \(f(a + b) = f(a) + f(b)\)
  2. \(f(0) = 0\)
  3. \(f(-a) = -f(a)\)
  4. \(f(ab) = f(a)f(b)\)
  5. \(f(1) = 1\)
  6. \(a \ne 0\)에 대해 \(f \left( \frac{1}{a} \right) = \frac{1}{f(a)}\)

이 중 2번, 3번, 6번은 다른 법칙과 체 공리로부터 유도할 수 있기 때문에 실질적으로는 1번, 4번, 5번이 성립하는 것만 보이면 됩니다.

정말 체 준동형사상일까?

나중에 정의와 증명에 도움이 될 보조함수와 보조정리를 제시해 보겠습니다.

\[f' : \mathbb{Z} \rightarrow \mathbb{Z}/p\mathbb{Z} \\ f'(x) = x \bmod p\]

이 함수는 \(f'(0) = 0\), \(f'(1) = 1\)을 만족함을 쉽게 유추할 수 있습니다. 또한, 이 함수는 \(f'(x + y) = f'(x) + f'(y)\), \(f'(xy) = f'(x)f'(y)\)를 만족합니다. 증명은 10430번 "나머지"로 갈음합니다.

위의 다섯 문제에서 제시하는 체 준동형사상은 다음과 같이 정의할 수 있습니다. 이 함수는 \(b\)가 \(p\)의 배수일 때 정의되지 않기 때문에 엄밀히 말해서 체 준동형사상은 아니지만, 그래도 개념 자체는 유효합니다. 위에서 0으로 나누기를 생각하지 않는다고 한 것은 그것까지 고려하면 글이 훨씬 복잡해지기 때문입니다.

\(f : \mathbb{Q} \nrightarrow \mathbb{Z}/p\mathbb{Z} \\ f \left( \frac{a}{b} \right) = f'(a)f'(b)^{-1}\) 5

5번 법칙은 단순 대입으로 증명할 수 있습니다.

\[\begin{align} f(1) &= f \left( \frac{1}{1} \right) \\ &= f'(1)(f'(1))^{-1} \\ &= 1 \cdot 1^{-1} \\ &= 1 \end{align}\]

4번 법칙도 이렇게 증명할 수 있습니다.

\[\begin{align} f \left( \frac{a}{c} \cdot \frac{b}{d} \right) &= f \left( \frac{ab}{cd} \right) \\ &= f'(ab)(f'(cd))^{-1} \\ &= f'(a)f'(b)(f'(c)f'(d))^{-1} \\ &= f'(a)f'(b)(f'(c))^{-1}(f'(d))^{-1} \end{align}\]

그런데 한편,

\[\begin{align} f \left( \frac{a}{c} \right) f \left( \frac{b}{d} \right) &= f'(a)(f'(c))^{-1}f'(b)(f'(d))^{-1} \\ &= f'(a)f'(b)(f'(c))^{-1}(f'(d))^{-1} \end{align}\]

두 식을 같은 식으로 변형할 수 있으므로 \(f \left( \frac{a}{c} \cdot \frac{b}{d} \right) = f \left( \frac{a}{c} \right) f \left( \frac{b}{d} \right)\)임을 알 수 있습니다.

1번 법칙을 증명하는 것은 연습 문제로 남기겠습니다.

그래서 뭐가 좋나요?

일단 체 준동형사상이 있으면 아래와 같이 체 연산만으로 이루어진 수식에 분배법칙을 적용해 아래처럼 바꿀 수 있습니다.

\[f \left( \frac{ab - 1}{c + d} + e \right) = \frac{f(a)f(b) - 1}{f(c) + f(d)} + f(e)\]

그 다음에는 \(f\)의 안팎에서 체 공리가 똑같이 성립하므로 "원래 세계"의 수식에 어떤 조작을 가하든 "거울 세계"의 수식에도 똑같이 반영할 수 있습니다.

\[f \left( \frac{ab + ce + de - 1}{c + d} \right) = \frac{f(a)f(b) + f(c)f(e) + f(d)f(e) - 1}{f(c) + f(d)}\]

최종 값에 모듈로를 한 번 적용해서 답을 내는 것은 좌변, 중간 값에 미리 모듈로를 적용하고 그 값끼리 연산하는 것은 우변에 해당하므로, 글 제목대로 1,000,000,007로 그냥 나눠도 괜찮습니다! 물론 자료형이나 연산자 실수로 오버플로우가 나지 않게 코드를 조심히 작성해야 하겠습니다.

글을 시작하면서 언급했듯이 이 글을 쓰기 시작한 계기는 제가 이런 문제를 풀면서 선뜻 이해가 되지 않았던 점들을 스스로 해결하기 위해서였고, 글을 마친 지금은 쓰기 전에 비해 조금 더 안심하고 문제를 풀 수 있을 것 같습니다. 글을 읽어주신 여러분께도 도움이 되기를 바랍니다.

  1. "\(\mathbb{Z}/p\mathbb{Z}\)"라는 표기는 몫집합을 나타내는 표기인데, 이런 개념이 낮설다면 "정수의 집합(\(\mathbb{Z}\))인데 \(p\)의 배수(\(p\mathbb{Z}\))를 모두 같은 원소로 취급하겠다(\(/\))" 정도로 이해해도 될 것 같습니다(참고). \(p\)의 배수가 같은 원소가 되면 \(p\)로 나눈 나머지가 같은 수끼리도 같은 원소가 됩니다. ↩

  2. \(p = 2\)일 때는 \(a^{p - 2} = a^0 = 1\)인 것으로 정의하면 됩니다. ↩

  3. 사상(morphism)은 특히 범주론에서 자주 사용하는 단어로, 함수보다 일반적인 개념입니다. 이 글에서는 집합론의 관점에서는 사상과 함수가 같은 의미라고 생각해도 충분하겠습니다. ↩

  4. 왜 "준"이 붙는지 궁금한 분들을 위해 설명하자면, 양방향으로 구조를 보존하는 함수, 즉 역함수도 준동형사상인 준동형사상을 동형사상이라고 합니다. ↩

  5. \(f\)는 분모가 \(p\)의 배수일 때 정의되지 않는 부분함수이기 때문에 \(\mathbb{Q} \rightarrow \mathbb{Z}/p\mathbb{Z}\) 대신 \(\mathbb{Q} \nrightarrow \mathbb{Z}/p\mathbb{Z}\)로 표기합니다. ↩

1,000,000,007로 그냥 나눠도 괜찮나요?