Символ Лежандра.
a. Введём в рассмотрение символ Лежандра ap (читается: символ а по отношению к р). Этот символ определяется для всех а, не делящихся на р; он равен 1, если а-квадратичный вычет, и -1, если а-квадратичный невычет. Число а называется числителем, р-знаменателем символа.
b. Ввиду e, очевидно, имеем
ap≡ap-12mod p.
c. Здесь мы выведем главнейшие свойства символа Лежандра и вследующем параграфе-свойства обобщения этого символа-символа Якоби, которые позволят быстро вычислять этот символ, а следовательно, решать вопрос о возможности сравнения
x2=amod p.
d. Если a≡a1mod p, то ap=a1p.
Это свойство следует из того, что числа одного и того же класса будут одновременно квадратичными вычетами или невычетами.
e. 1p=1.
Действительно, 1=12 и, следовательно, 1-квадратичный вычет.
f.-1p=-1p-12.
Это свойство следует из b при a=-1.
Так как p-12 четное, если р вида 4m+1, и нечётное, если р вида 4m+3, то отсюда следует, что -1 является квадратичным вычетом по модулю р, если р вида 4m+1, и является квадратичным невычетом по модулю р, если р вида 4m+3.
g. ab⋯lp=apbp⋯lp.
Действительно, имеемab⋯lp≡ab⋯lp-12≡ap-12bp-12⋯lp-12≡apbp⋯lpmod p.
откуда и вытекает наше утверждение. Отсюда следствие:
ab2p=ap,
т.е. в числителе символа можно отбросить любой квадратичный множитель.
h. Для вывода дальнейших свойств символа Лежандра мы сначала дадим ему другое истолкование. Полагая p1=p-12 , рассмотрим сравнения
a∙1≡ε1r1 mod p,a∙2≡ε2r2 mod p,⋯⋯⋯⋯⋯⋯⋯⋯⋯a∙p1≡εp1rp1 mod p,
где εxrx-абсолютно наименьший вычет ax, rx-егомодуль, так что εx=±1.
Числа aa∙1, -a∙1, a∙2, -a∙2, ⋯, a∙p1,-a∙p1 образуют приведённую систему вычетов по модулю p; их абсолютно наименьшие вычеты суть ε1r1,-ε1r1, ε2r2,-ε2r2,⋯,εp1rp1,-εp1rp1. Положительные из последних, т.е. r1, r2, ⋯, rp1, должны совпадать с числами 1, 2, ⋯,p1.
Перемножая теперь сравнения (1) и сокращая на
1∙2⋯p1=r1r2⋯rp1,
получим ap-12≡ε1ε2⋯εp1mod p, откуда b имеем
ap=ε1ε2⋯εp1.i. Найденному выражению символа Лежандра придадим более законченный вид. Имеем
2axp=2axp+2axp=2axp+2axp,
что будет чётным или нечётным, в зависимости от того, будет ли наименьший неотрицательный вычет числа ax меньше или больше 12p, т.е. будет ли εx=1 или εx=-1. Отсюда, очевидно,
εx=-12axp,
и потому их 2 находим
ap=-1x=1pl2axp.
j. Предполагая a нечётным, преобразуем последнее равенство.Имеем a+b-чётное
2ap=2a+2pp=4a+p2p=a+p2p=-1x=1p1a+bxp=-1x=1p1axp+x=1p1x.
откуда
2pap=-1x=1p1axp+p2-18. (3)
Эта формула поможет нам вывести два весьма важных свойства символа Лежандра.
k. 2p=-1p2-18.
Следует из формулы (3) при a=1.
Но p представить в виде p=8m+s, где s- одно из чисел 1, 3, 5, 7. При этом p2-18=8m2+2ms+s2-18, что будет чётным при s=1 и при s=7 и будет нечётным при s=3 и s=5.Поэтому 2 будет квадратичным вычетом по модулю p, если p вида 8m+1 или вида 8m+7, и будет квадратичным невычетом по модулю p, если p вида 8m+3 или вида 8m+5.
1. Если p и q-простые нечётные, то (закон взаимности квадратных вычетов)
qp=-1p-12∙q-12pq.
Так как p-12∙q-12 будет нечётным лишь в случае, когда оба числа p и q будут формы 4m+3, и чётными, если хоть одно из этих чисел будет формы 4m+1,то указанное свойство можно сформулировать так:
Если оба числа p и q формы 4m+3, то
qp=-pq;
Для доказательства заметим, что ввиду k формула (3) примет вид
ap=-1x=1p1axp. (4)
Полагая теперь q-12=q1, рассмотрим p1q1 пар чисел, получаемых когда в выражениях qx, py числа x и y независимо друг от друга пробегают системы значений
x=1, 2, ⋯, p1, y=1, 2, ⋯, q1.
Никогда не может быть qx=py, потомучто их этого равенства следовало бы, что py кратно q, что ввиду p,q=y,q=1 (так как 0<y<q) невозможно. Поэтому мы можем положить q1p1=S1+S2, где S1- число пар с qx<py и S1-число пар с py<qx.
Очевидно, S1 есть так же число пар с x<pqy. Здесь при данном y можно брать x=1, 2, ⋯, pqy. (Ввиду pqy≤pqq1<p2 имеем pqy≤p1.) Следовательно,
S1=y=1q1pqy....
a. Введём в рассмотрение символ Лежандра ap (читается: символ а по отношению к р). Этот символ определяется для всех а, не делящихся на р; он равен 1, если а-квадратичный вычет, и -1, если а-квадратичный невычет. Число а называется числителем, р-знаменателем символа.
b. Ввиду e, очевидно, имеем
ap≡ap-12mod p.
c. Здесь мы выведем главнейшие свойства символа Лежандра и вследующем параграфе-свойства обобщения этого символа-символа Якоби, которые позволят быстро вычислять этот символ, а следовательно, решать вопрос о возможности сравнения
x2=amod p.
d. Если a≡a1mod p, то ap=a1p.
Это свойство следует из того, что числа одного и того же класса будут одновременно квадратичными вычетами или невычетами.
e. 1p=1.
Действительно, 1=12 и, следовательно, 1-квадратичный вычет.
f.-1p=-1p-12.
Это свойство следует из b при a=-1.
Так как p-12 четное, если р вида 4m+1, и нечётное, если р вида 4m+3, то отсюда следует, что -1 является квадратичным вычетом по модулю р, если р вида 4m+1, и является квадратичным невычетом по модулю р, если р вида 4m+3.
g. ab⋯lp=apbp⋯lp.
Действительно, имеемab⋯lp≡ab⋯lp-12≡ap-12bp-12⋯lp-12≡apbp⋯lpmod p.
откуда и вытекает наше утверждение. Отсюда следствие:
ab2p=ap,
т.е. в числителе символа можно отбросить любой квадратичный множитель.
h. Для вывода дальнейших свойств символа Лежандра мы сначала дадим ему другое истолкование. Полагая p1=p-12 , рассмотрим сравнения
a∙1≡ε1r1 mod p,a∙2≡ε2r2 mod p,⋯⋯⋯⋯⋯⋯⋯⋯⋯a∙p1≡εp1rp1 mod p,
где εxrx-абсолютно наименьший вычет ax, rx-егомодуль, так что εx=±1.
Числа aa∙1, -a∙1, a∙2, -a∙2, ⋯, a∙p1,-a∙p1 образуют приведённую систему вычетов по модулю p; их абсолютно наименьшие вычеты суть ε1r1,-ε1r1, ε2r2,-ε2r2,⋯,εp1rp1,-εp1rp1. Положительные из последних, т.е. r1, r2, ⋯, rp1, должны совпадать с числами 1, 2, ⋯,p1.
Перемножая теперь сравнения (1) и сокращая на
1∙2⋯p1=r1r2⋯rp1,
получим ap-12≡ε1ε2⋯εp1mod p, откуда b имеем
ap=ε1ε2⋯εp1.i. Найденному выражению символа Лежандра придадим более законченный вид. Имеем
2axp=2axp+2axp=2axp+2axp,
что будет чётным или нечётным, в зависимости от того, будет ли наименьший неотрицательный вычет числа ax меньше или больше 12p, т.е. будет ли εx=1 или εx=-1. Отсюда, очевидно,
εx=-12axp,
и потому их 2 находим
ap=-1x=1pl2axp.
j. Предполагая a нечётным, преобразуем последнее равенство.Имеем a+b-чётное
2ap=2a+2pp=4a+p2p=a+p2p=-1x=1p1a+bxp=-1x=1p1axp+x=1p1x.
откуда
2pap=-1x=1p1axp+p2-18. (3)
Эта формула поможет нам вывести два весьма важных свойства символа Лежандра.
k. 2p=-1p2-18.
Следует из формулы (3) при a=1.
Но p представить в виде p=8m+s, где s- одно из чисел 1, 3, 5, 7. При этом p2-18=8m2+2ms+s2-18, что будет чётным при s=1 и при s=7 и будет нечётным при s=3 и s=5.Поэтому 2 будет квадратичным вычетом по модулю p, если p вида 8m+1 или вида 8m+7, и будет квадратичным невычетом по модулю p, если p вида 8m+3 или вида 8m+5.
1. Если p и q-простые нечётные, то (закон взаимности квадратных вычетов)
qp=-1p-12∙q-12pq.
Так как p-12∙q-12 будет нечётным лишь в случае, когда оба числа p и q будут формы 4m+3, и чётными, если хоть одно из этих чисел будет формы 4m+1,то указанное свойство можно сформулировать так:
Если оба числа p и q формы 4m+3, то
qp=-pq;
Для доказательства заметим, что ввиду k формула (3) примет вид
ap=-1x=1p1axp. (4)
Полагая теперь q-12=q1, рассмотрим p1q1 пар чисел, получаемых когда в выражениях qx, py числа x и y независимо друг от друга пробегают системы значений
x=1, 2, ⋯, p1, y=1, 2, ⋯, q1.
Никогда не может быть qx=py, потомучто их этого равенства следовало бы, что py кратно q, что ввиду p,q=y,q=1 (так как 0<y<q) невозможно. Поэтому мы можем положить q1p1=S1+S2, где S1- число пар с qx<py и S1-число пар с py<qx.
Очевидно, S1 есть так же число пар с x<pqy. Здесь при данном y можно брать x=1, 2, ⋯, pqy. (Ввиду pqy≤pqq1<p2 имеем pqy≤p1.) Следовательно,
S1=y=1q1pqy....
Поделиться рефератом
Расскажи своим однокурсникам об этом материале и вообще о СкачатьРеферат