Wiemy, iż największy wspólny dzielnik liczby i liczby jest równy . 

Rozkładając na czynniki pierwsze liczbę mamy:

Skoro największy wspólny dzielnik to , pomijamy z rozkładu i . 

Wobec tego