זר ל- , ולכן כל המספרים בקבוצה שונים זה מזה מודולו .
נחלק את איברי הקבוצה ב- עם שארית, ונקבל:
-
תהיינה שאריות החילוק הקטנות מ- , ותהיינה שאריות החילוק הגדולות מ- .
מן הלמה של גאוס נובע כי המספרים שווים לאיברים בסדר כלשהו.
-
נחסר את שתי המשוואות זו מזו ונקבל:
-
המספרים אי-זוגיים ולכן זוגי. לכן
-
כאשר השורה האחרונה על-פי הלמה של גאוס.