數論入門

持續更新中....

轉載請聲明出處

目錄說：我在右邊

看了好多人的部落格都不太全，勵志做出最全的數論知識

持續更新中...

前置知識

整除

計數原理

同餘

質數與約數

質數與合數

篩法

約數個數定理與約數和定理

淺談gcd與exgcd

gcd與exgcd

裴蜀定理

逆元

線性同餘方程

形如\(ax \equiv c \ (mod \ b)\)的方程，稱為線性同餘方程，

等價于\(ax + by=c\), 是以有解條件為 \((a,b) \mid c\)

若 \(gcd(a,b) = 1\)，則 \(x\) 有唯一解 \(x ≡ a^{−1} \ c(mod \ b)\)。

否則設 \(gcd(a,b) = d,a = a ′ d,b = b ′ d,c = c ′ d\)

那麼有 \(a ′ x + b ′ y = c ′\) ，即 \(a ′ x ≡ c ′ (mod \ b ′ )\)

這裡 \(gcd(a ′ ,b ′ ) = 1\)，是以有 \(x ≡ (a ′ ) ^{−1} c ′ (mod b ′ )\)

綜上，任意的線性同餘方程總可以判定為無解，或化為 \(x ≡ a(mod \ m)\) 的形式。

中國剩餘定理

歐拉函數與歐拉定理