互いに素な整数

定義

$ a, b \in \mathbb{Z} が次を満たすとき、$ a, bは互いに素という。

最大公約数$ \gcd (a, b) = 1 ($ \Leftrightarrow a, b は共通の素因数を持たない)

性質

$ a, b が互いに素ならば、

$ 0, a, 2a, \dots, (b-1)a を$ b で割った余りはすべて異なる(互いに素な整数の剰余定理)。

$ ax + by は整数全体を動く。

$ ax \equiv ay (\bmod b) ならば$ x \equiv y (\bmod b)である。

ここまでは逆も成り立つ

$ ax + by = c は整数解を持つ(ベズーの等式)。

$ ax = c (\bmod b) は整数解を持つ(一次合同方程式が解を持つ条件)。

例

$ \gcd(5, 7) = 1

$ 5 \cdot 3 + 7 \cdot (-2) = 1

証明

$ \gcd(1, a) = \gcd(a, by) = 1

$ \gcd(1, b) = \gcd(b, ax) = 1