[数论笔记]1.整除
本文最后更新于 279 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/numbertheory1/

前言

笔者最近开始学习 OI 需要的数论……
本系列为学习笔记。

参考教材:《信息学奥赛之数学一本通》 (林厚雄)

整除

定义

整除,设 $a$ 为非零整数, $b$ 为整数, $q$ 为整数。
若有 $b = a * q$,则 $b$ 被 $a$ 整除, $a$ 整除 $b$,$a$ 是 $b$ 的因子。
记作 $a|b$。

性质

整除的一些性质。

1. 若 $a | b$,$b | c$,则 $a | c$。

证明:设 $b = a \times q_1$,$c = b \times q_2$,则 $c = a \times q_1 \times q_2$,即 $a | c$。

2. 若 $a | b$,$a | c$,则对于任意整数 $x$,$y$ 有 $a | (b \times x + c \times y)$。

证明:设 $b = a \times q_1$,$c = a \times q_2$,则 $b \times x + c \times y$ 等价于 $a \times (q_1 \times x \times q_2 \times y)$,则 $a | (b \times x + c \times y)$。

3. 设 $m \ne 0$,若有 $a | b$,则有 $(m \times a) | (m \times b)$。

证明:设 $b = a \times q$,则原式等价于 $(m \times a) | (m \times a \times q)$。

4. 设整数 $x,y$ 满足:$a \times x + b \times y = 1$ 且有 $a | n,b | n$,则 $(a \times b) | n$。

证明:
根据 性质3 由 $a | n,b | n$ 有 $(a \times b) | (a \times n),(a \times b) | (b \times n)$。
根据 性质2 有 $(a \times b) |((a \times n) \times x + (b \times n) \times y)$。
化简得 $(a \times b) | n \times (a \times x + b \times y)$,其中 $a \times x + b \times y = 1$。
得原式 $(a \times b) | n$。

5. 若 $b = q \times d + c$,则 $d | b$ 的充要条件为 $d | c$。

证明:$b = q \times d + \frac{c}{d} \times d$,则 $\frac{c}{d}$ 为整数时 $d | b$,此时 $d | c$。

例题

由于书上的例题跟整除没有什么关系,并且后一道题涉及到更为困难的知识,笔者现在还未掌握,故照搬书上内容。

Church

ProblemChurch

ProblemChurchSolution

StrongBox

ProblemStrongBox

ProblemStrongBoxSolution1

ProblemStrongBoxSolution2

ProblemStrongBoxCode1

ProblemStrongBoxCode2

由于笔者水平不足,在阅读本题题解时遇到许多困难,因此本题笔者亦想补充一点讲解……

二元一次不定方程一般形式为 $a \times x + b \times y = c$,其中 $a,b,c$ 为整数,$a \times b \ne 0$。

方程有整数解的充要条件为 $\gcd (a,b) | c$,这个定律叫做裴蜀定理
笔者不会证,暂且背下来了。

设 $x_0,y_0$ 为该方程的一组整数解,则所有整数解可表示为:

$$x = x_0 + \frac{b}{\gcd(a,b)} \times t,y = y_0 – \frac{a}{\gcd(a,b)} \times t$$

证明如下:
原式等价于

$$\frac{a}{\gcd(a,b)} \times x + \frac{b}{\gcd(a,b)} \times y = \frac{c}{\gcd(a,b)}$$

$$\frac{a}{\gcd(a,b)} \times x = \frac{c}{\gcd(a,b)} – \frac{b}{\gcd(a,b)} \times y$$

将式子看做关于 $x$ 的方程,由于该式中自变量只有 $y_0$,且系数为 $\frac{b}{\gcd(a,b)}$。
因此设 $x = x_0 + \frac{b}{\gcd(a,b)} \times t$。

代入原式,有:

$$\frac{a}{\gcd(a,b)} \times x_0 + \frac{a}{\gcd(a,b)} \times \frac{b}{\gcd(a,b)} \times t = \frac{c}{\gcd(a,b)} – \frac{b}{\gcd(a,b)} \times y$$

移项整理得:

$$\frac{a}{\gcd(a,b)} \times x_0 + \frac{b}{\gcd(a,b)} \times (y + \frac{a}{\gcd(a,b)} \times t) = \frac{c}{\gcd(a,b)}$$

已知:

$$\frac{a}{\gcd(a,b)} \times x_0 + \frac{b}{\gcd(a,b)} \times y_0 = \frac{c}{\gcd(a,b)}$$

解得此时:

$$y = y_0 – \frac{a}{\gcd(a,b)} \times t$$

命题得证。
剩下的内容大概能看懂了,就不写了。

本文标题:[数论笔记]1.整除
本文作者:Clouder
本文链接: https://www.codein.icu/numbertheory1/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇