Let \(d = (a, m)\) and \(h = (b, m)\). If \(a ≡ b \bmod m\), then there is an integer \(k\) such that:
Since \(d|m\), then \(\frac{mk}{d} \in \mathbb{Z} \), and since \(d|a\), then \(\frac{a}{d} \in \mathbb{Z} \). That means \(\frac{b}{d}\) is also an integer. Therefore \(d|b\):
Since \(h = (b, m)\), then \(h\) is the smallest positive linear combination of \(b\) and \(m\). Since \(d|b\) and \(d|m\), then \(d\) divides any linear combination of \(b\) and \(m\). Therefore \(d|h\).
Going back to \(mk + a = b\), we can rearrange it as:
Dividing both sides by \(h\):
Since \(h|m\), then \(\frac{mk}{h} \in \mathbb{Z} \), and since \(h|b\), then \(\frac{b}{h} \in \mathbb{Z} \). That means \(\frac{a}{h}\) is also an integer. Therefore \(h|a\):
Since \(d = (a, m)\), then \(d\) is the smallest positive linear combination of \(a\) and \(m\). Since \(h|a\) and \(h|m\), then \(h\) divides any linear combination of \(a\) and \(m\). Therefore \(h|d\).
Since \(h|d\) and \(d|h\), then \(d=h\).