Кіріспе

Модульдік арифметикада, n теріс емес бүтін сандар жиынынан n-ге өзімен жақын (өте жақын) сандардың көбейтіндісі модуль n бойынша топ құрайды, бұл топ модульдік n бүтін сандардың көбейту тобы деп аталады. Басқаша айтқанда, осы топтың элементтерін n-ге өзімен жақын конгруэнттік кластар деп қарастыруға болады, сонымен қатар n модулі бойынша қалдықтар деп те атайды. Сондықтан, тағы бір атауы – n модулі бойынша примитивті қалдық кластар тобы. Сақиналар теориясында, абстрактілік алгебраның бір саласы, бұл топ модульдік n бүтін сандар сақинасының бірліктері тобы ретінде сипатталады. Мұндағы бірліктер – көбейтуге кері элементтері бар элементтерді білдіреді, ал осы сақинада олар n-ге өзімен жақын болып табылады.

Бұл топтың бөліндісі, әдетте белгіленеді, сандар теориясындағы негізгі ұғым болып табылады. Ол криптографияда, бүтін сандарды жіктеуде және жай сан тестілеуде қолданылады. Бұл абельдік, шекті топ, оның реті Эйлердің φ(n) функциясымен беріледі: n жай сан болғанда топ циклдік болады, ал жалпы құрылымын сипаттау оңай, бірақ генераторларды табуға арналған қарапайым жалпы формула белгісіз.

Топтық аксиомалар

Көбейту операциясы бойынша, n-ге өзімен жақын сандардың конгруэнция кластары жиыны абельдік топ аксиомаларын қанағаттандыратынын көрсету оңай. Шындығында, a саны n-ге өзімен жақын болса және тек қана 1= [[ең үлкен ортақ бөлгіш. Бір конгруэнция класындағы бүтін сандар a ≡ b (mod n) үшін 1= gcd(a, n) = gcd(b, n) болады; демек, біреуі n-ге өзімен жақын болса, екіншісі де солай болуы керек. Осылайша, n-ге өзімен жақын конгруэнция кластарының түсінігі дұрыс анықталған. Егер 1=gcd(a, n) = 1 және 1=gcd(b, n) = 1 болса, онда 1=gcd(ab, n) = 1 екендігін білдіреді, сондықтан n-ге өзімен жақын кластар жиыны көбейту операциясы бойынша жабық. Бүтін сандарды көбейту конгруэнция кластарын сақтайды, яғни егер a ≡ a' және b ≡ b' (mod n) болса, онда ab ≡ a'b' (mod n) болады. Бұл көбейту операциясының ассоциативті, коммутативті екенін және 1 класы бірегей көбейтулік бірлік екенін көрсетеді. Соңында, a берілген болса, n-ге көбейтуге кері x бүтін саны ax ≡ 1 (mod n) шартын қанағаттандырады. Ол тек қана a саны n-ге өзімен жақын болғанда ғана болады, себебі бұл жағдайда 1=gcd(a, n) = 1 және Безу леммасы бойынша 1=ax + ny = 1 теңдеуін қанағаттандыратын x және y бүтін сандары табылады. 1=ax + ny = 1 теңдеуі x санының n-ге өзімен жақын екенін білдіреді, сондықтан көбейтуге кері сан топқа жатады.

Нөмірлік

Қосу және көбейту операцияларымен модуль n бүтін сандарының (конгруэнттік сыныптарының) жиыны сақина болып табылады. Ол немесе деп белгіленеді (бұл белгілеу бүтін сандардың n-нің еселігінен тұратын идеалға қатысты бөлуді білдіреді). Сандар теориясынан тыс жағдайларда қарапайым жазу жиі қолданылады, бірақ n-нің алғашқы сан болған жағдайында ол p-адық бүтін сандармен шатастырылуы мүмкін. Бұл сақинадағы бірліктер тобы болып табылатын модуль n бүтін сандарының көбейту тобы (авторға байланысты) (неміс тіліндегі Einheit, яғни "бірлік" сөзінен) немесе ұқсас белгілермен жазылуы мүмкін. Бұл мақалада келесі белгілеу қолданылады.

белгілеуі n реттік циклдік топты білдіреді.
Ол қосу бойынша модуль n бүтін сандарының тобына изоморфты. Ескеріңіз, немесе де қосу бойынша топты білдіруі мүмкін. Мысалы, p алғашқы саны үшін көбейтуші топ циклдік және демек, қосылмалы топқа изоморфты, бірақ бұл изоморфизм анық емес.

Құрылымы

n модульдік бүтін сандардың көбейту тобының реті – n-мен өзара жай сандардың саны. Ол Эйлердің φ(n) функциясы арқылы беріледі: жай сан p үшін, φ(p) = p-1.

Жалған куәлардың кіші тобы

Егер n құрама сан болса, онда ,-ның "жалған куәгерлер тобы" деп аталатын дұрыс кіші тобы бар, ол теңдеудің шешімдерін қамтиды, яғни n-1 дәрежеге көтерілгенде n модулі бойынша 1-ге конгруэнтті болатын элементтер. Ферманың кіші теоремасы n = p жай сан болғанда, бұл топтың барлық элементтерінен тұратынын айтады; демек, n құрама сан болғанда, мұндай қалдықтар x, n санының жай сан екендігіне қатысты "жалған оң нәтиже" немесе "жалған куәгер" болып табылады. x = 2 саны осы қарапайым жайлықты тексеруде ең көп қолданылады, ал n = 341 = 11 × 31 саны ерекше, себебі , және n = 341 - x = 2 жайлыққа қатысты жалған куәгер болатын ең кіші құрама сан. Шындығында, 341 саны үшін жалған куәгерлер кіші тобы 100 элементтен тұрады және 300 элементтен тұратын топтың ішінде 3-індексі бар.

n = 9

Жалған куәлардың тривиальды емес кіші тобы бар ең кіші мысал 1=9 = 3 × 3. 9-ға өзіндік жақын сандар: 1, 2, 4, 5, 7, 8 – барлығы 6 сандар. 8 саны 9 модулі бойынша -1-ге сәйкес келетіндіктен, 88 саны да 9 модулі бойынша 1-ге сәйкес келеді. Осылайша, 1 және 8 сандары 9 санының "жай сан" екендігіне қате оң нәтижелер береді (өйткені 9 шын мәнінде жай сан емес). Бұл, шындығында, жалғыз куәгерлер, сондықтан {1,8} – жалған куәлардың кіші тобы. Сол аргумент бойынша, кез келген тақ құрама сан n үшін n-1 – "жалған куә" болады.

n = 91

n = 91 (= 7 × 13) үшін 91-ге өзімен ортақ бөлшегі жоқ қалдықтар бар, олардың жартысы (яғни 36-сы) 91 санының жалған куәгерлері болып табылады, атап айтқанда 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88 және 90, себебі x-тің осы мәндері үшін x90 саны 91-ге бөлінгенде 1 қалдық береді.

n = 561

n = 561 (= 3 × 11 × 17) – Кармайкл саны, демек, 561-ге өзіндік жақын (coprime) болатын кез келген s бүтін саны үшін s560 саны 1-ге модуль 561 бойынша конгруэнтті. Бұл жағдайда жалған куәгерлердің ішкі тобы дұрыс емес; ол 561 модульді көбейту бірліктерінің толық тобын құрайды, ол 320 қалдықтан тұрады.