Bài 2.3. Định lý Fermat nhỏ, định lý Euler và ứng dụng

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật (CTDL & GT)! Sau khi làm quen với các khái niệm cơ bản, hôm nay chúng ta sẽ lặn sâu vào một mảng kiến thức vô cùng thú vị và mạnh mẽ: Lý thuyết số (Number Theory), đặc biệt là hai viên ngọc quý: Định lý Fermat nhỏ và Định lý Euler.

Tại sao lý thuyết số lại quan trọng trong CTDL & GT? Đơn giản là vì nhiều bài toán trong lập trình thi đấu, mật mã học, hay thậm chí là trong các ứng dụng thực tế (như băm dữ liệu - hashing) đều yêu cầu chúng ta làm việc với các con số cực lớn và thực hiện các phép tính trên chúng một cách hiệu quả. Các định lý này cung cấp những "phím tắt" và công cụ để xử lý các bài toán đồng dư (modular arithmetic) phức tạp một cách thanh lịch và nhanh chóng.

Hãy cùng khám phá sức mạnh của chúng!

1. Đồng Dư Thức (Modular Arithmetic)

Trước khi đến với các định lý, chúng ta cần nhắc lại khái niệm đồng dư thức.

Hai số nguyên a và b được gọi là đồng dư với nhau theo modulo m (kí hiệu: $a \equiv b \pmod m$) nếu hiệu $a - b$ chia hết cho m. Điều này tương đương với việc a và b có cùng số dư khi chia cho m. Ví dụ:

$10 \equiv 3 \pmod 7$ vì $10 - 3 = 7$ chia hết cho 7.
$15 \equiv 1 \pmod 7$ vì $15 - 1 = 14$ chia hết cho 7.
$-2 \equiv 5 \pmod 7$ vì $-2 - 5 = -7$ chia hết cho 7.

Các phép toán cộng, trừ, nhân vẫn hoạt động "đẹp" trong thế giới đồng dư:

Nếu $a \equiv b \pmod m$ và $c \equiv d \pmod m$, thì:
- $a + c \equiv b + d \pmod m$
- $a - c \equiv b - d \pmod m$
- $a \cdot c \equiv b \cdot d \pmod m$

Tuy nhiên, phép chia lại phức tạp hơn nhiều. Để nói về phép chia, chúng ta cần khái niệm nghịch đảo modulo.

Nghịch đảo modulo: Số nguyên x được gọi là nghịch đảo modulo của a theo modulo m nếu $a \cdot x \equiv 1 \pmod m$. Nghịch đảo modulo của a modulo m chỉ tồn tại khi và chỉ khi a và m là nguyên tố cùng nhau (tức là $GCD(a, m) = 1$). Nếu tồn tại, nghịch đảo này là duy nhất trong tập ${0, 1, \dots, m-1}$.

Ví dụ: Nghịch đảo của 3 modulo 7 là 5, vì $3 \cdot 5 = 15 \equiv 1 \pmod 7$.

Tìm nghịch đảo modulo là một bài toán quan trọng và là nơi Định lý Fermat nhỏ và Định lý Euler phát huy tác dụng.

2. Định lý Fermat nhỏ (Fermat's Little Theorem)

Đây là một trong những định lý cơ bản và mạnh mẽ nhất trong lý thuyết số, đặc biệt khi làm việc với modulo là số nguyên tố.

Định lý Fermat nhỏ phát biểu: Nếu $p$ là một số nguyên tố, thì với bất kỳ số nguyên $a$, ta có: $a^p \equiv a \pmod p$

Một dạng tương đương và phổ biến hơn (khi $a$ không chia hết cho $p$, tức là $GCD(a, p) = 1$): $a^{p-1} \equiv 1 \pmod p$

Tại sao điều này lại hữu ích?

Nhìn vào dạng $a^{p-1} \equiv 1 \pmod p$. Nếu ta nhân cả hai vế với $a^{-1}$ (nghịch đảo modulo của $a$ theo modulo $p$), ta được: $a^{p-1} \cdot a^{-1} \equiv 1 \cdot a^{-1} \pmod p$ $a^{p-2} \equiv a^{-1} \pmod p$

Wow! Điều này cho ta một cách thần kỳ để tính nghịch đảo modulo của $a$ khi modulo là một số nguyên tố $p$: Nghịch đảo của $a$ modulo $p$ chính là $a^{p-2} \pmod p$. Điều kiện là $a$ không chia hết cho $p$.

Ứng dụng 1: Tính nghịch đảo modulo khi modulus là số nguyên tố

Đây là ứng dụng trực tiếp và quan trọng nhất của Định lý Fermat nhỏ. Chúng ta có thể tính $a^{-1} \pmod p$ bằng cách tính $a^{p-2} \pmod p$. Việc tính $a^{p-2} \pmod p$ có thể thực hiện hiệu quả bằng thuật toán lũy thừa modulo (modular exponentiation) hay còn gọi là binary exponentiation.

Thuật toán lũy thừa modulo (Binary Exponentiation): Để tính $base^{exp} \pmod{mod}$, thay vì nhân base với chính nó exp lần (rất chậm nếu exp lớn), ta sử dụng biểu diễn nhị phân của exp. Ví dụ: Tính $a^{13} \pmod m$. $13$ trong nhị phân là $1101_2 = 8 + 4 + 1$. $a^{13} = a^{8+4+1} = a^8 \cdot a^4 \cdot a^1 \pmod m$. Ta có thể tính $a^1, a^2, a^4, a^8$ bằng cách bình phương liên tiếp: $a^1 = a$ $a^2 = (a^1)^2$ $a^4 = (a^2)^2$ $a^8 = (a^4)^2$ Rồi nhân các kết quả tương ứng với các bit 1 trong exp.

Độ phức tạp của thuật toán này là $O(\log exp)$, rất hiệu quả khi exp lớn.

Code minh họa tính lũy thừa modulo:

#include <iostream>

// Hàm tính (base^exp) % mod sử dụng binary exponentiation
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod; // Đảm bảo base nằm trong khoảng [0, mod-1]

    while (exp > 0) {
        // Nếu bit cuối của exp là 1, nhân res với base
        if (exp % 2 == 1) res = (res * base) % mod;

        // Bình phương base và chia exp cho 2
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    long long base = 2;
    long long exp = 10;
    long long mod = 1000000007; // Một số nguyên tố lớn thường dùng

    long long result = power(base, exp, mod);
    std::cout << base << "^" << exp << " mod " << mod << " = " << result << std::endl; // Output: 2^10 mod 1000000007 = 1024

    base = 3;
    exp = 999999998; // exp lớn
    mod = 1000000007;

    result = power(base, exp, mod);
    // Định lý Fermat nhỏ: 3^(1000000007-1) mod 1000000007 = 1
    // exp = 999999998 = 1000000007 - 9. Oops, not p-1 exactly.
    // Let's use exp = mod - 1 to verify Fermat's Little Theorem
    exp = 1000000007 - 1;
    result = power(base, exp, mod);
    std::cout << base << "^(mod-1) mod " << mod << " = " << result << std::endl; // Output: 3^(mod-1) mod 1000000007 = 1

    return 0;
}

Giải thích code power:

Hàm nhận vào base, exp và mod.
res khởi tạo là 1, đây là kết quả lũy thừa $base^0$.
base %= mod; để đảm bảo các phép nhân sau đó không bị tràn số nếu base ban đầu rất lớn, và giữ kết quả luôn trong miền đồng dư.
Vòng while lặp cho đến khi exp về 0. Mỗi lần lặp tương ứng với xử lý một bit của exp (từ phải sang trái).
if (exp % 2 == 1): Nếu bit cuối cùng của exp là 1 (tức exp lẻ), điều này có nghĩa là lũy thừa hiện tại của base (tương ứng với trọng số bit này) cần được nhân vào kết quả cuối cùng. Ta cập nhật res = (res * base) % mod.
base = (base * base) % mod;: Bình phương base để chuẩn bị cho bit tiếp theo (bit bên trái có trọng số gấp đôi).
exp /= 2;: Dịch bit của exp sang phải (tương đương bỏ bit cuối).

Code minh họa tính nghịch đảo modulo sử dụng Fermat nhỏ:

#include <iostream>

// Hàm tính (base^exp) % mod sử dụng binary exponentiation
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// Hàm tính nghịch đảo modulo của n theo modulo prime_mod
// Sử dụng Định lý Fermat nhỏ: n^(prime_mod-2) % prime_mod
long long modInverseFermat(long long n, long long prime_mod) {
    // Điều kiện để nghịch đảo tồn tại theo Fermat nhỏ: prime_mod phải là số nguyên tố
    // và n không chia hết cho prime_mod (tức GCD(n, prime_mod) = 1)
    if (prime_mod <= 1) {
        std::cerr << "Modulo must be a prime number greater than 1" << std::endl;
        return -1; // Lỗi
    }
     // Check if n is a multiple of prime_mod
    if (n % prime_mod == 0) {
         std::cerr << "N does not have a modular inverse mod " << prime_mod << std::endl;
         return -1; // Lỗi, nghịch đảo không tồn tại
    }

    // Theo Định lý Fermat nhỏ: n^(p-1) = 1 (mod p)
    // Nhân cả 2 vế với n^-1: n^(p-2) = n^-1 (mod p)
    return power(n, prime_mod - 2, prime_mod);
}

int main() {
    long long n1 = 3;
    long long prime_mod1 = 7; // 7 là số nguyên tố
    long long inv1 = modInverseFermat(n1, prime_mod1);
    if (inv1 != -1) {
        std::cout << "Nghich dao cua " << n1 << " mod " << prime_mod1 << " la: " << inv1 << std::endl; // Output: Nghich dao cua 3 mod 7 la: 5 (vi 3*5 = 15 = 2*7 + 1)
        std::cout << n1 << " * " << inv1 << " mod " << prime_mod1 << " = " << (n1 * inv1) % prime_mod1 << std::endl; // Output: 3 * 5 mod 7 = 1
    }

    long long n2 = 10;
    long long prime_mod2 = 17; // 17 là số nguyên tố
    long long inv2 = modInverseFermat(n2, prime_mod2);
     if (inv2 != -1) {
        std::cout << "Nghich dao cua " << n2 << " mod " << prime_mod2 << " la: " << inv2 << std::endl; // Output: Nghich dao cua 10 mod 17 la: 12 (vi 10*12 = 120 = 7*17 + 1)
        std::cout << n2 << " * " << inv2 << " mod " << prime_mod2 << " = " << (n2 * inv2) % prime_mod2 << std::endl; // Output: 10 * 12 mod 17 = 1
    }

    long long n3 = 7;
    long long prime_mod3 = 7; // n chia hết cho prime_mod
    long long inv3 = modInverseFermat(n3, prime_mod3); // Output lỗi và trả về -1

    return 0;
}

Giải thích code modInverseFermat:

Hàm nhận n và prime_mod.
Nó kiểm tra các điều kiện cần thiết: prime_mod phải > 1 và n không chia hết cho prime_mod. Nếu không thỏa mãn, in thông báo lỗi và trả về -1.
Nếu các điều kiện được thỏa mãn, theo Định lý Fermat nhỏ, nghịch đảo của n modulo prime_mod chính là n^(prime_mod - 2) % prime_mod.
Hàm gọi power(n, prime_mod - 2, prime_mod) để tính giá trị này một cách hiệu quả.

Lưu ý quan trọng: Định lý Fermat nhỏ chỉ áp dụng khi modulus là một số nguyên tố. Khi modulus là hợp số, chúng ta cần một công cụ tổng quát hơn: Định lý Euler.

3. Định lý Euler (Euler's Totient Theorem)

Định lý Euler là sự tổng quát hóa của Định lý Fermat nhỏ cho trường hợp modulus là một số bất kỳ (không nhất thiết là số nguyên tố). Để phát biểu định lý này, chúng ta cần hiểu về Hàm Euler (Euler's Totient Function), ký hiệu là $\phi(n)$.

Hàm Euler $\phi(n)$: Hàm $\phi(n)$ đếm số lượng các số nguyên dương nhỏ hơn hoặc bằng $n$ mà nguyên tố cùng nhau với $n$. Tức là, $\phi(n) = |{k \in {1, 2, \dots, n} \mid GCD(k, n) = 1}|$.

Ví dụ về Hàm Euler:

$\phi(1) = 1$ (số 1 nguyên tố cùng nhau với 1)
$\phi(2) = 1$ (số 1 nguyên tố cùng nhau với 2)
$\phi(p) = p-1$ nếu $p$ là số nguyên tố (tất cả các số từ 1 đến $p-1$ đều nguyên tố cùng nhau với $p$). Đây chính là lý do Định lý Fermat nhỏ chỉ có $p-1$ ở số mũ.
$\phi(10)$: Các số nhỏ hơn hoặc bằng 10 là 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Các số nguyên tố cùng nhau với 10 (tức là không chia hết cho 2 và 5) là 1, 3, 7, 9. Vậy $\phi(10) = 4$.

Cách tính $\phi(n)$: Nếu phân tích thừa số nguyên tố của $n$ là $n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_r^{k_r}$, thì công thức tính $\phi(n)$ là: $\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right)$ $\phi(n) = n \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdots \frac{p_r-1}{p_r}$ $\phi(n) = p_1^{k_1-1}(p_1-1) \cdot p_2^{k_2-1}(p_2-1) \cdots p_r^{k_r-1}(p_r-1)$

Code minh họa tính Hàm Euler:

#include <iostream>

// Hàm tính giá trị của hàm Euler phi(n)
long long phi(long long n) {
    long long result = n; // Khởi tạo result = n

    // Duyệt qua các ước số nguyên tố của n
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            // i là ước số nguyên tố
            // Áp dụng công thức result = result * (1 - 1/i) = result - result / i
            while (n % i == 0)
                n /= i; // Loại bỏ tất cả các thừa số i
            result -= result / i;
        }
    }

    // Nếu sau vòng lặp, n > 1, tức là n còn một thừa số nguyên tố lớn hơn sqrt(n)
    if (n > 1)
        result -= result / n;

    return result;
}

int main() {
    std::cout << "phi(1) = " << phi(1) << std::endl;     // Output: 1
    std::cout << "phi(7) = " << phi(7) << std::endl;     // Output: 6 (7 la so nguyen to)
    std::cout << "phi(10) = " << phi(10) << std::endl;   // Output: 4 (cac so nguyen to cung nhau voi 10: 1, 3, 7, 9)
    std::cout << "phi(12) = " << phi(12) << std::endl;   // Output: 4 (cac so nguyen to cung nhau voi 12: 1, 5, 7, 11. 12 = 2^2 * 3. phi(12) = 12 * (1-1/2) * (1-1/3) = 12 * 1/2 * 2/3 = 4)
    return 0;
}

Giải thích code phi:

Khởi tạo result = n. Đây là bước bắt đầu của công thức $\phi(n) = n \prod (1 - 1/p)$.
Vòng lặp duyệt i từ 2 đến sqrt(n) để tìm các ước số nguyên tố nhỏ của n.
Nếu i là ước của n, nó là một thừa số nguyên tố $p$.
- while (n % i == 0) n /= i; loại bỏ tất cả các lần xuất hiện của thừa số nguyên tố i từ n. Điều này giúp đảm bảo n chỉ còn chứa các thừa số nguyên tố chưa được xử lý.
- result -= result / i; áp dụng phần $(1 - 1/i)$ của công thức. result hiện tại là $n \prod_{p_j < i} (1 - 1/p_j)$. Nhân với $(1 - 1/i)$ tương đương với trừ đi $result/i$.
Sau vòng lặp, nếu n > 1, điều đó có nghĩa là n ban đầu có một thừa số nguyên tố lớn hơn sqrt(n). Thừa số này chính là giá trị còn lại của n. Ta xử lý thừa số nguyên tố lớn này tương tự.

Định lý Euler phát biểu: Nếu $a$ và $n$ là hai số nguyên dương nguyên tố cùng nhau (tức là $GCD(a, n) = 1$), thì: $a^{\phi(n)} \equiv 1 \pmod n$

Tại sao điều này lại hữu ích?

Tương tự như Định lý Fermat nhỏ, từ $a^{\phi(n)} \equiv 1 \pmod n$, nếu $GCD(a, n) = 1$, ta nhân cả hai vế với $a^{-1}$ (nghịch đảo modulo của $a$ theo modulo $n$), ta được: $a^{\phi(n)} \cdot a^{-1} \equiv 1 \cdot a^{-1} \pmod n$ $a^{\phi(n)-1} \equiv a^{-1} \pmod n$

Đây là cách tổng quát để tính nghịch đảo modulo của $a$ theo modulo bất kỳ $n$ (với điều kiện $GCD(a, n) = 1$).

Ứng dụng 1: Tính nghịch đảo modulo khi modulus là hợp số

Nếu $GCD(a, n) = 1$, ta có thể tính $a^{-1} \pmod n$ bằng cách tính $a^{\phi(n)-1} \pmod n$ sử dụng thuật toán lũy thừa modulo và hàm Euler.

Code minh họa tính nghịch đảo modulo sử dụng Định lý Euler:

#include <iostream>

// Hàm tính (base^exp) % mod sử dụng binary exponentiation
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// Hàm tính giá trị của hàm Euler phi(n)
long long phi(long long n) {
    long long result = n;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

// Hàm tính nghịch đảo modulo của n theo modulo m
// Sử dụng Định lý Euler: n^(phi(m)-1) % m
long long modInverseEuler(long long n, long long m) {
     if (m <= 1) {
        std::cerr << "Modulo must be greater than 1" << std::endl;
        return -1; // Lỗi
    }
    // Điều kiện để nghịch đảo tồn tại theo Euler: GCD(n, m) = 1
    // Cần hàm GCD để kiểm tra, nhưng tạm bỏ qua trong ví dụ này và giả định GCD(n, m) = 1
    // Hoặc kiểm tra phi(m) - 1 >= 0

    // Theo Định lý Euler: n^phi(m) = 1 (mod m) nếu GCD(n, m) = 1
    // Nhân cả 2 vế với n^-1: n^(phi(m)-1) = n^-1 (mod m)
    long long phi_m = phi(m);
    if (phi_m == 0) { // Should not happen for m > 1, but good practice
        std::cerr << "Phi(m) is 0, cannot compute inverse." << std::endl;
        return -1;
    }
    // Need phi(m) - 1 >= 0, which is true for phi(m) >= 1. phi(m) >= 1 for m > 1.

    return power(n, phi_m - 1, m);
}

int main() {
    long long n1 = 3;
    long long m1 = 10; // 10 là hợp số, GCD(3, 10) = 1
    long long inv1 = modInverseEuler(n1, m1);
    if (inv1 != -1) {
        std::cout << "Nghich dao cua " << n1 << " mod " << m1 << " la: " << inv1 << std::endl; // phi(10) = 4. 3^(4-1) mod 10 = 3^3 mod 10 = 27 mod 10 = 7.
        std::cout << n1 << " * " << inv1 << " mod " << m1 << " = " << (n1 * inv1) % m1 << std::endl; // Output: 3 * 7 mod 10 = 1
    }

    long long n2 = 8;
    long long m2 = 15; // 15 là hợp số, GCD(8, 15) = 1
    long long inv2 = modInverseEuler(n2, m2); // phi(15). 15 = 3*5. phi(15) = 15*(1-1/3)*(1-1/5) = 15 * 2/3 * 4/5 = 8
    // inv = 8^(8-1) mod 15 = 8^7 mod 15
    // 8^2 = 64 = 4*15 + 4 = 4 mod 15
    // 8^3 = 8 * 4 = 32 = 2*15 + 2 = 2 mod 15
    // 8^7 = 8^3 * 8^3 * 8^1 = 2 * 2 * 8 = 4 * 8 = 32 = 2 mod 15
    if (inv2 != -1) {
        std::cout << "Nghich dao cua " << n2 << " mod " << m2 << " la: " << inv2 << std::endl; // Output: 2
        std::cout << n2 << " * " << inv2 << " mod " << m2 << " = " << (n2 * inv2) % m2 << std::endl; // Output: 8 * 2 mod 15 = 16 mod 15 = 1
    }

    long long n3 = 6;
    long long m3 = 10; // GCD(6, 10) = 2 != 1. Nghịch đảo không tồn tại.
    // modInverseEuler sẽ tính phi(10)=4, rồi power(6, 3, 10) = 6^3 mod 10 = 216 mod 10 = 6.
    // 6 * 6 = 36 = 3*10 + 6 != 1 mod 10. Kết quả 6 không phải nghịch đảo.
    // Hàm cần kiểm tra GCD trước, nhưng ví dụ này tạm bỏ qua để minh họa công thức.
    // Để chính xác, cần thêm kiểm tra if (std::gcd(n, m) != 1) return -1;
     long long inv3 = modInverseEuler(n3, m3);
     if (inv3 != -1) {
         std::cout << "Nghich dao cua " << n3 << " mod " << m3 << " la: " << inv3 << std::endl;
     } else {
         std::cout << "Nghich dao cua " << n3 << " mod " << m3 << " khong ton tai." << std::endl; // Should be the output
     }


    return 0;
}

Giải thích code modInverseEuler:

Hàm nhận n và m.
Tính phi(m) sử dụng hàm phi đã viết.
Theo Định lý Euler, nếu GCD(n, m) = 1, thì nghịch đảo của n modulo m là n^(phi(m)-1) % m.
Hàm gọi power(n, phi_m - 1, m) để tính giá trị này hiệu quả.
Lưu ý: Code ví dụ này chưa bao gồm kiểm tra $GCD(n, m) = 1$, đây là điều kiện bắt buộc để nghịch đảo tồn tại và định lý Euler áp dụng cho việc tìm nghịch đảo. Trong thực tế, bạn cần thêm kiểm tra if (std::gcd(n, m) != 1) return -1; (cần include <numeric>).

Ứng dụng 2: Rút gọn số mũ lớn trong lũy thừa modulo

Định lý Euler còn có một ứng dụng cực kỳ quan trọng khác: giúp tính $a^b \pmod n$ khi số mũ $b$ là một số rất lớn (thậm chí không thể lưu trong các kiểu dữ liệu chuẩn, ví dụ $b$ cho dưới dạng chuỗi).

Nếu $GCD(a, n) = 1$, thì từ Định lý Euler $a^{\phi(n)} \equiv 1 \pmod n$. Điều này có nghĩa là lũy thừa của $a$ modulo $n$ lặp lại sau mỗi $\phi(n)$ bước. Chu kỳ này cho phép chúng ta rút gọn số mũ: $a^b \equiv a^{b \pmod{\phi(n)}} \pmod n$, với điều kiện $b \ge \phi(n)$ (và $GCD(a, n) = 1$).

Nếu $b < \phi(n)$, thì $a^b \equiv a^b \pmod n$ (không cần rút gọn số mũ). Nếu $b = 0$, thì $a^0 \equiv 1 \pmod n$.

Một cách phát biểu chính xác hơn và thường dùng trong các bài toán competitive programming (đặc biệt khi $b$ rất lớn) là: Nếu $GCD(a, n) = 1$: $a^b \equiv a^{b \pmod{\phi(n)}} \pmod n$ nếu $b \pmod{\phi(n)} \ne 0$ $a^b \equiv a^{\phi(n)} \pmod n$ nếu $b \pmod{\phi(n)} = 0$ và $b > 0$ $a^b \equiv a^0 \pmod n = 1 \pmod n$ nếu $b = 0$

Hoặc có thể kết hợp lại thành $a^b \equiv a^{b \pmod{\phi(n)} + \phi(n) \cdot [b \ge \phi(n)]} \pmod n$ (sử dụng ký hiệu Iverson bracket [condition] = 1 nếu condition đúng, 0 nếu sai), hoặc đơn giản hơn trong code thường là a^b mod n = power(a, (b % phi_n) + phi_n, n) nếu $b$ được đọc dưới dạng chuỗi và lớn, và GCD(a, n) = 1. Lưu ý rằng nếu $b$ là số 0 thì $b \pmod{\phi(n)} = 0$, nên cần xử lý riêng trường hợp $b=0$ hoặc dùng công thức cộng thêm $\phi(n)$ khi $b \ge \phi(n)$.

Cách tiếp cận phổ biến khi $b$ là một chuỗi số rất dài:

Tính $m = \phi(n)$.
Tính $b' = b \pmod m$.
Nếu $b' = 0$ và $b$ ban đầu > 0, đặt $b' = m$. (Điều này đảm bảo $a^b \equiv a^m \pmod n$ khi $b$ là bội của $m$, theo Euler).
Kết quả là $a^{b'} \pmod n$.

Code minh họa tính lũy thừa modulo với số mũ lớn (dạng chuỗi):

#include <iostream>
#include <string>
#include <vector>

// Hàm tính (base^exp) % mod sử dụng binary exponentiation
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// Hàm tính giá trị của hàm Euler phi(n)
long long phi(long long n) {
    long long result = n;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

// Hàm tính b % m khi b là một chuỗi rất dài
long long modString(const std::string& b, long long m) {
    long long res = 0;
    for (char digit : b) {
        res = (res * 10 + (digit - '0')) % m;
    }
    return res;
}

// Hàm tính a^b % n khi b là chuỗi, sử dụng Euler Totient Theorem
long long powerWithLargeExponent(long long a, const std::string& b, long long n) {
    if (n == 1) return 0; // a^b mod 1 = 0

    // Tính phi(n)
    long long phi_n = phi(n);

    // Tính b mod phi_n
    long long reduced_exp = modString(b, phi_n);

    // Cần kiểm tra liệu b có >= phi_n hay không. Nếu có, và reduced_exp = 0,
    // thì số mũ hiệu dụng là phi_n chứ không phải 0.
    // Cách đơn giản để kiểm tra b >= phi_n với b là chuỗi: so sánh độ dài
    // hoặc tính giá trị của b và so sánh, nhưng tính giá trị b có thể tràn.
    // Một cách tiếp cận phổ biến khác (và an toàn hơn) trong competitive programming
    // là luôn sử dụng số mũ (b mod phi_n) + phi_n nếu b đủ lớn,
    // hoặc (b mod phi_n) nếu b nhỏ.
    // Hoặc đơn giản hơn, nếu b = 0 (chuỗi "0"), kết quả là a^0 = 1 mod n.
    // Nếu b > 0, và reduced_exp = 0, nghĩa là b là bội của phi_n.
    // Theo Euler, a^b = a^phi(n) = 1 (mod n) nếu GCD(a,n)=1 và b > 0.
    // Tuy nhiên, công thức a^b = a^(b mod phi(n)) là SAI nếu b < phi(n).
    // Công thức chính xác (cho GCD(a,n)=1) là: a^b = a^(b mod phi(n)) nếu b < phi(n)
    // và a^b = a^((b mod phi(n)) + phi(n)) nếu b >= phi(n).
    // Khi b là chuỗi, khó so sánh b với phi_n trực tiếp.
    // Cách hay dùng là tính b' = b mod phi(n). Nếu b' = 0, và b > 0,
    // thì số mũ thực sự là phi(n). Nếu b' != 0, số mũ là b'.
    // Trường hợp b = "0" -> reduced_exp = 0. Cần xử lý riêng.

    // Kiểm tra nếu chuỗi b là "0"
    bool is_b_zero = true;
    for(char c : b) {
        if (c != '0') {
            is_b_zero = false;
            break;
        }
    }

    if (is_b_zero) {
        return power(a, 0, n); // a^0 mod n = 1 mod n (correct for n>1)
    }


    // Nếu b > 0 và b chia hết cho phi_n (reduced_exp == 0), số mũ hiệu dụng là phi_n
    if (reduced_exp == 0) {
        reduced_exp = phi_n;
    }

     // Cần đảm bảo GCD(a, n) = 1 để Euler áp dụng được.
     // Nếu GCD(a, n) != 1, cần thuật toán khác (như mở rộng CRT hoặc properties of modular exponentiation)
     // Tạm giả định GCD(a, n) = 1 trong ví dụ này cho đơn giản.

    return power(a, reduced_exp, n);
}

int main() {
    long long a1 = 2;
    std::string b1 = "100000000000000000000"; // b rất lớn
    long long n1 = 1000000007; // Số nguyên tố
    // phi(n1) = n1 - 1 = 1000000006
    // b1 mod phi(n1): "10...0" mod 1000000006
    // 10^20 mod 1000000006
    // reduced_exp = modString(b1, phi(n1))
    // power(a1, reduced_exp, n1)

    long long phi_n1 = phi(n1); // 1000000006
    long long reduced_exp1 = modString(b1, phi_n1); // 10^20 mod 1000000006
    std::cout << "phi(" << n1 << ") = " << phi_n1 << std::endl;
    std::cout << "(\"" << b1 << "\") mod " << phi_n1 << " = " << reduced_exp1 << std::endl;
    // reduced_exp1 = 100000000000000000000 mod 1000000006. Let's compute this manually or with a calculator.
    // 10^9 = 1 mod 1000000007 by Fermat. Wait, mod is n1=1000000007. phi(n1)=1000000006.
    // 10^9 mod 1000000006
    // This calculation requires careful handling of modString with a potentially non-prime modulus.
    // The point is, we compute the exponent modulo phi(n).
    // Let's use a simpler example with known values.

    std::cout << "--- Simple Examples ---" << std::endl;
    long long a2 = 3;
    std::string b2 = "40";
    long long n2 = 10; // hợp số
    // phi(10) = 4
    // b2 = 40. 40 mod phi(10) = 40 mod 4 = 0.
    // b2 > 0 và 40 là bội của 4. Số mũ hiệu dụng là phi(10) = 4.
    // Kết quả: 3^4 mod 10 = 81 mod 10 = 1.
    // Theo công thức: power(3, (40 % 4 == 0 && 40 > 0) ? 4 : (40 % 4), 10) = power(3, 4, 10) = 1.

    long long phi_n2 = phi(n2); // phi(10) = 4
    long long reduced_exp2 = modString(b2, phi_n2); // 40 mod 4 = 0
    if (reduced_exp2 == 0 && b2 != "0") { // If b is > 0 and multiple of phi_n
       reduced_exp2 = phi_n2; // Use phi_n as exponent
    }
    // Check if b2 is "0" explicitly if needed
    bool is_b2_zero = true; for(char c : b2) if(c != '0') is_b2_zero = false;
    if(is_b2_zero) reduced_exp2 = 0;

    std::cout << "phi(" << n2 << ") = " << phi_n2 << std::endl; // Output: 4
    std::cout << "(\"" << b2 << "\") mod " << phi_n2 << " = " << modString(b2, phi_n2) << std::endl; // Output: 0
    std::cout << a2 << "^(\"" << b2 << "\") mod " << n2 << " = " << powerWithLargeExponent(a2, b2, n2) << std::endl; // Output: 1

    long long a3 = 3;
    std::string b3 = "27";
    long long n3 = 10;
    // phi(10) = 4
    // b3 = 27. 27 mod phi(10) = 27 mod 4 = 3.
    // b3 > 0 và không chia hết cho 4. Số mũ hiệu dụng là 3.
    // Kết quả: 3^3 mod 10 = 27 mod 10 = 7.
    // Theo công thức: power(3, (27 % 4 == 0 && 27 > 0) ? 4 : (27 % 4), 10) = power(3, 3, 10) = 7.

    long long phi_n3 = phi(n3); // phi(10) = 4
    long long reduced_exp3 = modString(b3, phi_n3); // 27 mod 4 = 3
     bool is_b3_zero = true; for(char c : b3) if(c != '0') is_b3_zero = false;
    if(!is_b3_zero && reduced_exp3 == 0) { // If b is > 0 and multiple of phi_n
       reduced_exp3 = phi_n3; // Use phi_n as exponent
    } else if (is_b3_zero) {
       reduced_exp3 = 0;
    }
    // For b3="27", reduced_exp3 = 3.

    std::cout << "phi(" << n3 << ") = " << phi_n3 << std::endl; // Output: 4
     std::cout << "(\"" << b3 << "\") mod " << phi_n3 << " = " << modString(b3, phi_n3) << std::endl; // Output: 3
    std::cout << a3 << "^(\"" << b3 << "\") mod " << n3 << " = " << powerWithLargeExponent(a3, b3, n3) << std::endl; // Output: 7


    long long a4 = 5;
    std::string b4 = "0";
    long long n4 = 10; // phi(10) = 4
    // b4 = "0". reduced_exp = 0. is_b4_zero = true.
    // Result: 5^0 mod 10 = 1.
     std::cout << a4 << "^(\"" << b4 << "\") mod " << n4 << " = " << powerWithLargeExponent(a4, b4, n4) << std::endl; // Output: 1

    // Example where GCD(a, n) != 1. Euler doesn't guarantee a^phi(n) = 1 mod n.
    // E.g., 2^phi(10) = 2^4 = 16 != 1 mod 10. 16 mod 10 = 6.
    // The property a^b = a^(b mod phi(n)) mod n for b >= phi(n) also requires GCD(a, n) = 1.
    // For GCD(a, n) != 1, more complex theorems or algorithms are needed.
    // However, for exponents b >= log2(n), a^b mod n becomes periodic. The period is called Carmichael function lambda(n), which divides phi(n).
    // But Euler's theorem with phi(n) is often sufficient for many problems where GCD(a, n) = 1 is given or implied.

    return 0;
}

Giải thích code powerWithLargeExponent:

Hàm nhận a, chuỗi b (số mũ), và n (modulus).
Trường hợp n = 1 xử lý riêng vì mọi số modulo 1 đều bằng 0.
Tính phi_n = phi(n).
Tính reduced_exp = b mod phi_n bằng hàm modString. Hàm modString hiệu quả cho chuỗi dài vì nó thực hiện phép modulo ở mỗi bước cộng/nhân.
Kiểm tra nếu chuỗi b là "0". Nếu đúng, kết quả là $a^0 \pmod n$, thường là 1 (trừ trường hợp $a=0$ và $n>1$, khi đó $0^0$ thường được coi là 1 trong bối cảnh này, hoặc không xác định, nhưng $0^0 \pmod n$ với $n > 1$ thường là 1).
Nếu b không phải là "0" và reduced_exp bằng 0, điều này có nghĩa là b là bội của phi_n (và b > 0). Theo Định lý Euler (khi $GCD(a, n) = 1$), $a^b \equiv a^{\phi(n)} \equiv 1 \pmod n$. Do đó, số mũ hiệu dụng trong trường hợp này là phi_n. Ta gán reduced_exp = phi_n.
Nếu reduced_exp khác 0, thì số mũ hiệu dụng chính là reduced_exp.
Cuối cùng, tính power(a, reduced_exp, n) để lấy kết quả cuối cùng.
Lưu ý quan trọng: Hàm này giả định $GCD(a, n) = 1$. Nếu $GCD(a, n) \ne 1$, Định lý Euler không đảm bảo $a^{\phi(n)} \equiv 1 \pmod n$. Mặc dù phép rút gọn số mũ vẫn có thể áp dụng được với một số sửa đổi (sử dụng hàm Carmichael $\lambda(n)$ hoặc các tính chất đặc biệt khi $GCD(a, n) \ne 1$), phiên bản dựa trên $\phi(n)$ này là phổ biến nhất cho các bài toán mà điều kiện nguyên tố cùng nhau được đáp ứng.

4. Các ứng dụng khác và tầm quan trọng

Ngoài việc tính nghịch đảo modulo và rút gọn số mũ, Định lý Fermat nhỏ và Euler còn là nền tảng cho nhiều thuật toán và lĩnh vực khác:

Kiểm tra tính nguyên tố (Primality Testing): Định lý Fermat nhỏ cung cấp cơ sở cho các thuật toán kiểm tra nguyên tố xác suất như Kiểm tra Miller-Rabin. Nếu $a^{p-1} \not\equiv 1 \pmod p$ cho một số $a$ nào đó, thì $p$ chắc chắn không phải số nguyên tố. Nếu $a^{p-1} \equiv 1 \pmod p$ cho nhiều giá trị $a$, thì $p$ có khả năng cao là số nguyên tố (nhưng không chắc chắn 100% do tồn tại số Carmichael).
Mật mã học: Đặc biệt là hệ mật mã RSA. RSA dựa trên sự khó khăn của việc phân tích thừa số nguyên tố các số lớn. Các phép toán trong RSA (như mã hóa, giải mã) sử dụng lũy thừa modulo với số mũ rất lớn, và Định lý Euler đảm bảo tính đúng đắn của quá trình giải mã.
Các bài toán Tổ hợp (Combinatorics): Nhiều bài toán đếm trong tổ hợp yêu cầu tính kết quả modulo một số $m$. Khi $m$ là số nguyên tố, ta thường cần tính các tổ hợp $C(n, k) = \frac{n!}{k!(n-k)!} \pmod m$. Việc tính nghịch đảo modulo của $k!$ và $(n-k)!$ sử dụng Định lý Fermat nhỏ là cách tiếp cận tiêu chuẩn.
Các bài toán liên quan đến Chu kỳ trong dãy số modulo: Định lý Euler giúp xác định chu kỳ của dãy $a^1, a^2, a^3, \dots \pmod n$ khi $GCD(a, n) = 1$. Chu kỳ này chia hết $\phi(n)$.

Bài tập ví dụ:

Số Sphenic

Số nguyên dương N được gọi là số Sphenic nếu N được phân tích duy nhất dưới dạng tích của ba thừa số nguyên tố khác nhau.

Ví dụ:

N = 30 là số Sphenic vì 30 = 2 × 3 × 5
N = 60 không phải số Sphenic vì 60 = 2 × 2 × 3 × 5

Cho số tự nhiên N, nhiệm vụ của bạn là kiểm tra xem N có phải số Sphenic hay không?

Input Format

Một số nguyên dương N (1 ≤ N ≤ 10^18).

Constraints

1 ≤ N ≤ 10^18

Output Format

Đưa ra YES hoặc NO tương ứng với N là số Sphenic hoặc không.

Sample Input 0

Sample Output 0

YES

Okay, đây là hướng dẫn giải bài "Số Sphenic" bằng C++ một cách ngắn gọn và tập trung vào thuật toán hiệu quả cho N lớn.

Hiểu định nghĩa: Số Sphenic là tích của đúng 3 thừa số nguyên tố phân biệt. Điều này có nghĩa là trong phân tích thừa số nguyên tố của N, mỗi thừa số nguyên tố chỉ được xuất hiện với số mũ là 1, và tổng số lượng thừa số nguyên tố (đếm các số phân biệt) phải là 3.
Phương pháp: Chúng ta cần phân tích N thành thừa số nguyên tố. Vì N có thể rất lớn (lên đến 10^18), phương pháp phân tích thông thường đến căn bậc hai của N cần được áp dụng cẩn thận.
Thuật toán phân tích và kiểm tra:
- Sử dụng một biến đếm (distinct_prime_factors_count) để theo dõi số lượng thừa số nguyên tố phân biệt đã tìm thấy.
- Sử dụng một biến tạm (temp_N) để lưu giá trị hiện tại của N khi chia dần các thừa số. Khởi tạo temp_N = N.
- Lặp qua các số i từ 2. Điều kiện dừng vòng lặp là khi i * i > temp_N. (Sử dụng long long cho i và temp_N để tránh tràn số).
- Trong vòng lặp:
  - Nếu temp_N chia hết cho i:
    - Đây là một thừa số nguyên tố mới. Tăng biến đếm distinct_prime_factors_count lên 1.
    - Nếu distinct_prime_factors_count đã vượt quá 3, ngay lập tức kết luận N không phải số Sphenic và dừng xử lý.
    - Bắt đầu chia temp_N cho i liên tục (while (temp_N % i == 0) temp_N /= i;). Điều này loại bỏ tất cả các lần xuất hiện của thừa số i. Quan trọng: Vì số Sphenic yêu cầu các thừa số nguyên tố phân biệt (số mũ bằng 1), nếu trong quá trình chia lặp này, chúng ta chia được temp_N cho i lần thứ hai trở đi (tức là số mũ của i lớn hơn 1), thì N không phải số Sphenic. Cần kiểm tra điều kiện này trong hoặc ngay sau vòng lặp while chia temp_N cho i. Một cách đơn giản hơn là chỉ cần chia temp_N cho i một lần, và sau đó kiểm tra xem temp_N có còn chia hết cho i không. Nếu có, số mũ > 1.
- Sau khi vòng lặp kết thúc (khi i * i > temp_N), nếu temp_N vẫn còn lớn hơn 1, điều đó có nghĩa là phần còn lại của temp_N là một thừa số nguyên tố cuối cùng (và nó phải lớn hơn căn bậc hai của giá trị N ban đầu hoặc giá trị temp_N khi bắt đầu vòng lặp cuối cùng).
- Tăng distinct_prime_factors_count lên 1 cho thừa số nguyên tố cuối cùng này.
- Nếu sau khi tăng, distinct_prime_factors_count vượt quá 3, kết luận N không phải số Sphenic.
- Cuối cùng, kiểm tra xem distinct_prime_factors_count có chính xác bằng 3 hay không. Nếu có, N là số Sphenic (YES), ngược lại là không (NO).
Lưu ý cho số mũ: Cách kiểm tra số mũ bằng 1 hiệu quả hơn: Khi tìm thấy một ước i, tăng distinct_prime_factors_count, sau đó dùng vòng while chia temp_N /= i cho đến khi không chia hết nữa. Nếu trong vòng while này, temp_N bị chia cho i nhiều hơn 1 lần, thì N không phải số Sphenic.
Kết luận: Xây dựng logic theo các bước trên, sử dụng kiểu dữ liệu long long cho N và các biến liên quan đến giá trị của N hoặc bình phương của ước số.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.