Dokonajmy niezależnych losowań ze zbioru reszt z dzielenia przez zakładając przy tym, że prawdopodobieństwo wylosowania dowolnej z reszt jest równe Z uzyskanych reszt tworzymy zbiór Ponieważ losowania są niezależne, może on składać się z mniej niż reszt, gdyż pewna reszta mogła zostać wylosowana więcej niż jeden raz. Jeżeli spełniony jest jednak warunek, w którym co najmniej połowa reszt może być zapisana w postaci dla oraz to możemy dopełnić zbiór do zbioru -elementowego w dowolny sposób i warunek ten pozostanie spełniony.

Niech będzie liczbą reszt, które przystają do liczby postaci dla oraz Wystarczy udowodnić, że wartość oczekiwana zmiennej losowej wynosi co najmniej Ustalmy dowolną resztę Ponieważ zbiór składa się z elementów, więc istnieje dokładnie takich reszt że dla pewnego Prawdopodobieństwo tego, że ustalona reszta nie może być zapisana w żądanej postaci, wynosi zatem

Co za tym idzie, prawdopodobieństwo tego, że może być ona tak zapisana, wynosi Korzystając z definicji wartości oczekiwanej oraz nierówności dla dostajemy