Simvolom Lezhandra nazivayetsya multiplikativna funkciya sho vikoristovuyetsya v teoriyi chisel Nazvana na chest francuzkogo matematika Adriyena Mari Lezhandra Zmist 1 Viznachennya 2 Vlastivosti 3 Obchislennya 3 1 Priklad 4 Div takozh 5 Dzherela 6 LiteraturaViznachennya RedaguvatiNehaj a deyake cile chislo i p proste chislo Simvol Lezhandra a p displaystyle left frac a p right nbsp viznachayetsya takim chinom a p 0 displaystyle left frac a p right 0 nbsp yaksho a displaystyle a nbsp dilitsya na p displaystyle p nbsp a p 1 displaystyle left frac a p right 1 nbsp yaksho a displaystyle a nbsp ye kvadratichnim lishkom za modulem p displaystyle p nbsp tobto isnuye take cile x displaystyle x nbsp sho x 2 a mod p displaystyle x 2 equiv a pmod p nbsp a p 1 displaystyle left frac a p right 1 nbsp yaksho a displaystyle a nbsp ye kvadratichnim nelishkom za modulem p displaystyle p nbsp Vlastivosti RedaguvatiMultiplikativnist a b p a p b p displaystyle left frac ab p right left frac a p right left frac b p right nbsp Yaksho a b mod p displaystyle a equiv b pmod p nbsp to a p b p displaystyle left frac a p right left frac b p right nbsp 1 p 1 displaystyle left frac 1 p right 1 nbsp 1 p 1 p 1 2 displaystyle left frac 1 p right 1 p 1 2 nbsp pershij dodatkovij zakon angl first supplementary law 2 p 1 p 2 1 8 displaystyle left frac 2 p right 1 p 2 1 8 nbsp drugij dodatkovij zakon angl second supplementary law DovedennyaNehaj s p 1 2 displaystyle s frac p 1 2 nbsp i rozglyanemo s displaystyle s nbsp rivnyan 1 1 1 2 2 1 2 3 3 1 3 4 4 1 4 s s 1 s displaystyle begin aligned 1 amp 1 1 2 amp 2 1 2 3 amp 3 1 3 4 amp 4 1 4 amp quad quad ldots s amp pm s 1 s end aligned nbsp Tut mi obirayemo znak tak shob mati pravilnij znak rezultatu Zaraz mnozhimo s displaystyle s nbsp rivnyan razom Livoruch otrimuyemo s displaystyle s nbsp Pravoruch mayemo 2 4 6 displaystyle 2 4 6 dots nbsp i yakis vid yemni neparni chisla Ale zauvazhimo sho 2 s 1 mod p displaystyle 2 s equiv 1 mod p nbsp 2 s 1 3 mod p displaystyle 2 s 1 equiv 3 mod p nbsp i t d otzhe ci vid yemni chisla ye inshimi parnimi chislami za modulem p displaystyle p nbsp ale prihovanimi Otzhe prava chastina stanovit s 2 s displaystyle s 2 s nbsp kozhna dvijka parna do odnogo z chleniv faktorialu shob predstaviti parni chisla za modulem p displaystyle p nbsp Zalishilos lishe zauvazhiti sho 1 1 2 s 1 s s 1 2 displaystyle 1 1 2 ldots s 1 s s 1 2 nbsp i perenesti v livu chastinu Zbirayuchi vse do kupi mi otrimuyemo 2 s s s 1 s s 1 2 mod p displaystyle 2 s s equiv s 1 s s 1 2 mod p nbsp abo po skorochenni faktorialiv 2 s 1 s s 1 2 displaystyle 2 s equiv 1 s s 1 2 nbsp I s s 1 2 p 2 1 8 displaystyle s s 1 2 p 2 1 8 nbsp otzhe mi naspravdi mayemo 2 p 1 2 1 p 2 1 8 displaystyle 2 p 1 2 equiv 1 p 2 1 8 nbsp Yaksho q displaystyle q nbsp proste chislo ne rivne p displaystyle p nbsp to q p p q 1 p 1 2 q 1 2 displaystyle left frac q p right left frac p q right 1 frac p 1 2 cdot frac q 1 2 nbsp chastkovij vipadok kvadratichnogo zakonu vzayemnosti Sered chisel 1 a p 1 displaystyle 1 leq a leq p 1 nbsp rivno polovina maye simvol Lezhandra rivnij 1 a insha polovina 1 Simvol Lezhandra pri p gt 2 displaystyle p gt 2 nbsp mozhna obchisliti za dopomogoyu kriteriyu Ejlera a p a p 1 2 mod p displaystyle left frac a p right equiv a p 1 2 pmod p nbsp Obchislennya RedaguvatiBezposerednye zastosuvannya kriteriyu Ejlera dlya obchislennya simvolu Lezhandra potrebuye pidnesennya do stepenya sho dlya velikih znachen a displaystyle a nbsp i p displaystyle p nbsp ye dovoli skladnim zokrema dovoditsya zastosuvati dovgu arifmetiku ta velmi trudomistkim Nabagato efektivnishe obchislyuvati simvoli Lezhandra cherez yih uzagalnennya simvoli Yakobi 1 Dokladnishe Simvol YakobiPriklad Redaguvati 12345 331 displaystyle left frac 12345 331 right nbsp 3 331 5 331 823 331 displaystyle left frac 3 331 right left frac 5 331 right left frac 823 331 right nbsp 3 331 5 331 161 331 displaystyle left frac 3 331 right left frac 5 331 right left frac 161 331 right nbsp 3 331 5 331 7 331 23 331 displaystyle left frac 3 331 right left frac 5 331 right left frac 7 331 right left frac 23 331 right nbsp 1 331 3 331 5 1 331 7 1 331 23 displaystyle 1 left frac 331 3 right left frac 331 5 right 1 left frac 331 7 right 1 left frac 331 23 right nbsp 1 3 1 5 2 7 9 23 displaystyle left frac 1 3 right left frac 1 5 right left frac 2 7 right left frac 9 23 right nbsp 1 3 1 5 2 7 3 23 2 displaystyle left frac 1 3 right left frac 1 5 right left frac 2 7 right left frac 3 23 right 2 nbsp 1 1 1 1 1 displaystyle left 1 right left 1 right left 1 right left 1 right 1 nbsp Div takozh RedaguvatiSimvol Kronekera YakobiDzherela Redaguvati Nesterenko 2012 s 69 Literatura RedaguvatiAjerlend K Rouzen M Klassicheskoe vvedenie v sovremennuyu teoriyu chisel Moskva Mir 1987 416 s ros Nesterenko A Yu Teoretiko chislovye metody v kriptografii ros Moskovskij gosudarstvennyj institut elektroniki i matematiki M 2012 224 s ISBN 978 5 94506 320 4 Otrimano z https uk wikipedia org w index php title Simvol Lezhandra amp oldid 40369864
