Екінші дәрежелі салыстырулар: Лежандра мен Якоби таңбалары, Гаусс леммасы, квадраттық өзара әрекеттесу және шешу алгоритмдері

Маликова Асем СИБ-29

Екінші дәрежелі салыстыру

Екінші дәрежелі салыстыруды түсіну үшін төмендегі теңсіздікті қарасты-рып көрейік:

$$\mathbf{x}^{\mathbf{2}}\mathbf{\equiv a}\left( \mathbf{mod\ m} \right) \mathbf{; }$$

-осындағы $m \in N, \ m > 1, \ a$ мен $m$ өзара жай сандар. Бүтін $a$ саны $m$ санының модулі бойынша шегерімдер сақинасы болып табылады.

Анықтама 1: Егер берілген екінші дәрежелі салыстырылымның нәтижесі болса, онда $a$ саны $m$ санының модулі бойынша квадраттық шегерімі болады, олай болмаған жағдайда $a$ саны $m$ санының модулі бойынша квадраттық шегерімі бола алмайды.

Мысал 1: $5$ саны $11$ санының модулі бойынша квадраттық шегерімі бола алады, себебі $x^{2} \equiv 5(mod\ 11)$ теңсіздігі бойынша $x \equiv 4(mod\ 11) :\ 4^{2} = 16 \equiv 5(mod\ 11)$ шешімі бар.

Мысал 2: $21$ саны $m = 541*547*563*571*587$ санының модулі бойынша квадраттық шегерімі бола алады, себебі $x^{2} \equiv 21(mod\ m)$ теңсіздігі бойынша $x \equiv 1008002722743(mod\ m)$ шешімін қабылдайды.

Мысал 3: $3$ саны $7$ санының модулі бойынша квадраттық шегерімі бола алмайды, себебі : $\ {\ 1}^{2} = 1, \ \ \ {\ \ 2}^{2} = 4, \ {\ \ \ \ \ 3}^{2} = 9 \equiv 2(mod\ 7), \ {\ \ \ \ 4}^{2} = 16 \equiv 2(mod\ 7), \ \ {\ \ 5}^{2} = 25 \equiv 4(mod\ 7), \ \ {\ \ \ \ 6}^{2} = 36 \equiv 1(mod\ 7) \$ көрсетілген теңсіз-діктердің шешімдерінің ешқайсысы 3 мәнің қабылдамайды.

Лежандра мен Якоби таңбалары

Анықтама 2: Төмендегі теңсіздікті қарастырып көрейік:

$\mathbf{x}^{\mathbf{2}}\mathbf{\equiv a}\left( \mathbf{mod\ p} \right) \mathbf{; \ }$ (1)

-осындағы $p \neq 2\ болатын\ p\ жай\ саны, \ \ a\ саны\ p\ санына\$ бөлінбейді. $a\ мен\ p\$ сандарының Лежандра таңбасын анықтап көрейік

$$\left( \frac{a}{p} \right) = \left\{ \begin{array}{r} 1, \ \ егер\ берілген\ теңсіздіктің\ шешімі\ бар\ болса\ \\ - 1, \ \ егер\ берілген\ теңсіздіктің\ шешімі\ болмаса\ \end{array} \right. \$$

Сонда, егер $\left( \frac{a}{p} \right) = 1$ -ге тең болса, онда $a$ саны $p$ санының модулі бойынша квадраттық шегерімі болады, ал егерде $\left( \frac{a}{p} \right) = - 1$ - ге тең болса, онда $a$ саны $p$ санының модулі бойынша квадраттық шегерімі бола алмайды.

Лежандра таңбасы $p \neq 2$ -ге бөлінбейтін кез келген $a$ , $b$ үшін келесі қасиеттерді қабылдайды:

1. (𝐚+𝐤𝐩𝐩) =(𝐚𝐩) \left( \frac{\mathbf{a + kp}}{\mathbf{p}} \right) \mathbf{=}\left( \frac{\mathbf{a}}{\mathbf{p}} \right), осындағыk∈Zk \in Z.

Дәлелдеу: $a + kp \equiv a(mod\ p)$ салыстырылымы осындағы кез келген $k \in Z$ үшін орындалатындықтан, берілген теңсіздік орындалады. Сонда, егер $a \equiv b(mod\ p)$ болатындығын ескерсек, онда салыстырылым $\left( \frac{a}{p} \right) = \left( \frac{b}{p} \right)$ қалпін қабылдай алады.

2. (𝐚𝐛𝟐𝐩) =(𝐚𝐩) \left( \frac{\mathbf{a}\mathbf{b}^{\mathbf{2}}}{\mathbf{p}} \right) \mathbf{=}\left( \frac{\mathbf{a}}{\mathbf{p}} \right) .

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

3. (𝐚𝐩) ≡𝐚𝐩−𝟏𝟐(𝐦𝐨𝐝𝐩) \left( \frac{\mathbf{a}}{\mathbf{p}} \right) \mathbf{\equiv}\mathbf{a}^{\frac{\mathbf{p - 1}}{\mathbf{2}}}\mathbf{(mod\ p) }. Атап айтқанда, (1p) =1\left( \frac{1}{p} \right) = 1кез келгенp≠2p \neq 2үшін, (1p) =−1\left( \frac{1}{p} \right) = - 1кез келгенp≡1(mod4) p \equiv 1(mod\ 4) және(−1p) =−1\left( \frac{- 1}{p} \right) = - 1кез келгенp≡3(mod4) p \equiv 3(mod\ 4) үшін орындалып отырады.

Дәлелдеу: Фермнің кіші теоремасына сәйкес, $a^{p - 1} \equiv 1(mod\ p) . \$ Сонда $a^{p - 1} - 1 = (a^{\frac{p - 1}{2}} - 1) (a^{\frac{p - 1}{2}} + 1) \equiv 0(mod\ p)$ салыстырылымы пайда болады. Салыстырылымдағы екі көбейткіш те $p$ -ға бөлінбейді, әйтпесе айырмашылығы 2-ге тең көбейткіш $p$ -ға бөлінуші еді. Осылайша, кез келген $a, \ \ 1 \leq a < p$ үшін салыстырылымның біреуі орындалады:

$\mathbf{a}^{\frac{\mathbf{p - 1}}{\mathbf{2}}}\mathbf{\equiv 1}\left( \mathbf{mod\ p} \right) \mathbf{, }$ (2)

$\mathbf{a}^{\frac{\mathbf{p - 1}}{\mathbf{2}}}\mathbf{\equiv - 1}\left( \mathbf{m}\mathbf{od\ p} \right) \mathbf{, \ \ \ }$ (3)

Егер $a$ саны $p$ санының модулі бойынша квадраттық шегерімі болса, онда $a \equiv c^{2}(mod\ p)$ салыстырылымына сәйкес $c$ саны бар болады. Осы салыстырылымның екі бөлігін де $\frac{p - 1}{2}$ дәрежеге келтіріп, Фермнің кіші теоремасын қолдансақ, салыстырылымның нәтижесі $a^{\frac{p - 1}{2}} \equiv с^{p - 1} \equiv 1(mod\ p)$ -ге сәйкес болады. Сонда шыққан нәтижеге сәйкес, кез келген квадраттық шегерім (2) салыстырымды қаңағаттандыратынына көз жеткіземіз. Бұл ретте, (1) салыстырылымды еске түсірген қажет. (1) салыстырылымға сәйкес, $y^{\frac{p - 1}{2}} \equiv 1(mod\ p)$ салыстырылымы $\frac{p - 1}{2}$ -ден артық жауап қабылдай алмайды, демек, кез келген квадраттық шегерім (3) салыстырымды қаңағаттандыратынына көз жеткіземіз.

4. (𝐚𝐛𝐩) =(𝐚𝐩) (𝐛𝐩) \left( \frac{\mathbf{ab}}{\mathbf{p}} \right) \mathbf{=}\left( \frac{\mathbf{a}}{\mathbf{p}} \right) \left( \frac{\mathbf{b}}{\mathbf{p}} \right) .

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

$$\left( \frac{\mathbf{ab}}{\mathbf{p}} \right) \mathbf{\equiv}\left( \mathbf{ab} \right) ^{\frac{\mathbf{p - 1}}{\mathbf{2}}}\mathbf{=}\mathbf{a}^{\frac{\mathbf{p - 1}}{\mathbf{2}}}\mathbf{b}^{\frac{\mathbf{p - 1}}{\mathbf{2}}}\mathbf{\equiv}\left( \frac{\mathbf{a}}{\mathbf{p}} \right) \left( \frac{\mathbf{b}}{\mathbf{p}} \right) \left( \mathbf{mod\ p} \right) \mathbf{. }$$

Осылайша, $\left( \frac{ab}{p} \right) - \left( \frac{a}{p} \right) \left( \frac{b}{p} \right)$ айырмашылығы $p$ санына бөлінеді. $p$ -жай сан, ал Лежандра таңбасы -1, 1 мәндерін қабылдайды, демек, бөліну тек $\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right)$ - жағдайында ғана болуы мүмкін.

5. Лемма 1 (Гаусс) . (ap) =(−1) μ, \left( \frac{a}{p} \right) = ({- 1) }^{\mu}, \осындағыμ\mu-a, 2•a, …, p−12•aa, \ 2 \bullet a, \ \ldots, \ \frac{p - 1}{2} \bullet a\сандарының абсолютты аз шегерімдері арасындағы теріс шегерімдер саны.

Дәлелдеу [1] : $\pm m_{k}$ - $ka$ санына сәйкес келетін ең аз шегерім болсын, мұндағы $m_{k} > 0$ . $k$ мәнінің 1-ден $\frac{p - 1}{2}$ -ге дейін өзгеруі кезінде $\mu$ саны -- $m_{k}$ -ға сәйкес келетін «-» белгілірінің саны. Егер, $k \neq l\$ және $1 \leq k, \ \ l \leq \frac{p - 1}{2}$ болса, онда $m_{k} \neq m_{l}$ болады. $a$ саны $p$ -ға бөлінбейтіндіктен, теңдеудің екі бөлігінде $a$ -ға бөле аламыз. Осыдан біз $k \equiv \pm l(mod\ p)$ , яғни $k \pm l \equiv 0(mod\ p)$ салыстырылымын аламыз. Бірақ оның болуы $k \pm l \leq k + l \leq p - 1$ мен $k \neq l$ болуына байланысты мүмкін емес. Сонда, $\left\{ m_{1}, \ {\ m}_{2}, \ \ldots, \ \ m_{\frac{(p - 1) }{2}} \right\}$ жиынының әр мүшесі әр түрлі болады және бұл жиын $\left\{ 1, \ \ 2, \ \ldots, \ \ \frac{p - 1}{2}\ \right\}$ -жиынына сәйкес келеді. $a \equiv \pm m_{1}(mod\ p)$ , $2a \equiv \pm m_{2}(mod\ p)$ , …, $\frac{p - 1}{2}\ \bullet a \equiv \ \pm m_{\frac{(p - 1) }{2}}(mod\ p)$ салыстырылымын көбейтудің нәтижесінде:

$$\left( \frac{\mathbf{p - 1}}{\mathbf{2}} \right) \mathbf{! \bullet}\mathbf{a}^{\frac{\mathbf{p - 1}}{\mathbf{2}}}\mathbf{\equiv (}\mathbf{- 1) }^{\mathbf{\mu}}\left( \frac{\mathbf{p - 1}}{\mathbf{2}} \right) \mathbf{!}\left( \mathbf{mod\ p} \right) \mathbf{. }$$

• салыстырымын аламыз.

$\left( \frac{p - 1}{2} \right) !$ саны $p$ -ға бөлінбейтіндіктен, салыстырымның екі бөлігінде оған бөлеміз: $a^{\frac{p - 1}{2}} \equiv ({- 1) }^{\mu}(mod\ p)$ . 3 қасиетті қолдана отырып және Лежандра таңбасы тек 1 мен -1 мәндерін ғана қабылдайтындығын ескере отырып, біз қажетті теңсіздікті аламыз.

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

6. (2p) =(−1) p2−18, \left( \frac{2}{p} \right) = {( - 1) }^{\frac{p^{2} - 1}{8}}, \яғниp=±1(mod8) p = \pm 1(mod\ 8) болған жағдайда(2p) =1\left( \frac{2}{p} \right) = 1мәні; p=±1(mod8) p = \pm 1(mod\ 8) болған жағдайда(2p) =−1\left( \frac{2}{p} \right) = - 1мәні шығады.

Дәлелдеу: $\ p$ санының модулі бойынша $2 \bullet 1, \ 2 \bullet 2, \ \ldots, \ 2 \bullet \frac{p - 1}{2}$ - шегерімдер жиының қарастырайық. Гаусс леммасындағы белгілеулер бойынша $\mu$ -саны осы жүйенің $\left( \frac{p - 1}{2} \right)$ -ден үлкен элеметтерінің санына тең. Бүтін $m\$ санды қос теңсіздікпен орнатайық: $\frac{p - 1}{2} - 2 < 2m \leq \ \ \frac{p - 1}{2}$ . Онда $\mu = \frac{p - 1}{2} - m$ .

$p$ -нің барлық мүмкін мәндерін анықтау үшін кеслесі есептеулерді кестеге жазайық:

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

Дәлелдеу: $p$ санының модулі бойынша квадраттық шегерімдер $1^{2}$ , $2^{2}$ , . . . , $\left( {(p - 1) /2) }^{2} \right)$ -сандар жүйесімен салытырымға келетін сандар ғана бола алады. Шынында да, $a^{2} \equiv b^{2}(mod\ p)$ үшін $0 < a < b \leq \frac{p - 1}{2}$ -ге $a \equiv b(mod\ p)$ пен $a \equiv - b \equiv p - b(mod\ p)$ болу керек. Ал қалған $\frac{p - 1}{2}$ сандары p санының модулі бойынша квадраттық шегерімі бола алмайды.

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

$$\left( \frac{\mathbf{p}}{\mathbf{q}} \right) \mathbf{=}\mathbf{( - 1) }^{\frac{\mathbf{p - 1}}{\mathbf{2}}\mathbf{\bullet}\frac{\mathbf{q - 1}}{\mathbf{2}}}\left( \frac{\mathbf{q}}{\mathbf{p}} \right)$$

Басқаша айтқанда, егер $p \equiv q \equiv 3(mod\ 4)$ онда $\left( \frac{p}{q} \right) = - \left( \frac{q}{p} \right)$ болады, олай болмаған жағдайда $\left( \frac{p}{q} \right) = \left( \frac{q}{p} \right)$ болады.

Дәлелдеу [2] : $f$ пен $g\$ функцияларын $m$ бүтін санына сәйкес келетін $p$ мен $q$ -дің абсолютті ең кіші шегерімдер арқылы тауып көрейік;

$$\mathbf{f}\left( \mathbf{m} \right) \mathbf{\equiv m}\left( \mathbf{mod\ p} \right) \mathbf{, }$$

$$\mathbf{g}\left( \mathbf{m} \right) \mathbf{\equiv m}\left( \mathbf{mod\ q} \right) \mathbf{. }$$

Қалдық туралы қытай теоремасына сәйкес, $\left\lbrack - \frac{pq - 1}{2}, \frac{pq - 1}{2} \right\rbrack$ -аралықтағы $m$ -нің әр бүтін саны үшін $(f(m), g(m) )$ және керісінше абсолютті ең кіші шегерімдері болады. $P$ - $\left\lbrack 1, \frac{pq - 1}{2} \right\rbrack$ -аралықтағы $m$ -нің әр бүтін саны үшін абсолютті ең кіші шегерімдер жиыны болсын. Белгілейік:

$$\mathbf{P}^{\mathbf{+ +}}\mathbf{=}\left\{ \mathbf{(x, \ y) \in Px > 0, \ y > 0} \right\}\mathbf{, }$$

$$\mathbf{P}^{\mathbf{- +}}\mathbf{=}\left\{ \mathbf{(x, \ y) \in Px < 0, \ y \geq 0} \right\}\mathbf{, }$$

$$\mathbf{P}^{\mathbf{+ -}}\mathbf{=}\left\{ \mathbf{(x, \ y) \in Px \geq 0, \ y < 0} \right\}\mathbf{. }$$

Мұндағы $N^{+ +}, \ N^{- +}, \ N^{+ -}$ -сандары $P^{+ +}, \ P^{- +}, \ P^{+ -}$ -жиындарының мүшелерінің саның көрсетеді.

Р жиыныныңда дәл $\frac{p - 1}{2}$ сәйкес (х, у) нүктелері бар және мұндағы $у = 0$ , бұл $(f(mq), \ 0)$ түріндегі нүктелер және мұндағы $m = 1, \ \ 2, \ \ldots, \ \ \frac{p - 1}{2}$ . $u$ - $f(mq) < 0$ теңсіздігін қанағаттандыратын нүктелер саны болсын. Сол сияқты, Р жиыныныңда дәл $\frac{q - 1}{2}$ сәйкес (х, у) нүктелері бар және мұндағы $x = 0$ , бұл $(0, \ g(np) )$ түріндегі нүктелер және мұндағы $n = 1, \ \ 2, \ \ldots, \ \ \frac{p - 1}{2}$ . $v$ - $g(np) < 0$ теңсіздігін қанағаттандыратын нүктелер саны болсын.

Р жиыныныңда $\ f(m) > 0$ теңсіздігі үшін дәл $\frac{p - 1}{2}\left( \frac{q - 1}{2} + 1 \right)$ нүкте бар, бұл $m = k + lp$ - сандарына сәйкес келетін $(f(m), \ g(m) ) \$ -нүктелері, мұнда: $1 \leq k \leq \frac{p - 1}{2}$ , $1 \leq l \leq \frac{q - 1}{2}$ . Демек,

$\mathbf{N}^{\mathbf{+ +}}\mathbf{+ \ }\mathbf{N}^{\mathbf{+ -}}\mathbf{=}\frac{\mathbf{p - 1}}{\mathbf{2}}\left( \frac{\mathbf{q - 1}}{\mathbf{2}}\mathbf{+ 1} \right) \mathbf{-}\left( \frac{\mathbf{p - 1}}{\mathbf{2}}\mathbf{+ u} \right) \mathbf{+ v =}\frac{\mathbf{p - 1}}{\mathbf{2}}\mathbf{\bullet}\frac{\mathbf{q - 1}}{\mathbf{2}}\mathbf{+ u + v}.$

Сол сияқты да $N^{+ +} + \ N^{- +} = \frac{p - 1}{2} \bullet \frac{q - 1}{2} + u + v.$

$f$ пен $g\$ функциялары тақ болып келеді: $f( - m) = - f(m) \$ , $g( - m) = - g(m)$ , сол себептен, осындай бүтін сандардың кез-келген жұбы үшін $х \neq 0$ , $у \neq 0$ , бұл $x \in \left\lbrack - \frac{p - 1}{2}, \ \frac{p - 1}{2}\ \right\rbrack$ , $y \in \left\lbrack - \frac{q - 1}{2}, \ \frac{q - 1}{2}\ \right\rbrack$ , және (х, у) не (-х, -у) нүктелерінің біреуі ғана Р жиынына кіреді. Демек:

$$\mathbf{N}^{\mathbf{+ +}}\mathbf{+ \ }\mathbf{N}^{\mathbf{- +}}\mathbf{=}\frac{\mathbf{p - 1}}{\mathbf{2}}\mathbf{\bullet}\frac{\mathbf{q - 1}}{\mathbf{2}}\mathbf{+ u + v. }$$

Осыдан:

$$\mathbf{2(N}^{\mathbf{+ +}}\mathbf{+ \ }\mathbf{N}^{\mathbf{+ -}}\mathbf{+ \ }\mathbf{N}^{\mathbf{- +}}\mathbf{) = 3}\left( \frac{\mathbf{p - 1}}{\mathbf{2}}\mathbf{\bullet}\frac{\mathbf{q - 1}}{\mathbf{2}}\mathbf{+}\mathbf{u}\mathbf{+}\mathbf{v} \right) \mathbf{. }$$

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

$$\mathbf{0 \equiv}\frac{\mathbf{p - 1}}{\mathbf{2}}\mathbf{\bullet}\frac{\mathbf{q - 1}}{\mathbf{2}}\mathbf{+ u + v}\left( \mathbf{mod\ 2} \right) \mathbf{, }$$

яғни:

$$\frac{\mathbf{p - 1}}{\mathbf{2}}\mathbf{\bullet}\frac{\mathbf{q - 1}}{\mathbf{2}}\mathbf{\equiv u + v}\left( \mathbf{mod\ 2} \right)$$

және:

---

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

• Іс жүргізу
• Автоматтандыру, Техника
• Алғашқы әскери дайындық
• Астрономия
• Ауыл шаруашылығы
• Банк ісі
• Бизнесті бағалау
• Биология
• Бухгалтерлік іс
• Валеология
• Ветеринария
• География
• Геология, Геофизика, Геодезия
• Дін
• Ет, сүт, шарап өнімдері
• Жалпы тарих
• Жер кадастрі, Жылжымайтын мүлік
• Журналистика
• Информатика
• Кеден ісі
• Маркетинг
• Математика, Геометрия
• Медицина
• Мемлекеттік басқару
• Менеджмент
• Мұнай, Газ
• Мұрағат ісі
• Мәдениеттану
• ОБЖ (Основы безопасности жизнедеятельности)
• Педагогика
• Полиграфия
• Психология
• Салық
• Саясаттану
• Сақтандыру
• Сертификаттау, стандарттау
• Социология, Демография
• Спорт
• Статистика
• Тілтану, Филология
• Тарихи тұлғалар
• Тау-кен ісі
• Транспорт
• Туризм
• Физика
• Философия
• Халықаралық қатынастар
• Химия
• Экология, Қоршаған ортаны қорғау
• Экономика
• Экономикалық география
• Электротехника
• Қазақстан тарихы
• Қаржы
• Құрылыс
• Құқық, Криминалистика
• Әдебиет
• Өнер, музыка
• Өнеркәсіп, Өндіріс