---
# System prepended metadata

title: 中國餘式定理、歐拉定理、費馬小定理
tags: [競程筆記, 數論]

---

中國餘式定理、歐拉定理、費馬小定理
===

###### tags: `數論`、`競程筆記`

中國餘式定理
---
- 功能：用於處理餘數相同的問題
- 範例
    1. Question $x = ?$
        $\hspace{1mm}$
        $\begin{equation}
        \left\{
            \begin{array}{lr}
                x\equiv 2\mod 3 \\
                x\equiv 3\mod 5 \\
                x\equiv 2\mod 7
            \end{array}
        \right.
        \end{equation}$
        $\hspace{1mm}$

        Anwser
        
        把 $x$ 當成 $a+b+c$
        $\hspace{1mm}$
        $\begin{equation}
        \left\{
            \begin{array}{lr}
                a+b+c\equiv 2\mod 3 \\
                a+b+c\equiv 3\mod 5 \\
                a+b+c\equiv 2\mod 7
            \end{array}
        \right.
        \end{equation}$
        
        $\begin{equation}
            \begin{gathered}
                \left\{
                    \begin{array}{lr}
                        a\equiv 2\mod 3 \\
                        b\equiv 0\mod 3 \\
                        c\equiv 0\mod 3
                    \end{array}
                \right.
                \quad
                \left\{
                    \begin{array}{lr}
                        a\equiv 0\mod 5 \\
                        b\equiv 3\mod 5 \\
                        c\equiv 0\mod 5
                    \end{array}
                \right.
                \quad
                \left\{
                    \begin{array}{lr}
                        a\equiv 0\mod 7 \\
                        b\equiv 0\mod 7 \\
                        c\equiv 2\mod 7
                    \end{array}
                \right.
            \end{gathered}
        \end{equation}$

        $\begin{equation}
            \left\{
                \begin{array}{lr}
                    a\equiv 2\mod 3 \\
                    b\equiv 0\mod 5  \rightarrow a = 35p \quad \because 3 | 35p - 2 \quad \therefore p = 1, a = 35 \\
                    c\equiv 0\mod 7
                \end{array}
            \right.
        \end{equation}$

        $\begin{equation}
            \left\{
                \begin{array}{lr}
                    a\equiv 0\mod 3 \\
                    b\equiv 3\mod 5 \rightarrow b = 21p \quad \because 5 | 21p - 3 \quad \therefore p = 3, b = 63 \\
                    c\equiv 0\mod 7
                \end{array}
            \right.
        \end{equation}$

        $\begin{equation}
            \left\{
                \begin{array}{lr}
                    a\equiv 0\mod 3 \\
                    b\equiv 0\mod 5 \rightarrow c = 15p \quad \because 7 | 15p - 2 \quad \therefore p = 2, c = 30 \\
                    c\equiv 2\mod 7
                \end{array}
            \right.
        \end{equation}$
        $\hspace{1mm}$
        $a+b+c = 128 = x （x 可能為多種解）$

    2. 求最小解
    
        先求 $3, 5, 7$ 的最小公倍數
        $[3, 5, 7] = 105$
        
        $\begin{equation}
            \begin{gathered}
                \left\{
                    \begin{array}{lr}
                        128\equiv 2\mod 3 \\
                        128\equiv 3\mod 5 \\
                        128\equiv 2\mod 7
                    \end{array}
                \right.
                \quad
                \left\{
                    \begin{array}{lr}
                        105t\equiv 0\mod 3 \\
                        105t\equiv 0\mod 5 \\
                        105t\equiv 0\mod 7
                    \end{array}
                \right.
                \rightarrow
                \left\{
                    \begin{array}{lr}
                        128+105t\equiv 2\mod 3 \\
                        128+105t\equiv 3\mod 5 \\
                        128+105t\equiv 2\mod 7
                    \end{array}
                \right.
            \end{gathered}
        \end{equation}$
        $\hspace{1mm}$
        $\therefore$ 當 $t = -1, x = 23$
        
費馬小定理
---
- 功能：處理質數的餘數問題
- 理論
    > 條件一：如果 gcd(a, p) = 1，則 a^(p-1)^ ≡ 1 mod p
    > 條件二：p 須為質數
- 範例
    - $2^{100} \mod 13 \ ?$
    $2^{12} \equiv 1 \mod 13$
    $(2^{12})^8 \equiv 1^8 \mod 13$
    $(2^{12})^8 \times 2^4 \equiv 1^8 \times 2^4 \mod 13 \rightarrow 3$

- 補充：偽質數
    - 情況：當 p 不是質數，但 a^(p-1)^ ≡ 1 mod p 成立，此時稱 p 為偽質數
    - 範例
    $p = 341(11\times31)$
    若 $a^{340} \equiv 1 \mod 341$
    此時 $p$ 就稱為偽質數
    
歐拉定理
---
- 功能：用於處理互質的餘數問題
- 理論
    > 條件：如果 a, b 為互質的整數，則 a^φ(b)^ ≡ 1 mod b
    > 補充：φ(b) 指比 b 小且與 b 互質的整數
- 範例
    - 求 7^222^ 的個位數 
    $7^{\phi(10)} \equiv 1 \mod 10$
    $7^4 \equiv 1 \mod 10$
    $7^{222} = (7^4)^{55} \times 7^2 = 49 \mod 10 \rightarrow 9$

