|
In modular arithmetic the set of congruence classes relatively prime to the modulus number, say ''n'', form a group under multiplication called the multiplicative group of integers modulo ''n''. It is also called the group of primitive residue classes modulo ''n''. In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo ''n''. (Units refers to elements with a multiplicative inverse.) This group is fundamental in number theory. It has found applications in cryptography, integer factorization, and primality testing. For example, by finding the order of this group, one can determine whether ''n'' is prime: ''n'' is prime if and only if the order is . ==Group axioms== It is a straightforward exercise to show that, under multiplication, the set of congruence classes modulo ''n'' that are relatively prime to ''n'' satisfy the axioms for an abelian group. Because implies that , the notion of congruence classes modulo ''n'' that are relatively prime to ''n'' is well-defined. Since and implies the set of classes relatively prime to ''n'' is closed under multiplication. The natural mapping from the integers to the congruence classes modulo ''n'' that takes an integer to its congruence class modulo ''n'' respects products. This implies that the class containing 1 is the unique multiplicative identity, and also the associative and commutative laws hold. In fact it is a ring homomorphism. Given ''a'', , finding ''x'' satisfying is the same as solving , which can be done by Bézout's lemma. The ''x'' found will have the property that . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Multiplicative group of integers modulo n」の詳細全文を読む スポンサード リンク
|