Элементарная теория сумм Гаусса
Элементарная теория сумм Гаусса
Рассмотрим следующую сумму – сумму Гаусса :
где D – целое положительное и (a, D)=1.
Покажем, что значение суммы будет одним и тем же, если х
пробегает любую полную систему вычетов по модулю D.
Действительно, пусть х пробегает полную систему вычетов по
модулю D. Тогда х=qD+k ,
где k =0, 1, …, D-1 , q є Z
Будем иметь :
что и требовалось.
Лемма 1.
Пусть (a, D)=1. Тогда:
Доказательство:
По свойству модуля комплексного числа :
Имеем:
Сделаем замену x = x + t . Когда х и х пробегают
полную систему вычетов по модулю D , от х и t пробегают независимо полные
системы вычетов по модулю D.
Действительно, пусть х и х пробегают полную систему
вычетов по модулю D . Тогда х = qD + k k=0,
1, …, D-1 , q є Z
х = pD +
i i=0, 1, …, D-1 , p є Z
Следовательно,
t = x – x = (q – p)D + (k – i) = l D + m , где m=0, 1, …, D-1 , l є Z
а)
Пусть D – нечетное, т.е. (2а, D)=1
если
D делит t.
Если
же D не делит t, то последнюю сумму можно записать в виде :
Получили
:
Тогда
Отсюда
б)
Пусть D делится на 4, т.е. возможно представление : D = 2D , где D –
четное и ( a, D )=1 .
Получим
:
Так
как D четное, то
Следовательно
в)
Пусть D = 2 (mod 4) , т.е. D = 4q + 2 , q є Z
Тогда
из предыдущего случая имеем : D = 2 (2q+1)= 2D , D - нечетное. Имеем :
Что и требовалось.
Лемма
2.
Если
D и D взаимно простые числа, то
S ( aD1 ,
D2 ) S ( aD2 , D1 ) = S ( a , D1
D2 )
Доказательство:
В
этих суммах t1 пробегает полную систему вычетов по модулю D2
, а t2 пробегает полную систему вычетов по модулю D2. При
этом D1t1 + D2t2 пробегает полную
систему вычетов по модулю D1D2 . Действительно , всего
членов в сумме D1D2 и никакие два несравнимы между
собой. Действительно, предположим противное : пусть D1t1
+ D2t2 = D1t1 + D2t2
( mod D1D2 )
Отсюда
D1 (t1 – t1) = D2 (t2 –
t2 ) (mod D1D2) Тогда
D1 (t1 – t1) = D2 (t2 –
t2 ) (mod D2) А так как D2 (t2
– t2 ) = 0 (mod D2)
То
по свойству сравнений имеем D1 (t1 – t1)
= 0 (mod D2) Отсюда так как (D1, D2)=1 ,
то t1 – t1 = 0 (mod D2) Аналогично
получим t2 – t2 = 0 (mod D1)
Т.е.
имеем t1 = t1 (mod D2)
и t2 = t2 (mod D1) . Но это
противоречит тому, что t1 пробегает полную систему вычетов по
модулю D2 , а t2 пробегает полную систему вычетов по
модулю D2, так как в полной системе вычетов любые два числа не
сравнимы. Следовательно наше предположение было неверным и действительно D1t1
+ D2t2 пробегает полную систему вычетов по модулю
D1D2 .
Поэтому
Лемма
3.
Пусть
p простое нечетное число и не делит a . Тогда
Доказательство:
что и требовалось
доказать.
-6-
Лемма
4.
Если
р простое нечетное число , то
Доказательство :
Из
леммы 3. получим
Так
как произведение сопряженных величин дает квадрат модуля, то
Лемма
5.
Если
р и q различные простые числа , то
Доказательство :
Так
как ( р, q )= 1 , мы можем воспользоваться леммой 2 : в нашем случае
Итак
, мы показали, что
что и требовалось
доказать.