1 互除法

互除法は、大きい方から小さい方を引くことを繰り返して最大公約数を求めます。ここでは \(a \gcd b\) を、次の漸化式（gcd𝕄）を満たす関数として仮定します。そのような関数が存在することは示しません。したがって、互除法が止まって値が決まること（そのような関数の存在）はこの本では示していません。主定理は「gcd𝕄 を満たす関数があれば、それは最大公約数」という形です。
\(a \gcd 0 = a\)、\(a \gcd b = b \gcd a\)、\((a + b) \gcd b = a \gcd b\)。
word(ss,s) … \(\gcd\)
gcd𝕄 … \(\begin{cases} a \in \mathbb{M} \Longrightarrow a \gcd 0 = a \\ a , b \in \mathbb{M} \Longrightarrow a \gcd b = b \gcd a \\ a , b \in \mathbb{M} \Longrightarrow ( a + b ) \gcd b = a \gcd b \end{cases}\)

1.1 公約数は最大公約数の約数

\(a \gcd b\) は自然数で、\(d\) が \(a\) と \(b\) を割ることと \(a \gcd b\) を割ることは同じ（K）。
\(a + b\) についての強い帰納法で示します。\(b = 0\) なら \(a \gcd 0 = a\)。\(a = c + b\) なら \(a \gcd b = c \gcd b\) で、公約数も同じ（0.book の ∣+・∣sub）。\(a < b\) なら入れ替えます。
K … \(a , b , d \in \mathbb{M} \Longrightarrow a \gcd b \in \mathbb{M} , ( d \mid a , d \mid b \Longleftrightarrow d \mid a \gcd b )\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，𝕄0s ，IND𝕄 ，suc𝕄 ，+𝕄 ，*𝕄 ，gcd𝕄

2 主定理

互除法で求めた \(a \gcd b\) は \(a\) と \(b\) の公約数で、どの公約数でも割り切れる＝最大公約数（K で \(d = a \gcd b\) とおく）。
\(a , b \in \mathbb{M} \Longrightarrow a \gcd b \mid a , a \gcd b \mid b , \forall d \in \mathbb{M} . ( d \mid a , d \mid b \Longrightarrow d \mid a \gcd b )\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，𝕄0s ，IND𝕄 ，suc𝕄 ，+𝕄 ，*𝕄 ，1. ，gcd𝕄