合同式

$$\forall a,b,n\in\Z;$$

$$a\equiv b\pmod{n}:\iff \exists k\in\Bbb{Z};a-b=kn$$

$$a$$と$$b$$を$$n$$で割った余りが等しいことを示す演算子

整数の問題を解くときにとても便利

$$a,b,n$$を実数に拡張すると円函数の周期計算に応用できるが、一部の性質が成り立たなくなるので注意

性質

推移律 $$a\equiv b\land b\equiv c\implies a\equiv c\pmod{n}$$

証明：$$\forall a,b,c,n\in\Z$$のとき、

$$a\equiv b\equiv c\pmod{n}$$

$$\iff\exists k,l\in\Z;a-b=kn\land b-c=ln$$

$$\implies \exists k,l\in\Z;a-c=(k+l)n$$

$$\implies \exists k\in\Z;a-c=kn$$

$$k+l$$を$$m$$に置き換えた後、変数名を$$m$$から$$k$$に変えた

$$\implies a\equiv c\pmod{n}$$

合同式の四則演算

#2022-02-24 18:04:35

#2021-12-14 20:20:59

#2021-06-14 16:21:52