初等数论--整除--带余除法

• 概念
• 基本性质
• 带余除法

博主本人是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。
我整理成一个系列：初等数论，方便检索。

概念

$初等数论研究对象是整数集合和自然数集合。$

$b|a:若a,b\in \mathbb{Z},b\ne 0，\exists c\in \mathbb{Z},使a=bc,则称b整除a。$

基本性质

1.$b|a\leftrightarrow (-b)|a\leftrightarrow b|(-a)\leftrightarrow (-b)|(-a)\leftrightarrow |b|||a|$
2.$a\ne 0且b|a\to |b|\le |a|$
3.$a|b且b|c\to a|c$
4.$a|b且b|a\to |a|=|b|,b=\pm a$
5.$a|b且a|c\to a|bt+cs,\forall t,s\in \mathbb{Z}$
6.$设m\ne 0,b|a\to mb|ma$

带余除法

$设a,b是两个给定的整数，b>0，则必定存在唯一的一对整数q、r，满足a=qb+r,0\le r<b证明：存在性+唯一性$

• $存在性$
  $$\begin{gathered} 我们已知整数序列\dots -3b,-2b,-b,0,b,2b,3b\dots ，a必定满足qb\le a\le (q+1)b，我们令r=a-qb，则 \\ qb-qb\le a-qb<(q+1)b-qb,即0\le r<b \end{gathered}$$
• $唯一性$
  $$\begin{gathered} 反证法：假设还存在一对整数q‘、r’，满足a=q^{\prime }b+r^{\prime },0\le r^{\prime }<b,则有 \\ a=qb+r,a=q^{\prime }b+r^{\prime },联立二式得到 \\ (q-q^{\prime })b=r^{\prime }-r, \\ 因为0\le r^{\prime },r<b,所以0\le |r^{\prime }-r|<b, \\ 因此|q-q^{\prime }|<1。 \\ 又因为q和q^{\prime }都是整数，所以q=q^{\prime }，所以r=r^{\prime } \end{gathered}$$

总结

以上是生活随笔为你收集整理的初等数论--整除--带余除法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。