Ghi chú học lý thuyết số: Định lý Fermat nhỏ, Hàm Euler, Định lý Euler, Công thức hạ bậc Euler

Kiến thức nền tảng

Hệ thặng dư đầy đủ

Tập hợp gồm n phần tử được lấy từ mỗi lớp thặng dư mod n tạo thành hệ thặng dư đầy đủ của n.

Hệ thặng dư thu gọn

Được gọi là hệ thặng dư tối giản. Nói đơn giản, hệ thặng dư thu gọn của n là tập hợp các số nguyên tố cùng nhau với n trong hệ thặng dư đầy đủ.

Định lý Fermat nhỏ

Nội dung:

Nếu $p$ là số nguyên tố và $\gcd(a,p)=1$, thì $a^{p-1}\equiv1\pmod p$.

Chứng minh:

Xét hệ thặng dư thu gọn của $p$ là $\{1,2,3,\cdots,p-1\}$. Khi nhân mỗi phần tử với $k$ ($\gcd(k,p)=1$), tập hợp mới vẫn là hệ thặng dư thu gọn của $p$.

Giả sử tồn tại hai phần tử $k\times a_1$ và $k\times a_2$ bằng nhau mod $p$:

$k\times a_1\equiv k\times a_2\pmod p$

Suy ra $p\mid k\times(a_1-a_2)$. Do $\gcd(p,k)=1$ nên $p\mid(a_1-a_2)$, mâu thuẫn với $0 < a_1,a_2 \le p-1$.

Từ đó có:

$(p-1)!\equiv(p-1)!\times k^{p-1}\pmod p$

Vì $\gcd((p-1)!,p)=1$ nên rút gọn được $k^{p-1}\equiv1\pmod p$.

Ứng dụng

Tính nghịch đảo modulo - ứng dụng quan trọng trong mã hóa.

Hàm Euler

Định nghĩa

Hàm $\varphi(x)$ đếm số nguyên dương nhỏ hơn x và nguyên tố cùng nhau với x.

Công thức

$\varphi(x)=x\prod_{i=1}^{n}(1-\frac{1}{p_i})$

Với $p_i$ là các thừa số nguyên tố của x.

Thuộc tính

  • Hàm nhân tính: $\varphi(nm)=\varphi(n)\varphi(m)$ khi $\gcd(n,m)=1$
  • $\varphi(p^k)=(p-1)\times p^{k-1}$ với p nguyên tố

Thực hiện sàng tuyến tính

#include<iostream>
using namespace std;
const int MAX = 1e5 + 5;
int phi[MAX], prime[MAX], cnt;

int main() {
    int n; cin >> n;
    phi[1] = 1;
    for (int i=2; i<=n; i++) {
        if (!prime[i]) {
            prime[++cnt] = i;
            phi[i] = i-1;
        }
        for (int j=1; j<=cnt && i*prime[j]<=n; j++) {
            int tmp = i * prime[j];
            prime[tmp] = 1;
            if (i % prime[j] == 0) {
                phi[tmp] = phi[i] * prime[j];
                break;
            } else {
                phi[tmp] = phi[i] * (prime[j]-1);
            }
        }
    }
    for (int i=1; i<=n; i++) cout << phi[i] << " ";
}

Định lý Euler

Nội dung:

Nếu $\gcd(a,m)=1$ thì $a^{\varphi(m)}\equiv 1\pmod m$

Chứng minh:

Xét hệ thặng dư thu gọn của $m$ có $\varphi(m)$ phần tử. Khi nhân mỗi phần tử với $a$ ($\gcd(a,m)=1$), tập hợp mới vẫn là hệ thặng dư thu gọn.

$$\prod p_i \equiv \prod (a \cdot p_i) \pmod m$$ $$\Rightarrow \prod p_i \equiv a^{\varphi(m)} \prod p_i \pmod m$$ $$\Rightarrow a^{\varphi(m)} \equiv 1 \pmod m$$

Công thức hạ bậc Euler

Định lý mở rộng:

$a^b \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod m$ khi $b \ge \varphi(m)$

Thực hiện:

#include<iostream>
using namespace std;

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    long long a, m; string s;
    cin >> a >> m >> s;
    
    // Tính φ(m)
    long long phi = m, tmp = m;
    for (int i=2; i*i<=tmp; i++) {
        if (tmp % i == 0) {
            phi = phi / i * (i-1);
            while (tmp % i == 0) tmp /= i;
        }
    }
    if (tmp > 1) phi = phi / tmp * (tmp-1);
    
    // Tính số mũ
    long long exp = 0;
    for (char c : s) exp = (exp * 10 + c - '0') % phi + phi;
    
    cout << power(a % m, exp, m);
}

Thẻ: lý thuyết số định lý Fermat hàm Euler định lý Euler công thức hạ bậc

Đăng vào ngày 8 tháng 7 lúc 15:53

Thẻ Phổ Biến

©2026 Thành phố Cuồng loạn