# 數論-同餘
本課程幾乎不用寫程式
努力理解內容在幹嘛就好：)
加油
:::danger
以下英文代號所表示的數
若無特別說明
請視為整數 $\mathbb{Z}$
:::
## 帶餘數ㄉ除法
被除數$\div$除數$=$商數$...$餘數

$48763\div 5=9752...3$
$3\div 5=0...3$
::: success
除數一樣 餘數也一樣耶
:::
## 同餘
### 定義
當兩數 $a,b$ 除以 $n$ 的餘數一樣時
我們說
==$a$ 和 $b$ 在模 $n$ 下同餘==
記做
==$a\equiv b$ (mod $n$)==

### 一些小性質
假設四數$a\equiv b$ (mod $n$) , $c\equiv d$ (mod $n$)
- $n\mid a-b$
- $a\pm c\equiv b\pm d$
- $ac\equiv bd$

### 熟悉一下
:::spoiler {state="open"}**完全平方數只有6種個位數**
枚舉0~9即可
:::
:::spoiler {state="open"}**證明 : 一個完全平方數的各位數字和不可能是2021**
設命題成立
則$x^2\equiv 2$ (mod $3$)
但平方數除以3餘數不會是2
故命題不成立
:::
:::spoiler **求所有非負整數a,b滿足 2^a-3^b=1**
好像離題了(X
提示: mod 8
:::

## 模逆元
### 回顧一下
\---------------------------------------------
\---------------------------------------------
:::success
好像沒看到除法耶 是不是不能除?
:::

### 除法與倒數
> $a\div b$ 可以視為 $a\times\dfrac{1}{b}$

### 倒數與模逆元
自身和倒數相乘之積為1
> $b\times\dfrac{1}{b}=1$

假設$b$ 在模 $n$ 下的模逆元是 $t$ , 則 $t$ 有一些性質...
> $bt\equiv 1$ (mod $n$)

> $t$ 在模 $n$ 下==唯一==

我懶得寫證明XD反正很簡單 大家可以自己試看看

> 0的模逆元==不存在==(不論是模誰都不存在)

應該挺顯然的(?

### 模逆元的存在性
**什麼時候$b^{-1}$ (mod $n$)存在?**
:::spoiler 一些無聊的過程
若$t\equiv b^{-1}$ (mod $n$)
則$n|bt-1$
$\Rightarrow$存在 $k$ 使得 $nk=bt-1$
:::
$\Rightarrow$若 $bt-nk=1$ 存在整數解 $(t,k)$ , 則此模逆元存在

那問題還是沒解決阿
**什麼時候存在整數解?**
這時候就要請出一個酷酷的==貝祖引理==
> 對於整數$a,b,c$, 以下兩件事等價
> 1. $\gcd(a,b)|c$
> 2. 存在$x,y$ 滿足 $ax+by=c$

注意:我們在這裡定義$\gcd(a,0)=a$

:::spoiler 證明2可以推到1?(簡單)
$\gcd(a,b)|a|ax$
$\gcd(a,b)|b|by$
所以
$\gcd(a,b)|ax-by=c$
:::
:::spoiler 證明1可以推到2?(難到靠北)
\---------------------------------------
$b=0$顯然
:+1:
好啦我還是打一下算式
$b=0\Rightarrow a=\gcd(a,b)\Rightarrow a|c$
則我們有$a*\dfrac{c}{a}+b*0=c$
\---------------------------------------
$b>0$時 , 令$a=bq+r$ ($0\le r<b$)
則改求$bx'+ry'=c$的整數解
若$r\not=0$則繼續輾轉下去直到$r=0$
套用上面$b=0$的結論
$bx'+(a-bq)y'=c$
$ay'+b(x'-qy')=c$
即滿足2的條件
\---------------------------------------
:::
\
結論：==$b^{-1}$ (mod $n$) 存在 若且唯若 $\gcd(b,n)=1$==
:::warning
雖然筆者覺得1的模逆元存在
但普遍似乎認為==不存在==
請大家注意
:::

## (擴展)歐幾里得
### 歐幾里得算法
aka==輾轉相除法==

用於求最大公因數
$\gcd(a,b)=\gcd(a,b\%a)$
- $O(\log(\max(a,b)))$
- worst case:費氏數列相鄰項

int gcd(int a, int b) {
    return __gcd(a,b);
}

記得要include algorithm
雖然現在人都一言不合就bits/stdc++.h

### extend-歐幾里得
範例code:求12在模7下的模逆元

#include<bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

pii exgcd(int a, int b){
    if(b==0) return make_pair(1,0);
    pii p = exgcd(b,a%b);
    return make_pair(p.second, p.first-a/b*p.second);
}

int main(){
    cout<<exgcd(12,7).first;
    return 0;
}

解釋:
函式exgcd(a,b)會回傳$ax+by=\gcd(a,b)$的一組解
但要怎麼拿到呢?
我們嘗試取得exgcd(b,a%b)
則它滿足
$bx+(a-a/b*b)y=\gcd(a,b)$
$bx+ay-a/b*by=\gcd(a,b)$
$ay+b(x-a/b*y)=\gcd(a,b)$
$\Rightarrow(y,x-a/b*y)$是$ax+by=\gcd(a,b)$的一組解!
- $O(\log(\max(a,b)))$
- worst case:費氏數列相鄰項

## 習題們
[TIOJ 1040 輾轉相除法](https://tioj.ck.tp.edu.tw/problems/1040)
[ZJ a289 模逆元](https://zerojudge.tw/ShowProblem?problemid=a289)

## 延伸應用(有空再講)
- 歐拉定理(數論的 , 不是幾何)&費馬小定理
- CRT(中國剩餘定理) (ex.2019TOI初選)
- 二次剩餘
- 密碼學

## 歐拉歐拉歐拉
### 暖身一下
:::spoiler {state="open"}有多少個小於10的正整數和10互質?
1, 3, 7, 9
共4個
:::
:::spoiler {state="open"}有多少個小於1000的正整數和1000互質?
1, 3, 7, 9, ...
共400個
:::
:::spoiler {state="open"}有多少個小於48763的正整數和48763互質?
1, 2, 3, 4, ...
共39600個
:::

### 歐拉函數
我們定義$\phi(n)$代表小於n的正整數中 , 與n互質的數的數量
我們有
> $\phi(n)=(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...$
> 其中$p_i$為$n$的質因數

證明?
不重要。
後面學到CRT之後可以試看看
或是直接看wiki
我就懶:+1:

### 歐拉定理
> $a^{\phi(n)}\equiv1$ (mod $n$)

證明需要用到一個酷東西叫「既約剩餘系」
所以就不講ㄌ

## 費馬大小定理(FLT)
先觀察一下
> 一個整數$a$ , 要嘛被質數$p$整除 , 要嘛與它互質

於是FLittleT就跑出來了

### Fermat's Little Theorem
對所有質數$p$ , 若整數$a$不是$p$的倍數 , 則
> $a^{p-1}\equiv1$ (mod $p$)

而對於所有整數$a$
> $a^p\equiv a$ (mod $p$)

### 小推論
對所有質數$p$ , 若整數$a$不是$p$的倍數 , 則
> $a^{-1}\equiv a^{p-2}$ (mod $p$)

### Fermat's Last Theorem
by 維基
放好看的
不用記

### 小練習
但不適合現在練
[M費氏數列](https://vjudge.net/contest/436565#problem/R)

:::success
歐拉定理與FLT可以大幅降低大數取模的困難度
:::

## 中國剩餘定理(CRT)
### 暖身
:::spoiler {state="open"}基本版 韓信點兵
有$k$個士兵
3個一排剩1個
5個一排剩2個
7個一排剩4個
若$k<105$
請問$k=?$
:::
:::spoiler 國中解答
k=3a+1
=3(5b+2)+1
=3[5(7c+5)+2]+1
=105c+67

A:67
:::

### 定理內容
> 若$n_1,n_2,...,n_m$為m個==兩兩互質==的正整數
> 且$x_1,x_2,...,x_m$為m個的整數
> 則必存在一個整數$x$滿足
> $x\equiv x_i$ (mod $n_i$) $\forall1\le i\le m$ (存在性)
> 且若$x$和$x'$皆滿足條件
> 則$x\equiv x'$ (mod $n_1n_2...n_m$) (唯一性)

###### tags: `MDCPP` `Cosmos`