博主本人是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。 我整理成一个系列：初等数论，方便检索。
初 等 数 论 研 究 对 象 是 整 数 集 合 和 自 然 数 集 合 。 初等数论研究对象是整数集合和自然数集合。 初等数论研究对象是整数集合和自然数集合。
b ∣ a : 若 a , b ∈ Z , b ≠ 0 ， ∃ c ∈ Z , 使 a = b c , 则 称 b 整 除 a 。 b|a : 若a,b\in\mathbb Z,b\neq0，{\exists}c\in\mathbb Z,使a=bc,则称b整除a。 b∣a:若a,b∈Z,b=0，∃c∈Z,使a=bc,则称b整除a。
1. b ∣ a ↔ ( − b ) ∣ a ↔ b ∣ ( − a ) ↔ ( − b ) ∣ ( − a ) ↔ ∣ b ∣ ∣ ∣ a ∣ b|a\leftrightarrow (-b)|a\leftrightarrow b|(-a)\leftrightarrow (-b)|(-a)\leftrightarrow |b|||a| b∣a↔(−b)∣a↔b∣(−a)↔(−b)∣(−a)↔∣b∣∣∣a∣ 2. a ≠ 0 且 b ∣ a → ∣ b ∣ ≤ ∣ a ∣ a\neq0且b|a\rightarrow |b|\le|a| a=0且b∣a→∣b∣≤∣a∣ 3. a ∣ b 且 b ∣ c → a ∣ c a|b且b|c\rightarrow a|c a∣b且b∣c→a∣c 4. a ∣ b 且 b ∣ a → ∣ a ∣ = ∣ b ∣ , b = ± a a|b且b|a\rightarrow |a|=|b|,b=\pm a a∣b且b∣a→∣a∣=∣b∣,b=±a 5. a ∣ b 且 a ∣ c → a ∣ b t + c s , ∀ t , s ∈ Z a|b且a|c\rightarrow a|bt+cs,\forall t,s\in\mathbb Z a∣b且a∣c→a∣bt+cs,∀t,s∈Z 6. 设 m ≠ 0 , b ∣ a → m b ∣ m a 设m\neq 0,b|a\rightarrow mb|ma 设m=0,b∣a→mb∣ma
设 a , b 是 两 个 给 定 的 整 数 ， b > 0 ， 则 必 定 存 在 唯 一 的 一 对 整 数 q 、 r ， 满 足 a = q b + r , 0 ≤ r < b 证 明 ： 存 在 性 + 唯 一 性 设a,b是两个给定的整数，b>0，则必定存在唯一的一对整数q、r，满足a=qb+r,0\le r<b 证明：存在性+唯一性 设a,b是两个给定的整数，b>0，则必定存在唯一的一对整数q、r，满足a=qb+r,0≤r<b证明：存在性+唯一性
存 在 性 存在性 存在性 我 们 已 知 整 数 序 列 … − 3 b , − 2 b , − b , 0 , b , 2 b , 3 b … ， a 必 定 满 足 q b ≤ a ≤ ( q + 1 ) b ， 我 们 令 r = a − q b ， 则 q b − q b ≤ a − q b < ( q + 1 ) b − q b , 即 0 ≤ r < b 我们已知整数序列{…-3b,-2b,-b,0,b,2b,3b…}，a必定满足qb\le a\le (q+1)b，我们令r=a-qb，则\\qb-qb\le a-qb< (q+1)b-qb,即0\le r<b 我们已知整数序列…−3b,−2b,−b,0,b,2b,3b…，a必定满足qb≤a≤(q+1)b，我们令r=a−qb，则qb−qb≤a−qb<(q+1)b−qb,即0≤r<b 唯 一 性 唯一性 唯一性 反 证 法 ： 假 设 还 存 在 一 对 整 数 q ‘ 、 r ’ ， 满 足 a = q ′ b + r ′ , 0 ≤ r ′ < b , 则 有 a = q b + r , a = q ′ b + r ′ , 联 立 二 式 得 到 ( q − q ′ ) b = r ′ − r , 因 为 0 ≤ r ′ , r < b , 所 以 0 ≤ ∣ r ′ − r ∣ < b , 因 此 ∣ q − q ′ ∣ < 1 。 又 因 为 q 和 q ′ 都 是 整 数 ， 所 以 q = q ′ ， 所 以 r = r ′ 反证法：假设还存在一对整数q‘、r’，满足a=q'b+r',0\le r'<b,则有\\a=qb+r,a=q'b+r',联立二式得到\\(q-q')b=r'-r,\\因为0\le r',r<b,所以0\le|r'-r|<b,\\因此|q-q'|<1。\\又因为q和q'都是整数，所以q=q'，所以r=r' 反证法：假设还存在一对整数q‘、r’，满足a=q′b+r′,0≤r′<b,则有a=qb+r,a=q′b+r′,联立二式得到(q−q′)b=r′−r,因为0≤r′,r<b,所以0≤∣r′−r∣<b,因此∣q−q′∣<1。又因为q和q′都是整数，所以q=q′，所以r=r′