WikiDer > Birlik moduli n

Ushbu maqola mumkin talab qilish tozalamoq Vikipediya bilan tanishish uchun sifat standartlari. Muayyan muammo: Kontekstning etishmasligi, aniq misollarning etishmasligi, bilan asosiy farqlarni izohlashning etishmasligi Birlikning ildizi va Cheklangan maydon § Birlik ildizlari. Iltimos yordam bering ushbu maqolani yaxshilang Agar imkoningiz bo'lsa. (2018 yil oktyabr) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Yilda matematika, ya'ni halqa nazariyasi, a k- birlik modulining ildizi n ijobiy uchun butun sonlar k, n ≥ 2, a birlikning ildizi ning halqasida butun sonlar modul n, ya'ni echim x uchun tenglama (yoki muvofiqlik) ${ displaystyle x ^ {k} equiv 1 { pmod {n}}}$. Agar k uchun eng kichik ko'rsatkich x, keyin x deyiladi a ibtidoiy k- birlik modulining ildizi n.^[1] Qarang modulli arifmetik notatsiya va terminologiya uchun.

Buni a bilan aralashtirmang ibtidoiy ildiz moduli nguruhining generatori bo'lgan birliklar butun modullar halqasining n. Modulli ibtidoiy ildizlar n ibtidoiy ${ displaystyle varphi (n)}$-birlik modulining ildizlari n, qayerda ${ displaystyle varphi}$ bu Eylerning totient funktsiyasi.

Birlik ildizlari

Xususiyatlari

• Agar x a k-birlik modulining ildizi n, keyin x teskari bo'lgan birlik (teskari) ${ displaystyle x ^ {k-1}}$. Anavi, x va n bor koprime.
• Agar x birlik, keyin u (ibtidoiy) k- birlik modulining ildizi n, qayerda k bo'ladi multiplikativ tartib ning x modul n.
• Agar x a k-birlik ildizi va ${ displaystyle x-1}$ emas nol bo'luvchi, keyin ${ displaystyle sum _ {j = 0} ^ {k-1} x ^ {j} equiv 0 { pmod {n}}}$, chunki

${ displaystyle (x-1) cdot sum _ {j = 0} ^ {k-1} x ^ {j} equiv x ^ {k} -1 equiv 0 { pmod {n}}.}$

Soni k- ildizlar

Keng tarqalgan qabul qilingan belgining etishmasligi uchun biz sonini belgilaymiz k- birlik modulining uchinchi ildizlari n tomonidan ${ displaystyle f (n, k)}$.Bu bir qator xususiyatlarni qondiradi:

• ${ displaystyle f (n, 1) = 1}$ uchun ${ displaystyle n geq 2}$
• ${ displaystyle f (n, lambda (n)) = varphi (n)}$ bu erda λ Karmikel funktsiyasi va ${ displaystyle varphi}$ bildiradi Eylerning totient funktsiyasi
• ${ displaystyle n mapsto f (n, k)}$ a multiplikativ funktsiya
• ${ displaystyle k mid l f (n, k) mid f (n, l)} ni anglatadi$ bu erda bar belgilanadi bo'linish
• ${ displaystyle f (n, mathrm {lcm} (a, b)) = mathrm {lcm} (f (n, a), f (n, b))}$ qayerda ${ displaystyle mathrm {lcm}}$ belgisini bildiradi eng kichik umumiy
• Uchun asosiy ${ displaystyle p}$, ${ displaystyle forall i in mathbb {N} mavjud j in mathbb {N} f (n, p ^ {i}) = p ^ {j}}$. Dan aniq xaritalash ${ displaystyle i}$ ga ${ displaystyle j}$ ma'lum emas. Agar u ma'lum bo'lgan bo'lsa, unda avvalgi qonun bilan birgalikda baholash uchun usul paydo bo'lar edi ${ displaystyle f}$ tez.

Birlikning ibtidoiy ildizlari

Xususiyatlari

• Modulli ibtidoiy ildizlar uchun mumkin bo'lgan maksimal radius ko'rsatkichi ${ displaystyle n}$ bu ${ displaystyle lambda (n)}$, bu erda λ ni anglatadi Karmikel funktsiyasi.
• Birlikning ibtidoiy ildizi uchun radix ko'rsatkichi a bo'luvchi ning ${ displaystyle lambda (n)}$.
• Har bir bo'luvchi ${ displaystyle k}$ ning ${ displaystyle lambda (n)}$ ibtidoiylikni keltirib chiqaradi ${ displaystyle k}$-birdamlikning ildizi. Siz birini tanlab olishingiz mumkin ${ displaystyle lambda (n)}$- birlikning ibtidoiy ildizi (bu $ phi $ ta'rifi bilan mavjud bo'lishi kerak), nomlangan ${ displaystyle x}$ va quvvatni hisoblang ${ displaystyle x ^ { lambda (n) / k}}$.
• Agar x ibtidoiy k-birlik ildizi, shuningdek birlikning (ibtidoiy emas) ℓ-chi ildizi, keyin k $ Delta $ ning bo'luvchisi. Bu to'g'ri, chunki Bézout kimligi butun sonni beradi chiziqli birikma ning k va ℓ ga teng ${ displaystyle mathrm {gcd} (k, ell)}$. Beri k minimal, shunday bo'lishi kerak ${ displaystyle k = mathrm {gcd} (k, ell)}$ va ${ displaystyle mathrm {gcd} (k, ell)}$ $ Delta $ ning bo'luvchisi.

Ibtidoiy son k- ildizlar

Keng tarqalgan ramzning etishmasligi uchun biz ibtidoiy sonni belgilaymiz k- birlik modulining uchinchi ildizlari n tomonidan ${ displaystyle g (n, k)}$.U quyidagi xususiyatlarni qondiradi:

• ${ displaystyle g (n, k) = { begin {case}> 0 & { text {if}} k mid lambda (n), 0 & { text {aks holda}}. end {case} }}$
• Natijada funktsiya ${ displaystyle k mapsto g (n, k)}$ bor ${ displaystyle d ( lambda (n))}$ noldan farqli qiymatlar, qaerda ${ displaystyle d}$ hisoblaydi bo'linuvchilar soni.
• ${ displaystyle g (n, 1) = 1}$
• ${ displaystyle g (4,2) = 1}$
• ${ displaystyle g (2 ^ {n}, 2) = 3}$ uchun ${ displaystyle n geq 3}$, chunki -1 har doim a kvadrat ildiz 1 dan.
• ${ displaystyle g (2 ^ {n}, 2 ^ {k}) = 2 ^ {k}}$ uchun ${ displaystyle k in [2, n-1)}$
• ${ displaystyle g (n, 2) = 1}$ uchun ${ displaystyle n geq 3}$ va ${ displaystyle n}$ ichida (ketma-ketlik) A033948 ichida OEIS)
• ${ displaystyle sum _ {k in mathbb {N}} g (n, k) = f (n, lambda (n)) = varphi (n)}$ bilan ${ displaystyle varphi}$ bo'lish Eylerning totient funktsiyasi
• Orasidagi bog'liqlik ${ displaystyle f}$ va ${ displaystyle g}$ dan foydalangan holda nafis tarzda yozilishi mumkin Dirichlet konvulsiyasi:

${ displaystyle f = mathbf {1} * g}$, ya'ni ${ displaystyle f (n, k) = sum _ {d mid k} g (n, d)}$

Ning qiymatlarini hisoblashingiz mumkin ${ displaystyle g}$ dan ${ displaystyle f}$ ga teng bo'lgan ushbu formuladan foydalanib Möbius inversiya formulasi.

Yo'qligini tekshirish x ibtidoiy k- birlik modulining ildizi n

By tez daraja buni tekshirishingiz mumkin ${ displaystyle x ^ {k} equiv 1 { pmod {n}}}$. Agar bu to'g'ri bo'lsa, x a k- birlik modulining ildizi n lekin ibtidoiy emas. Agar u ibtidoiy ildiz bo'lmasa, unda $ phi $ ning bo'luvchisi bo'ladi k, bilan ${ displaystyle x ^ { ell} equiv 1 { pmod {n}}}$. Ushbu imkoniyatni istisno qilish uchun bir necha $ ning tengligini tekshirish kerak k asosiy bilan bo'lingan. Ya'ni tekshirilishi kerak bo'lgan narsa:

${ displaystyle forall p { text {prime dividing}} k, quad x ^ {k / p} not equiv 1 { pmod {n}}.}$

Ibtidoiy narsani topish k- birlik modulining ildizi n

Ibtidoiylar orasida k-birlikning dastlabki ildizlari, ibtidoiy ${ displaystyle lambda (n)}$- ildizlar eng tez-tez uchraydi, shuning uchun ibtidoiy bo'lish uchun ba'zi bir butun sonlarni sinash tavsiya etiladi ${ displaystyle lambda (n)}$- uchinchi ildiz, nima tezda muvaffaqiyatli bo'ladi. Ibtidoiy uchun ${ displaystyle lambda (n)}$-chi ildiz x, raqam ${ displaystyle x ^ { lambda (n) / k}}$ ibtidoiy ${ displaystyle k}$-birlik ildizi.If k bo'linmaydi ${ displaystyle lambda (n)}$, keyin yo'q bo'ladi k-birlikning ildizlari, umuman.

Ko'plab ibtidoiy narsalarni topish k-modullar n

Bir marta sizda ibtidoiy narsa bor k-birlikning ildizi x, har qanday kuch ${ displaystyle x ^ {l}}$ a ${ displaystyle k}$- birlikning asosiy ildizi, ammo ibtidoiy emas. Quvvat ${ displaystyle x ^ {l}}$ ibtidoiy ${ displaystyle k}$-agar birdamlikning ildizi ${ displaystyle k}$ va ${ displaystyle l}$ bor koprime. Dalil quyidagicha: Agar ${ displaystyle x ^ {l}}$ ibtidoiy emas, keyin bo'luvchi mavjud ${ displaystyle m}$ ning ${ displaystyle k}$ bilan ${ displaystyle (x ^ {l}) ^ {m} equiv 1 { pmod {n}}}$, va beri ${ displaystyle k}$ va ${ displaystyle l}$ koprime, teskari mavjud ${ displaystyle l ^ {- 1}}$ ning ${ displaystyle l}$ modul ${ displaystyle k}$. Bu hosil beradi ${ displaystyle 1 equiv ((x ^ {l}) ^ {m}) ^ {l ^ {- l}} equiv x ^ {m} { pmod {n}}}$, bu shuni anglatadiki ${ displaystyle x}$ ibtidoiy emas ${ displaystyle k}$-birlik ildizi, chunki kichikroq ko'rsatkich mavjud ${ displaystyle m}$.

Ya'ni, eksponatlash orqali x olish mumkin ${ displaystyle varphi (k)}$ turli xil ibtidoiy k-birlik ildizlari, ammo bularning hammasi ham bunday ildizlar bo'lmasligi mumkin. Biroq, ularning barchasini topish juda oson emas.

Topish n ibtidoiy bilan k-birlik modulining ildizi n

Siz qanday sonda ekanligini bilmoqchi bo'lishingiz mumkin qoldiq sinf uzuklari sizda ibtidoiy narsa bor k-birlikning ildizi. Masalan, agar siz a ni hisoblashni xohlasangiz, bu sizga kerak Alohida Furye konvertatsiyasi (aniqrog'i a Raqamlarning nazariy o'zgarishi) ning ${ displaystyle k}$o'lchovli butun son vektor. Teskari konvertatsiyani amalga oshirish uchun siz ham bo'lishingiz kerak ${ displaystyle k}$, anavi, k shuningdek, modul moduli bo'lishi kerak ${ displaystyle n.}$

Bunday topishning oddiy usuli n ibtidoiylikni tekshirish k-dagi ildizlarga nisbatan arifmetik progressiya ${ displaystyle k + 1,2k + 1,3k + 1, nuqta}$. Ushbu modullarning barchasi o'xshashdir k va shunday qilib k bu birlik. Ga binoan Arifmetik progressiyalar haqidagi Dirichlet teoremasi progressiyada cheksiz sonlar va asosiy darajalar mavjud ${ displaystyle p}$ u ushlab turadi ${ displaystyle lambda (p) = p-1}$. Shunday qilib, agar ${ displaystyle mk + 1}$ u holda asosiy hisoblanadi ${ displaystyle lambda (mk + 1) = mk}$ va shuning uchun sizda ibtidoiy narsa bor k- birlikning ildizlari. Ammo tub sonlar uchun sinov juda kuchli, siz boshqa mos modullarni topishingiz mumkin.

Topish n birlik modulining ko'plab ibtidoiy ildizlari bilan n

Agar siz modulga ega bo'lishni istasangiz ${ displaystyle n}$ ibtidoiy narsalar mavjud ${ displaystyle k_ {1}}$-, ${ displaystyle k_ {2}}$-th, ..., ${ displaystyle k_ {m}}$- birlik modulining uchinchi ildizlari ${ displaystyle n}$, quyidagi teorema muammoni soddasigacha kamaytiradi:

Berilgan uchun ${ displaystyle n}$ ibtidoiy mavjud ${ displaystyle k_ {1}}$-th, ..., ${ displaystyle k_ {m}}$- birlik modulining uchinchi ildizlari ${ displaystyle n}$ agar va faqat ibtidoiy narsa bo'lsa ${ displaystyle mathrm {lcm} (k_ {1}, ..., k_ {m})}$- birlik modulining ildizi n.

Isbot

Orqaga yo'nalish: Agar ibtidoiy narsa bo'lsa ${ displaystyle mathrm {lcm} (k_ {1}, ..., k_ {m})}$-birlik modulining ildizi ${ displaystyle n}$ deb nomlangan ${ displaystyle x}$, keyin ${ displaystyle x ^ { mathrm {lcm} (k_ {1}, dots, k_ {m}) / k_ {l}}}$ a ${ displaystyle k_ {l}}$- birlik modulining ildizi ${ displaystyle n}$.

Oldinga yo'nalish: Agar ibtidoiy bo'lsa ${ displaystyle k_ {1}}$-th, ..., ${ displaystyle k_ {m}}$- birlik modulining uchinchi ildizlari ${ displaystyle n}$, keyin barcha eksponentlar ${ displaystyle k_ {1}, nuqtalar, k_ {m}}$ ning bo'luvchilari ${ displaystyle lambda (n)}$. Bu shuni anglatadi ${ displaystyle mathrm {lcm} (k_ {1}, nuqtalar, k_ {m}) mid lambda (n)}$ va bu o'z navbatida ibtidoiy narsa borligini anglatadi ${ displaystyle mathrm {lcm} (k_ {1}, ..., k_ {m})}$- birlik modulining ildizi ${ displaystyle n}$.

Adabiyotlar