Теорема Эйзенштейна.

Пусть p,qÎN - взаимно простые нечетные числа. p'=(p-1)/2; q'=(q-1)/2. Тогда выполняется равенство: ([q/p]+[2q/p]+...+[p'q/p])+([p/q]+[2p/q]+...+[q'p/q])=p'q'.

Доказательство.

Возьмем систему координат и проведем в ней прямую y=qx/p. Будем рассматривать область с 0xp'; 0yq'. Заметим, что в этой области прямая qx/p не пересекает ни одной целой точки (1), т.к. НОД(p, q)=1. Учитывая (1), замечаем, что количество целых точек с абсциссой 1, лежащих под данной прямой, есть [q/p]. Аналогично заметим, что количество целых точек с абсциссой i, лежащих под данной прямой есть [iq/p] (i=1..p'). Поэтому число целых точек под прямой в данной области есть ([q/p]+[2q/p]+...+[p'q/p]). Учитывая (1), заметим, что число целых точек, лежащих над графиком, имеющих ординату 1, есть [p/q]. Аналогично заметим, что количество целых точек с ординатой i, лежащих над данной прямой, есть [ip/q] (i=1..q'). Поэтому число целых точек над прямой в данной области есть ([p/q]+[2p/q]+...+[q'p/q]). Отсюда всего целых точек над и под графиком в данной области ([q/p]+[2q/p]+...+[p'q/p])+([p/q]+[2p/q]+...+[q'p/q]). По (1) это число точек есть число всех целых точек в данной области, т.е. p'q', т.е. ([q/p]+[2q/p]+...+[p'q/p])+([p/q]+[2p/q]+...+[q'p/q])=p'q'.