Екінші дәрежелі салыстыру. Құрама модуль жағдайы

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 20 бет
Таңдаулыға:

Маликова Асем СИБ-29
Екінші дәрежелі салыстыру
Екінші дәрежелі салыстыруды түсіну үшін төмендегі теңсіздікті қарасты-рып көрейік:
x2≡amod m;
-осындағы m∈N, m1, a мен m өзара жай сандар. Бүтін a саны m санының модулі бойынша шегерімдер сақинасы болып табылады.
Анықтама 1: Егер берілген екінші дәрежелі салыстырылымның нәтижесі болса, онда a саны m санының модулі бойынша квадраттық шегерімі болады, олай болмаған жағдайда a саны m санының модулі бойынша квадраттық шегерімі бола алмайды.
Мысал 1: 5 саны 11 санының модулі бойынша квадраттық шегерімі бола алады, себебі x2≡5mod 11 теңсіздігі бойынша x≡4mod 11: 42=16≡5(mod 11) шешімі бар.
Мысал 2: 21 саны m=541*547*563*571*587 санының модулі бойынша квадраттық шегерімі бола алады, себебі x2≡21mod m теңсіздігі бойынша x≡1008002722743mod m шешімін қабылдайды.
Мысал 3: 3 саны 7 санының модулі бойынша квадраттық шегерімі бола алмайды, себебі : 12=1, 22=4, 32=9≡2mod 7, 42=16≡2mod 7, 52=25≡4mod 7, 62=36≡1mod 7 көрсетілген теңсіз-діктердің шешімдерінің ешқайсысы 3 мәнің қабылдамайды.

Лежандра мен Якоби таңбалары
Анықтама 2: Төмендегі теңсіздікті қарастырып көрейік:
x2≡amod p; (1)
-осындағы p!=2 болатын p жай саны, a саны p санына бөлінбейді. a мен p сандарының Лежандра таңбасын анықтап көрейік
ap=1, егер берілген теңсіздіктің шешімі бар болса -1, егер берілген теңсіздіктің шешімі болмаса

Сонда, егер ap=1-ге тең болса, онда a саны p санының модулі бойынша квадраттық шегерімі болады, ал егерде ap=-1-ге тең болса, онда a саны p санының модулі бойынша квадраттық шегерімі бола алмайды.
Лежандра таңбасы p!=2-ге бөлінбейтін кез келген a, b үшін келесі қасиеттерді қабылдайды:
1. a+kpp=ap , осындағы k∈Z.

Дәлелдеу: a+kp≡a(mod p) салыстырылымы осындағы кез келген k∈Z үшін орындалатындықтан, берілген теңсіздік орындалады. Сонда, егер a≡b(mod p) болатындығын ескерсек, онда салыстырылым ap=bp қалпін қабылдай алады.

2. ab2p=ap .

Дәлелдеу: ЕКОЕb,p=1 болғандықтан, b-1(mod p) - салыстырылымы бар болады. Онда x2≡ab2mod p және (b-1x)2≡a(mod p) теңсіздіктерінің шешілуі не шешілмеуі бір мезгілде болыды, демек олар бір біріне тең бола алыды.

3. ap≡ap-12(mod p). Атап айтқанда, 1p=1 кез келген p!=2 үшін, 1p=-1 кез келген p≡1(mod 4) және -1p=-1 кез келген p≡3(mod 4) үшін орындалып отырады.

Дәлелдеу: Фермнің кіші теоремасына сәйкес, ap-1≡1(mod p). Сонда ap-1-1=(ap-12-1)(ap-12+1)≡0(mod p) салыстырылымы пайда болады. Салыстырылымдағы екі көбейткіш те p-ға бөлінбейді, әйтпесе айырмашылығы 2-ге тең көбейткіш p-ға бөлінуші еді. Осылайша, кез келген a, 1=ap үшін салыстырылымның біреуі орындалады:

ap-12≡1mod p, (2)
ap-12≡-1mod p, (3)

Егер a саны p санының модулі бойынша квадраттық шегерімі болса, онда a≡c2(mod p) салыстырылымына сәйкес c саны бар болады. Осы салыстырылымның екі бөлігін де p-12 дәрежеге келтіріп, Фермнің кіші теоремасын қолдансақ, салыстырылымның нәтижесі ap-12≡сp-1≡1mod p - ге сәйкес болады. Сонда шыққан нәтижеге сәйкес, кез келген квадраттық шегерім (2) салыстырымды қаңағаттандыратынына көз жеткіземіз. Бұл ретте, (1) салыстырылымды еске түсірген қажет. (1) салыстырылымға сәйкес, yp-12≡1mod p салыстырылымы p-12 -ден артық жауап қабылдай алмайды, демек, кез келген квадраттық шегерім (3) салыстырымды қаңағаттандыратынына көз жеткіземіз.

4. abp=apbp.

Дәлелдеу: 3-ші қасиетті екі рет қолданған жағдайда, төмендегі теңсіздік пайда болады:

abp≡abp-12=ap-12bp-12≡apbpmod p.

Осылайша, abp-apbp айырмашылығы p санына бөлінеді. p-жай сан, ал Лежандра таңбасы -1, 1 мәндерін қабылдайды, демек, бөліну тек abp=apbp - жағдайында ғана болуы мүмкін.

5. Лемма 1 (Гаусс). ap=(-1)μ, осындағы μ - a, 2∙a, ..., p-12∙a сандарының абсолютты аз шегерімдері арасындағы теріс шегерімдер саны.

Дәлелдеу [1]: +-mk - ka санына сәйкес келетін ең аз шегерім болсын, мұндағы mk0. k мәнінің 1-ден p-12-ге дейін өзгеруі кезінде μ саны - - mk-ға сәйкес келетін - белгілірінің саны. Егер, k!=l және 1=k, l=p-12 болса , онда mk!=ml болады. a саны p-ға бөлінбейтіндіктен, теңдеудің екі бөлігінде a-ға бөле аламыз. Осыдан біз k≡+-l(mod p) , яғни k+-l≡0(mod p) салыстырылымын аламыз. Бірақ оның болуы k+-l=k+l=p-1 мен k!=l болуына байланысты мүмкін емес. Сонда, m1, m2, ..., m(p-1)2 жиынының әр мүшесі әр түрлі болады және бұл жиын 1, 2, ..., p-12 - жиынына сәйкес келеді. a≡+-m1mod p, 2a≡+-m2mod p, ..., p-12 ∙a≡ +-m(p-1)2mod p салыстырылымын көбейтудің нәтижесінде:

p-12!∙ap-12≡(-1)μp-12!mod p.

oo салыстырымын аламыз.
p-12! саны p-ға бөлінбейтіндіктен , салыстырымның екі бөлігінде оған бөлеміз: ap-12≡(-1)μ(mod p). 3 қасиетті қолдана отырып және Лежандра таңбасы тек 1 мен -1 мәндерін ғана қабылдайтындығын ескере отырып, біз қажетті теңсіздікті аламыз.

Мысал 4. Гаусс леммасын қолдана отырып, 513 санының Лежандра таңбасын табайық. Ең абсолютті кіші шегерімдер жүйесін құрайық: 5, 2∙5=10=-3(mod 13), 3∙5=15=2(mod 13), 4∙5=20=-6(mod 13), 5∙5=25=-1(mod 13), 6∙5=30=4(mod 13). Нәтижесінде үш теріс мәндегі сандар алынды, сонда 513=(-1)3=-1 мәні шығады.

6. 2p=(-1)p2-18, яғни p=+-1(mod 8) болған жағдайда 2p=1 мәні; p=+-1mod 8 болған жағдайда 2p=-1 мәні шығады.

Дәлелдеу: p санының модулі бойынша 2∙1, 2∙2, ..., 2∙p-12 - шегерімдер жиының қарастырайық. Гаусс леммасындағы белгілеулер бойынша μ-саны осы жүйенің p-12-ден үлкен элеметтерінің санына тең. Бүтін m санды қос теңсіздікпен орнатайық: p-12-22m= p-12. Онда μ=p-12-m.
p-нің барлық мүмкін мәндерін анықтау үшін кеслесі есептеулерді кестеге жазайық:
p
p-12
p-12-22m= p-12
m
μ
2p=(-1)μ
8k+1
4k
4k-22m=4k
2k
2k
1
8k+7
4k+3
4k+12m=4k+3
2k+1
2k+2
1
8k+3
4k+1
4k-12m=4k+1
2k
2k+1
-1
8k+5
4k+2
4k2m=4k+2
2k+1
2k+1
-1

7. a-ның 1-ден (p-1)-ге дейін өзгеруі кезінде Лежандра таңбасы 1 мен -1 мәндерін қабылдау жиілігі бірдей болады.

Дәлелдеу: p санының модулі бойынша квадраттық шегерімдер 12, 22, ..., (p-1)2)2 - сандар жүйесімен салытырымға келетін сандар ғана бола алады. Шынында да, a2≡b2(mod p) үшін 0ab=p-12 - ге a≡bmod p пен a≡-b≡p-bmod p болу керек. Ал қалған p-12 сандары p санының модулі бойынша квадраттық шегерімі бола алмайды.

Теорема 1.(Гаустың квадраттық өзара әрекеттесу заңы). p мен q-өзара жай, p!=2, q!=2 сандар делік. Онда :

pq=(-1)p-12∙q-12qp

Басқаша айтқанда, егер p≡q≡3(mod 4) онда pq=-qp болады, олай болмаған жағдайда pq=qp болады.
Дәлелдеу [2]: f пен g функцияларын m бүтін санына сәйкес келетін p мен q - дің абсолютті ең кіші шегерімдер арқылы тауып көрейік;

fm≡mmod p,
gm≡mmod q.

Қалдық туралы қытай теоремасына сәйкес, -pq-12,pq-12 - аралықтағы m-нің әр бүтін саны үшін (fm,gm) және керісінше абсолютті ең кіші шегерімдері болады. P - 1,pq-12 - аралықтағы m-нің әр бүтін саны үшін абсолютті ең кіші шегерімдер жиыны болсын. Белгілейік:

P++=(x, y)∈Px0, y0,
P-+=(x, y)∈Px0, y=0,
P+-=(x, y)∈Px=0, y0.

Мұндағы N++, N-+, N+- - сандары P++, P-+, P+- - жиындарының мүшелерінің саның көрсетеді.
Р жиыныныңда дәл p-12 сәйкес (х, у) нүктелері бар және мұндағы у=0, бұл (fmq, 0) түріндегі нүктелер және мұндағы m=1, 2, ..., p-12. u - fmq0 теңсіздігін қанағаттандыратын нүктелер саны болсын. Сол сияқты, Р жиыныныңда дәл q-12 сәйкес (х, у) нүктелері бар және мұндағы x=0, бұл (0, gnp) түріндегі нүктелер және мұндағы n=1, 2, ..., p-12. v - gnp0 теңсіздігін қанағаттандыратын нүктелер саны болсын.
Р жиыныныңда fm0 теңсіздігі үшін дәл p-12q-12+1 нүкте бар, бұл m=k+lp - сандарына сәйкес келетін (fm, gm) - нүктелері, мұнда: 1=k=p-12 , 1=l=q-12. Демек,

N+++ N+-=p-12q-12+1-p-12+u+v=p-12∙q-12+u +v.

Сол сияқты да N+++ N-+=p-12∙q-12+u+v.
f пен g функциялары тақ болып келеді: f-m=-fm , g-m=-gm, сол себептен, осындай бүтін сандардың кез-келген жұбы үшін х!=0, у!=0, бұл x∈-p-12, p-12 , y∈-q-12, q-12 , және (х, у) не (-х, -у) нүктелерінің біреуі ғана Р жиынына кіреді. Демек:

N+++ N-+=p-12∙q-12+u+v.
Осыдан:
2(N+++ N+-+ N-+)=3p-12∙q-12+u+v.

Осы теңдіктін екі жағын да mod 2-ге алайық:

0≡p-12∙q-12+u+vmod 2,

яғни:

p-12∙q-12≡u+vmod 2
және:

(-1)p-12∙q-12=(-1)μ(-1)v,

а Гаусс леммасы бойынша (-1)μ=qp және (-1)v=pq болады.

Мысал 5: 88347 санының Лежандра таңбасын анықтайық. 88 саның көбейткіштерге жіктейік: 88=23∙11. Демек, 4-ші қасиетке сәйкес:

88347=23∙11347=23347∙11347.

2 қасиет бойынша: 23347=2∙22347=2347, 347≡3(mod 8) болған-дықтан, 6-шы қасиет бойынша біз 2347=-1 мәнің аламыз.

11347 саның есептеу үшін квадраттық өзара әрекеттесу заның қолданай-ық: 11347=(-1)11-12∙347-1234711=(-1)5∙1 7334711=-34711.
347=11∙31+6 болғандықтан, 1-ші қасиет бойынша біз 34711=611-ны аламыз. 4-ші қасиетті қолданайық: 611=211311. 6-шы қасиет бойынша есептейік: 211=(-1)112-18=(-1)15=-1, 3-ші қасиет бойынша: 311≡311-12=35=243=1(mod 11) мәнедері шығады. Осылайша, 11347=--1∙1=1 және 88347=-1∙1=-1.

Мысал 6: Квадраттық өзара әрекеттесу заның қолдана отырып, 5 саны модулі бойынша квадраттық шегерім бола алатын p жай сандарын табайық. Лежандра таңбасын жазайық:

5p=(-1)5-12∙p-12p5=(-1)2∙p-12p5=p5

Енді, p-нің қандай мәндерінде 1-ге тең екенің анықтайық. 3 қасиет бойынша Лежандра таңбасы:

p5=p5-12=p2mod 5.

Осылайша, p2=1mod 5 - ке сәйкес келетін p жай сандарын табайық. p!=5 жай саны 5-ке бөліну кезінде 1, 2, 3, 4 қалдықтарын бере алады, бұл ретте 12=42= 1mod 5. Сонда, 5 саны 5k+1және 5k+4 түріндеге жай сандар-дың квадраттық шегерімі болады, осындағы k-бүтін сан. Басқаша айтқанда, ондық сандар жүйесінде берілген p саны 1 не 9 санымен аяқталуы керек, мысалға: 11, 19, 29, 31 және т.б. сандар.

Лежандра таңбасының жалпылау түрі болып - Якоби таңбасы болып табылады.

Анықтама 3: Айталық: m, n∈Z, осындағы n=p1p2...pr және pi!=2 сандары жай сан. mn санының Якоби таңбасы төмендегі теңдікпен анық-талады:

mn=mP1mP2...mPr.

Егер n-жай сан болса, онда Якоби таңбасы Лежандра таңбасына айналады.
Якоби таңбасы келесі қасиеттерді қабылдайды:
1. an өрнегі 0, 1, -1 мәндерін қабылдайды, және an=0 мәнің тек ЕҮОБ(a,n)!=1 болғанда ғана орындалады. a+-1=1 болып саналады.
2. a+knn=an кез келген a, k∈Z үшін
3. ab2n=an кез келген a, b∈Z, ЕҮОБ(b,n)=1 үшін
4. abn=anbn кез келген a, b∈Z үшін
5. 1n=1; -1n=(-1)n-12. Демек, n=1mod 4 болған кезде -1n=1 мәнің; сол сияқты, n=-1mod 4 болған кезде -1n=-1 мәнің аламыз.
Дәлелдеу [3]: 1n=1 теңдігі Якоби таңбасының анықтамасы бойынша орындалады. Екінші теңдіктің дәлелі үшін, p1=2k1+1, p2=2k2+1 тақ сандары үшін төмендегі салыстыру орындалатының атап айтқан жөн:

p1p2-12=p1-12+p2-12mod 2.

Шынында да, (p1-1)(p2-1)= 2k1∙2k2=4k1k2=0(mod 4), сол себ-ептен p1p2-1=(p1-1)(p2-1)+p1+p2-2=(p1-1)+ (p2-1)(mod 4). Осы салыстырудың шеткі бөліктері мен модулін 2-ге бөлу арқылы біз қажетті қатынасты аламыз. Индукция арқылы біз

i=1rpi-12≡p1p2...pr-12mod 2.

- теңдігін аламыз. Сонда:
-1n=i=1r-1pi=i=1r-1pi-12=-1i=1rpi-1 2=-1p1p2...pr-12=-1n-12.

6. 2n=(-1)n2-18. Демек, n=+-1mod 8 болған кезде 2n=1 мәнің; сол сияқты, n=+-3mod 8 болған кезде 2n=-1 мәнің аламыз.

Дәлелдеу [3]: p1, p2 тақ сандары үшін төмендегі салыстыру орындалады:

p12p22-18=p12-18+p22-18mod 2.

Шынында да, p12-1 мен p22-1 сандарының әр қайсысы 4-ке бөлінеді, яғни (p12-1)(p22-1)≡0mod 16 , сол себептен p12p22-1≡(p12-1)+(p22-1)mod 16. Осы салыстырудың екі бөлігі мен модулін 8-ге бөлу арқылы біз қажетті қатынасты аламыз. Индукция арқылы біз

i=1rpi2-18≡p12p22...pr2-18mod 2.

теңдігін аламыз. Сонда:

2n=i=1r2pi=i=1r-1pi2-18=-1i=1rpi2-1 8=-1p12p22...pr2-18=-1n2-12.

7. m, n тақ сандары үшін mn=(-1)m-12∙n-12nm теңдігі орындалады.
Дәлелдеу [3]: Егер m=p1p2...pr, n=q1q2...qs болса, онда 4 қасиетті ескере отырып, Якоби таңбасының анықтамасы мен квадраттық өзара әрекет-тесу заңы арқылы mn=(-1)i=1rj=1spi-12∙qj-12nm салыстырылымын аламыз. Дәреже көрсеткіштеріндегі соманы 2-модуль бойынша есептеу жеткілікті бола-ды. Сонда:

i=1rj=1spi-12∙qj-12≡m-12j=1sqj-12≡m -12∙n-12mod 2.

Яғни, i=1rj=1spi-12∙qj-12 мен m-12∙n-12 сандарының екеуі де бірдей жұптылықты иемденеді, және (-1)i=1rj=1s pi-12∙qj-12=(-1)m-12∙n-12.
Якоби таңбасының қасиеттеріне сүйінсек, онда, егер n - бүтін тақ сан болса және a=2ka1 , мұндағы a тақ сан, онда:

an=2kna1m=2nkn(mod a1)a1(-1)(a1-1)(n-1)4∙.

Осыдан біз Якоби таңбасын есептеу алгоритмін аламыз[1].

Алгоритм 1. Якоби таңбасын есептеу.
Кіру. Бүтін n=3 тақ саны, бүтан a сан, 0=an.
Шығу. Якоби таңбасы an.
1. g--1-ді қою.
2. a=0 болғанда жауап:0.
3. a=1 болғанда жауап: g.
4. a=2ka1 түрінде a-ны ұсыну, мұндағы a1 тақ сан.
5. k жұп болған жағдайда, s--1-ді салу. Егер k тақ болса,онда, n=+-1mod 8 болғанда s--1-ді салу; n=+-3mod 8 болғанда s---1-ді салу.
6. a1=1 болғанда жауап: g∙s.
7. Егер, n=3mod 4 және a1=3mod 4 болса, онда s--- s.
8. a--n(mod a1), n--a1, g--g∙s - ті салып, екінші пунктке оралу.
Алгоритм қиындығы O(log2n) .
Мысал 7:5322739 санының Якоби таңбасын анықтайық. g=1 деп есептейік.
Бірінші итерация. a санының көрінісін табайық: 532=22∙133, a1=133. k=2 жұп сан, сол себептен s=1. a=2739≡79(mod 133), n=133, g=1∙1=1 деп есептейік.
Екінші итерация. a санының көрінісін табайық: 79=20∙79, a1=79. k=0 жұп сан, сол себептен s=1. a=133≡54(mod 79), ), n=79, g=1∙1=1 деп есептейік.
Үшінші итерация. a санының көрінісін табайық: 54=21∙27, a1=27. k=1 тақ сан және n=79≡-1(mod 8), сол себептен s=1. Сонымен қатар, n=3mod 4 және a1=3mod 4болғандықтан, s=-1. a=79≡25(mod 27), n=27, g=1∙-1=-1 деп есептейік.
Төртінші итерация. a санының көрінісін табайық: 25=20∙25, a1=25. k=0 жұп сан, сол себептен s=1. a=27≡2(mod 25), n=25, g=1∙-1=-1 деп есептейік.
Бесінші итерация. a санының көрінісін табайық: 2=21∙2, a1=2. k=1 тақ сан және n≡1(mod 8), сол себептен s=1.
a1=1 болғандықтан, алгоритм 6 қадамда: 1∙-1=-1 мәнімен аяқталады.

Жай сан модулі

Төмендегі теңсіздікті қарастырып көрейік:
x2≡amod p; (4)
-осындағы p!=2 болатын p жай саны, a саны p санына бөлінбейді.
Берілген теңсіздіктін шішімінің болу мүмкіндігін анықтау үшін, Лежандра таңбасы ap-ны тапқан жеткілікті болады. ap=-1 болған жағдайда (4) теңсіздіктің шешімі болмайды.
ap=1 болған кезде (4) теңсіздіктің екі шешімі болады. Шынында да, егер ap=1 болса, онда Лежандра таңбасының анықтамасына сәйкес, (4) теңсіздіктің кем дегенде бір шешімі болады: x1(mod p). x2 - (4) теңсіздіктің басқа шешімі болсын делік. Демек, x1-x2 , x1+x2 өрнектерінің кем деген біреуі болсын p-санына бөлінуі керек. Бірінші жағдайда бізге белгілі x1 шешімін алсақ, екінші жағдайдағы алатын шешіміміз: x2=-x1(mod p). Бұл жағдайда x1 және -x1 мәндері әртүрлі, әйтпесе 2x1≡0(mod p) теңдігі орын-далушы еді, бірақ, p!=2 және ЕКОБx1, p=ЕКОБa, p=1 болғандықтан бұл теңдік орындалмайды. Сонымен қатар, жоғарыда көрсетілген теоремаға сәйкес - (4) теңсіздігі екіден артық шешім қабылдай алмайды.

Модульдің түрлеріне байланысты (4) теңсіздіктің бірнеше шығару жолын қарастырып көрейік.
p≡3(mod 4), яғни p=4m+3, мұндағы m∈Z делік. Егер (4) теңсіз-діктің шешімі болса, онда ap=1 болады. Лежандра таңбасының 4 қасиеті бойынша 1=ap=ap-12=a2m+1(mod p). Онда:

(am+1)2=a2m+2=a2m+1∙a≡amod p.

Осылайша, шешім x≡+-am+1(mod p) түренде болады.

Мысал 8: x2≡7 mod 31 теңсіздігін шығарып көрейік. Лежандра таңбасын есептейік: 731=1, демек, теңсіздіктін шешімі бар. 31 санын 31=4∙7+3 түрінде жазайық, сонда m=7 болады. Есептің шешімін табайық: x≡+-78=+-737372≡+-2∙2∙18≡+-10 (mod 31).
Тексерейік: (+-10)2-7=100-7=93=31∙3.
p≡5(mod 8), яғни p=8m+5, мұндағы m∈Z делік. Егер (4) теңсіздіктің шешімі болса, онда ap=1 болады. Лежандра таңбасының 3 қасиеті бойынша бойынша 1=ap=ap-12=a4m+2=(a2m+1)2(mod p). Осы-дан, a2m+1≡1(mod p) немесе a2m+1≡-1(mod p) мәндері шығады. Бірінші жағдайда теңдіктің екі жағын да a-ға көбейту арқылы a2m+2≡a(mod p) мәні шығады, яғни, шешім x≡+-am+1(mod p) күйінде болады.
a2m+1≡-1(mod p) жағдайында жайғдай әлдеқайда күрделірек болады. p≡5(mod 8) кезінде 2 саны p санының модулі бойынша квадраттық шегерімі бола алмайтының ескеруіміз қажет. Шынында да, 2p=2p-12=24m+2≡(22m+1)2(mod p). Лежандра таңбасының 3 қасиеті бойынша бойынша 2p=2p-12=24m+2=(a2m+1)2(mod p). Осылайша, (a2m+1)2≡-1(mod p). Онда:
a2m+1∙(a2m+1)2≡1mod p.
Салыстырылымның екі жағын да a-ға көбейту арқылы, теңсіздіктің шешімі: x≡+-am+1∙a2m+1(mod p) болады.
Мұнда 2 санының орнына кез келген p санының модулі бойынша квадраттық шегерімі бола алатын сандарды қоюға болады.
Мысал 9: x2≡10mod 53 теңсіздігін шығарайық. Лежандра таңбасын табайық: 1053=1, демек, теңсіздіктін шешімі бар. 53 санын 53=8∙6+5 түрінде жазайық, сонда m=6 болады. 102-6+1≡1(mod 53) болғандықтан, есептін шешімі: x≡+-107≡+-13 (mod 53) болады.
Тексерейік: (+-13)2-10=169-10=159=53∙3.
Мысал 10: x2≡11mod 37 теңсіздігін шығарайық. Лежандра таңбасын табайық: 1137=1, демек, теңсіздіктін шешімі бар. 37 санын 37=8∙4+5 түрінде жазайық, сонда m=4 болады. 112-4+1≡-1(mod 37) болғандықтан, есептін шешімі: x≡+-115∙29≡+-14 (mod 37) болады.
Тексерейік: (+-14)2-11=196-11=185=37∙5.
p≡1(mod 8) делік. p санының көрінісін табайық: p=2k∙h+1, мұндағы k=3, h-тақ сан. (4) теңсіздіктің шешімінің болуы ap=1 - ді білдіреді. Лежандра таңбасының 3 қасиеті бойынша бойынша 1=ap=ap-12≡a2k-1∙h(mod p). Осыдан , a2k-2∙h≡+-1(mod p). N - p санының модулі ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.