Niech i oraz
Jeżeli to a więc Zatem dla twierdzenie jest prawdziwe.
Niech teraz
Przez oznaczmy zbiór liczb należących do pierwszych względem i mniejszych lub równych
Niech dla każdego oznacza resztę z dzielenia liczby przez
Niech
Udowodnimy, że W tym celu wystarczy pokazać, że: dla każdej liczby gdzie zachodzi i jest względnie pierwsza względem (czyli ), funkcja opisana wzorem gdzie jest różnowartościowa (wtedy zbiory i byłyby równoliczne, gdyż jest z definicji surjekcją),
bowiem zbiory i są skończone (a więc nie mogą być równoliczne ze swoimi podzbiorami właściwymi).
Liczby są resztami z dzielenia przez więc są większe lub równe i mniejsze od
Jest też zawsze: a więc: dla i
Ponieważ zarówno jak i są względnie pierwsze względem to również ma tę własność. Załóżmy, że pewna liczba całkowita dzieli zarówno jak i Ze wzoru wynika, że musi być równe a więc i muszą być względnie pierwsze.