Załóżmy, że liczby oraz mają wspólny dzielnik większy od . Oznaczmy go . Zachodzi więc .

Skoro jest dzielnikiem liczby , to , gdzie jest pewną liczbą naturalną.

Skoro jest dzielnikiem