Лемма. Пусть D  — не­ко­то­рое мно­же­ство раз­лич­ных про­стых де­ли­те­лей числа Ко­ли­че­ство на­ту­раль­ных чисел, не пре­вос­хо­дя­щих n и не крат­ных ни од­но­му числу из L равно

До­ка­за­тель­ство. Рас­крыв скоб­ки, по­лу­ча­ем фор­му­лу вклю­че­ний-ис­клю­че­ний. Пусть крас­ных чисел боль­ше Тогда не­ко­то­рые крас­ные числа имеют с n общий про­стой де­ли­тель. Пусть q  — наи­боль­шее из таких про­стых и a  — крас­ное число, крат­ное Чтобы по­лу­чить про­ти­во­ре­чие до­ста­точ­но найти раз­лич­ные крас­ные числа b и c, срав­ни­мые по мо­ду­лю а для этого до­ста­точ­но по­ка­зать, что боль­ше ко­ли­че­ства воз­мож­ных остат­ков крас­ных чисел по мо­ду­лю

По лемме,

где D  — мно­же­ство всех про­стых де­ли­те­лей числа n, а ука­зан­ное ко­ли­че­ство остат­ков не боль­ше, чем

Итак, до­ста­точ­но до­ка­зать не­ра­вен­ство

Со­кра­щая на n и на скоб­ки, в ко­то­рых по­лу­ча­ем

что рав­но­силь­но не­ра­вен­ству

Оно верно, по­сколь­ку