>The generalization of Euclid's theorem states let m|ab and
>gcd(a, m) = 1. Then m|b.

The link is wrong. Please accept my apologies. You have to look a couple of paragraphs up on that page.

For coprime a and b, there are s and t s.t. as + bt = 1 so that as = 1 (mod b) is solvable.