Sumę można zapisać jako suma iloczynu liczby  i liczby całkowitej  oraz liczby , stąd ta liczba daje resztę  przy dzieleniu przez , co należało wykazać.