# 二階數學補充-同餘

事前聲明
:::danger
以下英文代號所表示的數
若無特別說明
請視為整數 $\mathbb{Z}$
:::

## 帶餘數ㄉ除法
欸我不知道為什麼會變這樣
反正那個倒三角形跟點點$\div$
原本是除號

被除數$\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 {state="open"}**求所有非負整數a,b滿足 2^a-3^b=1**
好像離題了(X
提示: mod 8
:::

## 電資考古題解說

### EC2107 (同餘加速窮舉)
在窮舉的過程 把數列的每一項都壓到0~9的範圍
讓每一項數字都不會太大

$a_1=1$
$a_2=3$
$a_3=3\times3-7\times1=2\equiv2$
$a_4=3\times2-7\times3=-15\equiv5$
$a_5=3\times5-7\times2=1\equiv1$
$a_6=3\times1-7\times5=-32\equiv8$
$a_7=3\times8-7\times1=17\equiv7$
$a_8=3\times7-7\times8=-35\equiv5$
$a_9=3\times5-7\times7=-34\equiv6$
$a_{10}=3\times6-7\times5=-17\equiv3$
$a_{11}=3\times3-7\times6=-33\equiv7$
$a_{12}=3\times7-7\times3=0\equiv0\rightarrow12$個一循環
$a_{13}=3\times0-7\times7=-49\equiv1$
$a_{14}=3\times1-7\times0=3\equiv3$

### EC2005 (費馬小定理秒殺)
$5^{2020}\equiv(5^{10})^{202}\equiv1^{202}\equiv1$

### EC1901(2) (基本練習)
$1211\times7725\equiv1\times3\equiv3$

### CS1103

### CS1116

### CS0902

### CS0903

### CS0904

### CS0811

### CS0812

### CS0201

## 延伸應用(有空再講)
- 歐拉定理(數論的 , 不是幾何)&費馬小定理
- 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: `電資二階` `Cosmos`