Сан теориясындағы көбейту реті: n-ге жақын a санының ең кішкентай дәрежесі. Математикалық топтар, Эйлер функциясы φ(n) және модульдік арифметика туралы біліңіз.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Сандар теориясында, оң бүтін сан n және n-ге өзімен ортақ бөлшегі жоқ a бүтін саны берілгенде, a-ның n-ге қатысты көбейту реті – a^k ≡ 1 (mod n) болатын ең кіші оң бүтін сан k. Басқаша айтқанда, a-ның n-ге қатысты көбейту реті – n-ге қатысты қалдықтар сақинасының бірліктер тобындағы a-ның реті болып табылады.
In number theory, given a positive integer n and an integer a coprime to n, the multiplicative order of a modulo n is the smallest positive integer k such that
In other words, the multiplicative order of a modulo n is the order of a in the multiplicative group of the units in the ring of the integers modulo n.
a-ның n-ге қатысты реті кейде былай жазылады: .
The order of a modulo n is sometimes written as .
Қасиеттері
Біз модуль n бүтін сандардың көбейту тобында жұмыс істеп жатқанымызды білмей-ақ, a-ның дәрежелерінің модуль n бойынша тек шекті сандағы әр түрлі мәндерді қабылдайтынын байқап, оның нақты реті бар екенін көрсетуге болады. Сондықтан, «көгершін ұясы» принципіне сәйкес, екі дәреже, мысалы s және t, және жоғалусыздықты сақтай отырып, s > t, сондайынша as ≡ at (mod n) болуы керек. a және n өзара жай сандар болғандықтан, a-ның кері элементі a−1 болады және біз конгруенцияның екі жағын a−t-мен көбейту арқылы as−t ≡ 1 (mod n) аламыз. Көбейту ретінің ұғымы – топ элементтерінің ретінің ерекше жағдайы. n модульді a санының көбейту реті – n-ге өзара жай сандардың n модульді қалдықтарынан тұратын көбейту тобындағы a-ның реті. Бұл Zn сақинасының бірліктерінің тобы; оның φ(n) саны бар, мұнда φ – Эйлердің тотиент функциясы, және U(n) немесе U(Zn) деп белгіленеді. Лагранж теоремасының салдары ретінде, a (mod n) реті әрқашан φ(n)-ді бөледі. Егер a-ның реті φ(n)-ге тең болса, яғни ең үлкен мүмкін мәнге ие болса, онда a, n модульді түпнұсқа түбір деп аталады. Бұл U(n) тобының циклдік екенін және a-ның қалдық класы оны тудырады дегенді білдіреді. a (mod n) реті сондай-ақ λ(n)-ді бөледі, бұл Кармайкл функциясының мәні, және φ(n)-нің бөлінуімен салыстырғанда күштірек тұжырым.
Even without knowledge that we are working in the multiplicative group of integers modulo n, we can show that a actually has an order by noting that the powers of a can only take a finite number of different values modulo n, so according to the pigeonhole principle there must be two powers, say s and t and without loss of generality s > t, such that as ≡ at (mod n). Since a and n are coprime, a has an inverse element a−1 and we can multiply both sides of the congruence with a−t, yielding as−t ≡ 1 (mod n). The concept of multiplicative order is a special case of the order of group elements. The multiplicative order of a number a modulo n is the order of a in the multiplicative group whose elements are the residues modulo n of the numbers coprime to n, and whose group operation is multiplication modulo n. This is the group of units of the ring Zn; it has φ(n) elements, φ being Euler's totient function, and is denoted as U(n) or U(Zn). As a consequence of Lagrange's theorem, the order of a (mod n) always divides φ(n). If the order of a is actually equal to φ(n), and therefore as large as possible, then a is called a primitive root modulo n. This means that the group U(n) is cyclic and the residue class of a generates it. The order of a (mod n) also divides λ(n), a value of the Carmichael function, which is an even stronger statement than the divisibility of φ(n).