Two integers a and b are coprime if and only if there are two integers u and v ∈ Z with a.u + b.v = 1

This theorem applies to much other rings than the set Z of integers.

Proof :

1) If au+bv = 1, the GCD p of a and b divides au+bv hence it is 1.

2) Conversely if a and b non null are coprime, consider the set E
of numbers a.u + b.v and more precisely the set F of these a.u + b.v > 0.
There is at least one element, for instance a = a×1 + b×0.

Let's call p the smallest one and divide a by p :
a = p.q + r 0≤r<p.

r = a - p.q = a - (a.u + b.v)q E.
This remainder r is in fact 0 because else rF hence
r≥p.

Hence p divides a,
and similarily p divides b.
Hence p = 1 and there are u and v with a.u + b.v = 1.

QED

Note : A constructive proof (allowing to calculate effectively u and v) uses
the Euclid algoritrhm.