単項生成可換モノイド

$f_x(0)=0$、$f_x(n)=nx$ と定めると、自然数倍の法則より
$$ f_x(m+n)=(m+n)x=mx+nx=f_x(m)+f_x(n) $$
だから準同型である。逆に $g\colon\mathbb N\to M$ が準同型で $g(1)=x$ を満たすなら、帰納法により
$$ g(n)=g(\underbrace{1+\cdots+1}_{n\text{ 個}})=nx $$
である。よって $g=f_x$ となる。$\blacksquare$

$M$ が $x$ で生成されるなら、前命題の $f_x(n)=nx$ は全射である。逆に $f\colon\mathbb N\twoheadrightarrow M$ があれば、任意の $y\in M$ はある $n\in\mathbb N$ によって $y=f(n)=nf(1)$ と表せる。したがって $M$ は $f(1)$ で生成される。$\blacksquare$

反射律と対称律は定義から明らかである。$a\sim_{r,d}b$ かつ $b\sim_{r,d}c$ とする。いずれかの等号を除けば $a,b,c\ge r$ かつ $a\equiv b\equiv c\pmod d$ なので $a\sim_{r,d}c$ であり、推移律が成り立つ。
さらに $a\sim_{r,d}b$ と $n\in\mathbb N$ に対し、$a=b$ なら $a+n=b+n$ である。それ以外なら $a,b\ge r$ かつ $d\mid(a-b)$ だから、$a+n,b+n\ge r$ かつ $d\mid((a+n)-(b+n))$ である。よって $a+n\sim_{r,d}b+n$ となり、加法と両立する。$\blacksquare$

$R$ が等号関係でないとする。異なる二数を同一視する組のうち小さい方の最小値を $r$ とする。次に
$$ d=\min\{k\ge1\mid r\mathrel R r+k\} $$
と定める。この集合が空でないことは $r$ の定義から従う。
$r\mathrel R r+d$ と加法との両立性より、任意の $a\ge r$ について $a\mathrel R a+d$ である。したがって $a,b\ge r$ かつ $d\mid(b-a)$ なら $a\mathrel R b$ であり、$\sim_{r,d}\subseteq R$ を得る。
逆に $a\mathrel R b$ とし、$a< b$ とする。$r$ の最小性より $a\ge r$ である。$b-a=qd+s$、$0\le s< d$ とEuclid除法する。上で示した周期性から $a\mathrel R a+qd$ であり、ゆえに
$$ a+qd\mathrel R b=a+qd+s $$
である。もし $s>0$ なら、十分大きな $k$ を選んで $r+kd\ge a+qd$ とし、この関係へ $r+kd-(a+qd)$ を加えると
$$ r+kd\mathrel R r+kd+s $$
を得る。一方、周期性より $r\mathrel R r+kd$ および $r+s\mathrel R r+s+kd$ であるから、推移律により $r\mathrel R r+s$ となる。これは $0< s< d$ と $d$ の最小性に反する。従って $s=0$ であり、$d\mid(b-a)$ である。よって $R\subseteq\sim_{r,d}$ となる。
最後に、$r$ は非自明な同値類に現れる最小の自然数、$d$ は $r$ と同値なより大きい自然数との差の最小値として $R$ から復元される。したがって $(r,d)$ は一意である。$\blacksquare$

生成元 $x$ を選び、全射 $f_x\colon\mathbb N\twoheadrightarrow M$ を取る。核合同関係が等号なら $f_x$ は単射でもあるため $M\cong\mathbb N$ である。核合同関係が等号でなければ、前定理より一意な $(r,d)$ に対して $\ker f_x=\sim_{r,d}$ となる。第一同型定理から
$$ M\cong\mathbb N/{\sim_{r,d}}=C_{r,d} $$
を得る。$\blacksquare$