Сандар теориясының негіздері
Сандар теориясы - бүтін сандардың қасиеттерін зерттейтін математика саласы. Сырттай қарапайым болғанымен - бүтін сандар жай ғана …, -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 \] Мұндағы \(q\) бөлінді деп аталады, ал \(r\) қалдық деп аталады. Мысал: егер \(a=29\) және \(b=5\) болса, онда \(29 = 5\cdot 5 + 4\), сондықтан \(q=5\) және \(r=4\). Бұл тұжырымдама маңызды, себебі ол негіз болып табылады Модульге бөлу операциясы және Эвклидтің ЖББ табу алгоритмі. 3. Ең үлкен ортақ бөлгіш (ЖББ) және Евклид алгоритмі \(a\) және \(b\) екі бүтін сан үшін (екеуі де нөлге тең емес), ең үлкен ортақ бөлгіш немесе ЖББ — \(\gcd(a,b)\) деп белгіленген — оларды бөлетін ең үлкен оң бүтін сан. ЖББ есептеудің ең тиімді жолы - Евклид алгоритмі. Бөлу теоремасы бойынша, егер: \[a = bq + r\] болса, онда: \[\gcd(a,b) = \gcd(b,r)\] Бұл процесс \(r\) қалдығы 0-ге тең болғанша қайталанады. Соңғы қадамда ЖББ соңғы нөлге тең емес бөлгіш болып табылады. Жылдам мысал: \(\gcd(48,18)\) табыңыз. – \(48 = 18\cdot 2 + 12\) – \(18 = 12\cdot 1 + 6\) – \(12 = 6\cdot 2 + 0\) Сонда \(\gcd(48,18)=6\). Евклид алгоритмі өте маңызды, себебі ол үлкен сандар үшін де жылдам, бұл оны есептеулерде өте пайдалы етеді. 4. Сызықтық комбинациялар және Безутің сәйкестігі Бір негізгі нәтиже - Безудің сәйкестігі: екеуі де нөлге тең емес \(a\) және \(b\) бүтін сандары үшін келесідей \(x\) және \(y\) бүтін сандары бар: \[ \gcd(a,b) = ax + by \] Бұл ЖБҚ-ны \(a\) және \(b\\ сызықтық комбинациясы ретінде жазуға болатынын білдіреді. \(x\) және \(y\) мәндерін кеңейтілген Евклид алгоритмімен табуға болады. Безуттың теңдеуі келесілерді шешуде маңызды рөл атқарады: – сызықтық Диофант теңдеуі \(ax+by=c\), – оның модуліне кері мәнін табу (криптографияда маңызды). 5. Жай сандар және факторизация Жай сан – 1-ден үлкен оң бүтін сан, оның тек екі оң бөлгіші бар: 1 және өзі. 2, 3, 5, 7, 11 сияқты сандар жай сан. 1-ден үлкен, бірақ жай емес сандар құрама сан деп аталады, мысалы, 12, 21, 35. Ең танымал тұжырымдама – Арифметиканың негізгі теоремасы: әрбір бүтін сан \(n>1\) жай сандардың көбейтіндісі ретінде бірмәнді (ретімен) жазылуы мүмкін:
\[
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)} \эквивалент 1 \pmod{m}
\]
мұндағы \(\varphi(m)\) - Эйлердің тотьен функциясы (1 мен \(m\) арасындағы \(m\)-ге салыстырмалы түрде жай сандардың саны).
Бұл теоремалар әртүрлі криптографиялық әдістер мен жылдам модульдік есептеу әдістерінің негізінде жатыр.
9. Кеңейтілген қолданбалар мен нұсқаулар
Бастапқыда бүтін сандар туралы қарапайым сұрақ ретінде қарастырылғанымен, сандар теориясы қазір кең ауқымды салаға айналды. Оның қолданылуына мыналар кіреді:
– Криптография: RSA, Диффи-Хеллман және эллиптикалық қисықтар жай сан, конгруэнттілік және модуль бойынша кері қасиеттерді пайдаланады.
– Информатика: хэштеу, кездейсоқ сандар генераторлары және үлкен сандарды есептеу алгоритмдері.
– Комбинаторика және кодтау теориясы: қателерді түзететін кодтар мен дискретті құрылымдарды құру.
Осы негізгі пәндерден кейін жиі зерттелетін кеңейтілген тақырыптарға сызықтық емес Диофант теңдеулері, квадрат қалдықтар, алгебралық сандар теориясы және жай сандардың таралуы жатады.
Жабу
Сандар теориясының негіздері бөлінгіштік, ЕБШ, жай сандар және конгруэнция ұғымдарына негізделген. Евклид алгоритмінен бастап модульдік арифметикаға дейін әрбір идея бүтін сандардың құрылымын түсінудің негізін құрайды және нақты әлемдегі, әсіресе цифрлық дәуірде қолдануға жол ашады. Бұл қарапайым ұғымдарды меңгеру дискретті математикалық есептерді талдау және қазіргі заманғы сандар теориясындағы терең тақырыптарды зерттеу үшін қуатты құралдарды қамтамасыз етеді.
