Bézout Theorem

Theorem :
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.

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Française Previous topic Next topic