기초 정수론1

PS에 필요한 기초적인 정수론을 다뤄 봅시다.

 

저는 수학을 잘 하지는 못합니다.

그래서 이 글에서는 각 주제에 해당하는 내용에 대해 간단히 설명만 하고, 엄밀한 증명은 하지 않을 예정입니다.

 

단순히 "이런 것들이 있다" 정도로만 봐 주시면 좋을 것 같습니다.

자세한 내용이나 증명은 다른 글을 참조해주세요.

---

유클리드 알고리즘

두 양의 정수 \(A, B\)의 최대공약수를 구해봅시다.

 

\(\gcd(A, B) = g\)라고 하면, 다음과 같이 나타낼 수 있습니다.

$$A = ga, B = gb$$

\(a\)와 \(b\)는 서로소입니다.

\(A\)를 \(B\)로 나눴을 때 몫과 나머지를 각각 \(q, r\)이라고 해 봅시다.

$$A = Bq+r$$

위의 식을 대입해 봅시다.

$$ga = gbq+r$$

$$r = g(a-bq)$$

따라서 나머지 \(r\)도 \(g\)를 약수로 가짐을 알 수 있습니다.

여기에서 만약 \(a-bq\)와 \(b\)가 서로소라면, \(B\)와 \(r\)의 최대공약수 역시 \(g\)가 될 것입니다.

 

\(a-bq\)와 \(b\)가 서로소가 아니라고 가정하고, 둘의 최대공약수를 \(h\)라고 합시다.

$$a-bq = hx, b = hy$$

\(x\)와 \(y\)는 서로소입니다.

 

그러면

$$a = h(yq+x)$$

가 되므로, \(a\)와 \(b\)가 \(h\)라는 공약수를 가지게 되는데 이는 모순입니다.

따라서 \(a-bq\)와 \(b\)는 서로소이고,

\(\gcd(A, B) = \gcd(B, r)\) 입니다.

이를 이용해 두 수의 최대공약수를 \(O(\log(A+B))\)의 시간에 구할 수 있게 됩니다.

 

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

#include <iostream>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int a, b; cin >> a >> b;
    int mul = a * b;
 
    while (b)
    {
        int r = a % b;
        a = b, b = r;
    }
 
    cout << a << '\n' << mul / a;
}

---

확장 유클리드 알고리즘

양의 정수 \(a, b\)에 대해, \(ax+by=1\)의 정수해를 하나 구해봅시다. (\(\gcd(a,b) = 1\))

 

유클리드 알고리즘과 같이, \(a\)를 \(b\)로 나눴을 때 몫과 나머지를 각각 \(q, r\)이라고 합시다.

$$a = bq + r$$

$$(bq+r)x + by = 1$$

$$b(qx+y) + rx = 1$$

 

\(qx+y = x'\), \(x = y'\)라고 하면,

$$bx' + ry' = 1$$

 

이를 계속 반복하면 결국

$$1 \cdot x + 0 \cdot y = 1$$

이라는 식을 푸는 문제로 바뀌게 되며, 이는 \(x = 1, y = 0\)이라는 답이 존재합니다.

 

이를 이용해 원래 식에서의 답도 \(O(\log(a+b))\)의 시간에 알 수 있습니다.

 

 

조금만 더 응용하면, 일반적인 \(ax+by=c\)의 해도 계산할 수 있습니다.

\(g = \gcd(a,b)\)라고 합시다.

 

먼저, \(c\)가 \(g\)로 나눠 떨어지지 않으면, 답은 없습니다.

그렇지 않다면, 양변을 모두 \(g\)로 나누어 \(a'x+b'y=c'\)라는 식으로 바꿉시다.

\(a'x+b'y=1\)에 대한 해는 확장 유클리드 알고리즘으로 구할 수 있고, 구한 해에 \(c'\)를 곱하면 됩니다.

 

www.acmicpc.net/problem/3955

3955번: 캔디 분배

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll k, c;
pll ext_gcd(ll a, ll b) // ax + by = 1의 해 반환
{
    if (b == 0) return { 1, 0 };
    pll res = ext_gcd(b, a % b); // bx' + ry = 1로 변환
    ll x = res.second;
    ll y = res.first - a / b * x;
    return { x, y };
}
 
ll mceil(ll a, ll b) // ceil(a/b)
{
    if (a > 0) return (a - 1) / b + 1;
    return a / b;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> k >> c;
        if (gcd(k, c) != 1)
        {
            // 해가 없다
            cout << "IMPOSSIBLE" << '\n';
            continue;
        }
 
        // kx + cy = 1의 해
        pll res = ext_gcd(k, c);
 
        ll x0 = res.first;
        ll y0 = res.second;
 
        // 일반해는 x = x0 + tc, y = y0 - tk (t는 정수) 이다.
        // x < 0, 0 < y <= 1e9를 만족해야 한다.
 
        ll r1 = mceil(-x0, c);
        ll r2 = mceil(y0, k);
 
        ll t_mx = min(r1, r2) - 1;
 
        if (y0 - (ll)1e9 <= k * t_mx) cout << y0 - t_mx * k << '\n';
        else cout << "IMPOSSIBLE" << '\n';
    }
}

 

마지막으로, 모듈러 역원을 구할 수 있습니다.

문제를 풀다보면 "답이 커질 수 있으니, 답을 어떤 수로 나눈 나머지를 출력하라"는 말을 많이 보셨을 겁니다.

이를 위해 모듈러 연산을 하게 되는데, 모듈러의 덧셈, 뺄셈, 곱셈은 쉽게 할 수 있지만 나눗셈은 그렇지 않습니다.

 

어떤 정수 \(a\)에 대해,

$$ax \equiv 1 \mod m$$

을 만족하는 \(x\)가 존재한다면, \(x\)를 \(a\)의 모듈러 역원이라고 합니다.

\(a\)를 나누는 연산이 필요하다면, 대신 모듈러 역원인 \(x\)를 곱하면 됩니다.

 

위 식을 다시 써보면 \(a\)와 \(m\)이 정해져 있을 때,

$$ax + my = 1$$

의 정수해를 구하는 문제와 같아지므로, 확장 유클리드 알고리즘을 이용해 답을 구할 수 있습니다.

 

www.acmicpc.net/problem/14565

14565번: 역원(Inverse) 구하기

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
pll ext_gcd(ll a, ll b) // ax + by = 1의 해 반환
{
    if (b == 0) return { 1, 0 };
    pll res = ext_gcd(b, a % b); // bx' + ry = 1로 변환
    ll x = res.second;
    ll y = res.first - a / b * x;
    return { x, y };
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    ll n, a; cin >> n >> a;
 
    ll add_inv = n - a;
    ll mul_inv = -1;
 
    // ax = 1 (mod n)
    // ax + ny = 1
 
    if (gcd(a, n) == 1)
    {
        pll res = ext_gcd(a, n);
        mul_inv = res.first;
        mul_inv = (mul_inv % n + n) % n;
    }
 
    cout << add_inv << ' ' << mul_inv;
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217