Сандар теориясынын негиздери
Сандар теориясы - бүтүн сандардын касиеттерин изилдеген математиканын бир тармагы. Сырткы көрүнүшү жөнөкөй болгону менен — бүтүн сандар жөн гана …, -2, -1, 0, 1, 2, … камтыйт — сан теориясы укмуштуудай бай түзүлүшкө ээ. Заманбап математикадагы, криптографиядагы жана информатикадагы көптөгөн маанилүү түшүнүктөр сан теориясынын бөлүнүүчүлүк, жөнөкөй сан жана конгруэнция сыяктуу фундаменталдык идеяларына негизделген. Бул макалада сан теориясынын негизги негиздери: бөлүнүүчүлүк жана Евклиддин алгоритми, жөнөкөй сандар жана факторизация, модулдук арифметика жана кээ бир өнүккөн колдонмолор жана багыттар каралат.
1. Бүтүн сандар жана негизги амалдар
Сандар теориясы, адатта, ℤ менен белгиленген бүтүн сандар жыйындысы боюнча иштейт. Колдонулган негизги амалдар кошуу, кемитүү жана көбөйтүү болуп саналат. Рационалдык же чыныгы сандардан айырмаланып, бүтүн сандарга бөлүү дайыма эле бүтүн санды бере бербейт. Дал ушул жерде калдык менен бөлүү түшүнүгү борбордук орунга чыгат.
Сандар теориясындагы маанилүү байланыштардын бири - бөлүнүүчүлүк. \(a\) жана \(b\) бүтүн сандары үчүн, эгерде \(b = ak\) болгондой \(k\) бүтүн сан болсо, \(a\mid b\) деп жазабыз. Мисалы, \(3\mid 12\) анткени \(12 = 3 \4\), бирок \(5\mid 12\) анткени \(12 = 5k\) болгон \(k\) бүтүн сан жок.
Бөлүнүүчүлүк төмөнкү негизги касиеттерге ээ:
– Эгерде \(a \mid b\) жана \(a \mid c\) болсо, анда \(a \mid (b+c)\) жана \(a \mid (bc)\).
– Эгерде \(a \mid b\) болсо, анда ар бир \(k\) бүтүн сан үчүн \(a \mid (bk)\).
– Эгерде \(a \mid b\) жана \(b \mid c\) болсо, анда \(a \mid c\).
Бул жөнөкөй касиеттер бүтүн сандар жөнүндөгү көптөгөн билдирүүлөрдү далилдөө үчүн курал катары кызмат кылат.
2. Бөлүү алгоритми
Бөлүү теоремасы мындай дейт: ар бир бүтүн сан \(a\) жана оң бүтүн сан \(b\) үчүн төмөнкүдөй уникалдуу бүтүн сандар \(q\) жана \(r\) бар:
\[
a = bq + r,\quad 0 \le r < b
\]
Di sini \(q\) disebut hasil bagi (quotient) dan \(r\) disebut sisa (remainder). Contoh: jika \(a=29\) dan \(b=5\), maka \(29 = 5\cdot 5 + 4\), sehingga \(q=5\) dan \(r=4\).
Konsep ini penting karena menjadi dasar operasi modulo dan algoritma Euclid untuk mencari FPB.
3. Faktor persekutuan terbesar (FPB) dan algoritma Euclid
Untuk dua bilangan bulat \(a\) dan \(b\) (tidak keduanya nol), faktor persekutuan terbesar atau FPB —dilambangkan \(\gcd(a,b)\)—adalah bilangan bulat positif terbesar yang membagi keduanya.
Cara paling efisien untuk menghitung FPB adalah algoritma Euclid . Berdasarkan teorema pembagian, jika:
\[
a = bq + r
\]
maka:
\[
\gcd(a,b) = \gcd(b,r)
\]
Proses ini diulang sampai sisa \(r\) menjadi 0. Pada langkah terakhir, FPB adalah bilangan pembagi terakhir yang bukan nol.
Contoh cepat: cari \(\gcd(48,18)\).
- \(48 = 18\cdot 2 + 12\)
- \(18 = 12\cdot 1 + 6\)
- \(12 = 6\cdot 2 + 0\)
Maka \(\gcd(48,18)=6\).
Algoritma Euclid sangat penting karena cepat bahkan untuk bilangan besar, sehingga sangat berguna dalam komputasi.
4. Kombinasi linear dan identitas Bézout
Salah satu hasil fundamental adalah identitas Bézout : untuk bilangan bulat \(a\) dan \(b\) yang tidak keduanya nol, terdapat bilangan bulat \(x\) dan \(y\) sehingga:
\[
\gcd(a,b) = ax + by
\]
Artinya FPB dapat ditulis sebagai kombinasi linear dari \(a\) dan \(b\). Nilai \(x\) dan \(y\) dapat ditemukan dengan algoritma Euclid diperluas .
Identitas Bézout menjadi kunci dalam menyelesaikan:
- persamaan Diofantin linear \(ax+by=c\),
- mencari invers modulo (penting dalam kriptografi).
5. Bilangan prima dan faktorisasi
Bilangan prima adalah bilangan bulat positif lebih besar dari 1 yang hanya memiliki dua pembagi positif: 1 dan dirinya sendiri. Bilangan seperti 2, 3, 5, 7, 11 adalah prima. Bilangan yang lebih besar dari 1 namun bukan prima disebut komposit , misalnya 12, 21, 35.
Konsep paling terkenal adalah Teorema Dasar Aritmetika : setiap bilangan bulat \(n>1\) dapat ditulis secara unik (hingga urutan) sebagai hasil kali bilangan prima:
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
Мисалня:
\[
360 = 2^3 \cdot 3^2 \cdot 5
\]
Факторизациялоонун бул уникалдуулугу көптөгөн алдыңкы темалардын, анын ичинде чоң сандарды факторизациялоонун татаалдыгына негизделген RSA криптографиясынын негизи болуп саналат.
6. Конгруэнция жана модулдук арифметика
Модульдук арифметика бөлүүнүн калдыгына негизделген сандарды изилдейт. Биз мындай дейбиз:
\[
a \equiv b \pmod{m}
\]
эгерде \(m \mid (ab)\) болсо, анда \(a\) жана \(b\) сандарын \(m\) санына бөлгөндө бирдей калдыкка ээ болот дегенди билдирет.
Мисал: \(17 \equiv 5 \pmod{12}\) анткени \(17-5=12\) 12ге бөлүнөт. 12 модулунда 17 жана 5 барабар деп эсептелет.
Конгруэнция кадимки операциялар менен бирдей касиеттерге ээ:
– Эгерде \(a \equiv b \pmod{m}\) жана \(c \equiv d \pmod{m}\) болсо, анда
\(a+c \equiv b+d \pmod{m}\) жана \(ac \equiv bd \pmod{m}\).
Модулдук арифметика төмөнкүлөр үчүн абдан пайдалуу:
– мезгилдүү үлгүлөрдү аныктоо,
– көбөйткүчтөрдү текшерүү,
– натыйжалуу эсептөө алгоритмдерин иштеп чыгуу,
– жана заманбап криптография.
7. Модулдук тескери жана конгруэнциялык теңдемелер
Эгерде √x√ саны төмөнкүдөй болсо, √a√ саны √m√ санына тескери модуль менен аныкталат:
\[
ax \equiv 1 \pmod{m}
\]
Бул тескери сан, эгерде жана анда гана бар болсо, \(\gcd(a,m)=1\). Мисалы, 3 саны тескери модуль боюнча 7ге барабар, анткени \(3\cdot 5=15\equiv 1 \pmod{7}\), демек анын тескери саны 5ке барабар.
Модулдук тескери түшүнүгү төмөнкүдөй теңдемелерди чыгарууну жеңилдетет:
\[
ax \equiv b \pmod{m}
\]
Эгерде \(a^{-1}\) теңдемесинин тескери мааниси бар болсо, анда чечимди эки тарапты тең көбөйтүү менен алууга болот:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. Ферманын кичине теоремасы жана Эйлер теоремасы
Элементардык сандар теориясындагы эки белгилүү жыйынтык:
1. Ферманын кичине теоремасы: эгерде \(p\) жөнөкөй сан болсо жана \(a\) \(p\) га бөлүнбөсө, анда:
\[
a^{p-1} \эквиваленти 1 \pmod{p}
\]
2. Эйлердин теоремасы (жалпылоо): эгер \(\gcd(a,m)=1\) болсо, анда:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
мында \(\varphi(m)\) - Эйлердин тотьен функциясы (1 жана \(m\) ортосундагы \(m\)ге салыштырмалуу жөнөкөй сандардын саны).
Бул теоремалар ар кандай криптографиялык ыкмалардын жана тез модулдук эсептөө ыкмаларынын негизинде жатат.
9. Өркүндөтүлгөн колдонмолор жана багыттар
Ал бүтүн сандар жөнүндөгү жөнөкөй суроо катары башталганы менен, сандар теориясы азыр кеңири тармакка айланды. Анын колдонулушу төмөнкүлөрдү камтыйт:
– Криптография: RSA, Диффи-Хеллман жана эллиптикалык ийри сызыктар жөнөкөй сан, конгруэнция жана модуль боюнча тескери касиеттерди колдонот.
– Информатика: хэштөө, кокустук сан генераторлору жана чоң сандагы эсептөө алгоритмдери.
– Комбинаторика жана коддоо теориясы: каталарды оңдоочу коддорду жана дискреттик структураларды түзүү.
Бул негиздерден кийин көп учурда изилденүүчү татаал темаларга сызыктуу эмес Диофант теңдемелери, квадраттык калдыктар, алгебралык сандар теориясы жана жөнөкөй сандардын бөлүштүрүлүшү кирет.
Penutup
Сандар теориясынын негиздери бөлүнүүчүлүк, ЭКБ, жөнөкөй сандар жана конгруэнция түшүнүктөрүнө негизделген. Евклиддин алгоритминен баштап модулдук арифметикага чейин, ар бир идея бүтүн сандардын түзүлүшүн түшүнүү үчүн негиз түзөт жана реалдуу дүйнөдөгү колдонмолорго, айрыкча санарип доорунда жол ачат. Бул элементардык түшүнүктөрдү өздөштүрүү дискреттик математикалык маселелерди талдоо жана заманбап сандар теориясындагы терең темаларды изилдөө үчүн күчтүү куралдарды камсыз кылат.
