Editing Multiplicative group of integers modulo n

{{DISPLAYTITLE:Multiplicative group of integers modulo ''n''}}
{{Short description|Group of units of the ring of integers modulo n}}
In [[modular arithmetic]], the [[integer]]s [[coprime]] (relatively prime) to ''n'' from the set <math>\{0,1,\dots,n-1\}</math> of ''n'' non-negative integers form a [[group (mathematics)|group]] under multiplication [[integers modulo n|modulo ''n'']], called the '''multiplicative group of integers modulo ''n'''''.  Equivalently, the elements of this group can be thought of as the [[Modular arithmetic#Congruence class|congruence classes]], also known as ''residues'' modulo ''n'', that are coprime to ''n''.
Hence another name is the group of '''primitive residue classes modulo ''n'''''.
In the [[ring (algebra)|theory of rings]], a branch of [[abstract algebra]], it is described as the [[group of units]] of the [[ring of integers modulo n|ring of integers modulo ''n'']]. Here ''units'' refers to elements with a [[Modular multiplicative inverse|multiplicative inverse]], which, in this ring, are exactly those coprime to ''n''.

{{Group theory sidebar|Finite}}

This group, usually denoted <math>(\mathbb{Z}/n\mathbb{Z})^\times</math>, is fundamental in [[number theory]]. It is used in [[cryptography]], [[integer factorization]], and [[primality test]]ing.  It is an [[abelian group|abelian]], [[finite group|finite]] group whose [[order of a group|order]] is given by [[Euler's totient function]]: <math>|(\mathbb{Z}/n\mathbb{Z})^\times|=\varphi(n).</math>  For prime ''n'' the group is [[cyclic group|cyclic]], and in general the structure is easy to describe, but no simple general formula for finding [[Generating set of a group|generators]] is known.

==Group axioms==
It is a straightforward exercise to show that, under multiplication, the set of [[congruence class]]es modulo ''n'' that are coprime to ''n'' satisfy the axioms for an [[abelian group]].

Indeed, ''a'' is coprime to ''n'' if and only if {{nowrap|1= [[greatest common divisor|gcd]](''a'', ''n'') = 1}}. Integers in the same congruence class {{nowrap|''a'' ≡ ''b'' (mod ''n'')}} satisfy {{nowrap|1= gcd(''a'', ''n'') = gcd(''b'', ''n'')}}; hence one is coprime to ''n'' if and only if the other is. Thus the notion of congruence classes modulo ''n'' that are coprime to ''n'' is well-defined.

Since {{nowrap|1=gcd(''a'', ''n'') = 1}} and {{nowrap|1=gcd(''b'', ''n'') = 1}} implies {{nowrap|1=gcd(''ab'', ''n'') = 1}}, the set of classes coprime to ''n'' is closed under multiplication.

Integer multiplication respects the congruence classes; that is, {{nowrap|''a'' ≡ ''a' ''}} and {{nowrap|''b'' ≡ ''b' '' (mod ''n'')}} implies {{nowrap|''ab'' ≡ ''a'b' '' (mod ''n'')}}.
This implies that the multiplication is associative, commutative, and that the class of 1 is the unique multiplicative identity.

Finally, given ''a'', the [[Modular multiplicative inverse|multiplicative inverse]] of ''a'' modulo ''n'' is an integer ''x'' satisfying {{nowrap|''ax'' ≡ 1 (mod ''n'')}}.
It exists precisely when ''a'' is coprime to ''n'', because in that case {{nowrap|1=gcd(''a'', ''n'') = 1}} and by [[Bézout's lemma]] there are integers ''x'' and ''y'' satisfying {{nowrap|1=''ax'' + ''ny'' = 1}}. Notice that the equation {{nowrap|1=''ax'' + ''ny'' = 1}} implies that ''x'' is coprime to ''n'', so the multiplicative inverse belongs to the group.

==Notation==
The set of (congruence classes of) integers modulo ''n'' with the operations of addition and multiplication is a [[Ring (mathematics)|ring]].
It is denoted <math>\mathbb{Z}/n\mathbb{Z}</math>&nbsp; or&nbsp; <math>\mathbb{Z}/(n)</math>&nbsp; (the notation refers to taking the [[Quotient ring|quotient]] of integers modulo the [[Ideal (ring theory)|ideal]] <math>n\mathbb{Z}</math> or <math>(n)</math> consisting of the multiples of ''n'').
Outside of number theory the simpler notation <math>\mathbb{Z}_n</math> is often used, though it can be confused with the [[p-adic number|{{math|<var>p</var>}}-adic integers]] when ''n'' is a prime number.

The multiplicative group of integers modulo ''n'', which is the [[group of units]] in this ring, may be written as (depending on the author) <math>(\mathbb{Z}/n\mathbb{Z})^\times,</math> &nbsp; <math>(\mathbb{Z}/n\mathbb{Z})^*,</math> &nbsp; <math>\mathrm{U}(\mathbb{Z}/n\mathbb{Z}),</math> &nbsp; <math>\mathrm{E}(\mathbb{Z}/n\mathbb{Z})</math> &nbsp; (for German ''Einheit'', which translates as ''unit''), <math>\mathbb{Z}_n^*</math>, or similar notations. This article uses <math>(\mathbb{Z}/n\mathbb{Z})^\times.</math>

The notation <math>\mathrm{C}_n</math> refers to the [[cyclic group]] of order ''n''.
It is [[group isomorphism|isomorphic]] to the group of integers modulo ''n'' under addition.
Note that <math>\mathbb{Z}/n\mathbb{Z}</math> or <math>\mathbb{Z}_n</math> may also refer to the group under addition.
For example, the multiplicative group <math>(\mathbb{Z}/p\mathbb{Z})^\times</math> for a prime ''p'' is cyclic and hence isomorphic to the additive group <math>\mathbb{Z}/(p-1)\mathbb{Z}</math>, but the isomorphism is not obvious.

==Structure==
The order of the multiplicative group of integers modulo ''n'' is the number of integers in <math>\{0,1,\dots,n-1\}</math> coprime to ''n''. It is given by [[Euler's totient function]]: <math>| (\mathbb{Z}/n\mathbb{Z})^\times|=\varphi(n)</math> {{OEIS|id=A000010}}.
For prime ''p'', <math>\varphi(p)=p-1</math>.

===Cyclic case===
{{main article|primitive root modulo n}}
The group <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> is [[cyclic group|cyclic]] if and only if ''n'' is 1, 2, 4, ''p''<sup>''k''</sup> or 2''p''<sup>''k''</sup>, where ''p'' is an odd prime and {{nowrap|''k'' > 0}}. For all other values of ''n'' the group is not cyclic.<ref>{{MathWorld|title=Modulo Multiplication Group|urlname=ModuloMultiplicationGroup}}
</ref><ref>{{Cite web |title=Primitive root - Encyclopedia of Mathematics |url=https://encyclopediaofmath.org/wiki/Primitive_root |access-date=2024-07-06 |website=encyclopediaofmath.org}}</ref><ref name="Vinogradov2003.pp=105-121">{{Harvnb|Vinogradov|2003|loc=§ VI PRIMITIVE ROOTS AND INDICES|pp=105–121}}</ref>
This was first proved by [[Carl Friedrich Gauss|Gauss]].{{sfn|Gauss|1986|loc=arts. 52–56, 82–891}}

This means that for these ''n'':
:<math> (\mathbb{Z}/n\mathbb{Z})^\times \cong \mathrm{C}_{\varphi(n)},</math> where <math>\varphi(p^k)=\varphi(2 p^k)=p^k - p^{k-1}.</math>

By definition, the group is cyclic if and only if it has a [[Generating set of a group|generator]] ''g''; that is, the powers <math>g^0,g^1,g^2,\dots,</math> give all possible residues modulo ''n'' coprime to ''n'' (the first <math>\varphi(n)</math> powers <math>g^0,\dots,g^{\varphi(n)-1}</math> give each exactly once).
A generator of <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> is called a '''[[primitive root modulo n|primitive root modulo ''n'']]'''.{{sfn|Vinogradov|2003|p=106}}
If there is any generator, then there are <math>\varphi(\varphi(n))</math> of them.

===Powers of 2===
Modulo 1 any two integers are congruent, i.e., there is only one congruence class, [0], coprime to 1. Therefore, <math>(\mathbb{Z}/1\,\mathbb{Z})^\times \cong \mathrm{C}_1</math> is the trivial group with {{nowrap|1=φ(1) = 1}} element. Because of its trivial nature, the case of congruences modulo 1 is generally ignored and some authors choose not to include the case of ''n'' = 1 in theorem statements.

Modulo 2 there is only one coprime congruence class, [1], so <math>(\mathbb{Z}/2\mathbb{Z})^\times \cong \mathrm{C}_1</math> is the [[trivial group]].

Modulo 4 there are two coprime congruence classes, [1] and [3], so <math>(\mathbb{Z}/4\mathbb{Z})^\times \cong \mathrm{C}_2,</math> the cyclic group with two elements.

Modulo 8 there are four coprime congruence classes, [1], [3], [5] and [7]. The square of each of these is 1, so <math>(\mathbb{Z}/8\mathbb{Z})^\times \cong \mathrm{C}_2 \times \mathrm{C}_2,</math> the [[Klein four-group]].

Modulo 16 there are eight coprime congruence classes [1], [3], [5], [7], [9], [11], [13] and [15]. <math>\{\pm 1, \pm 7\}\cong \mathrm{C}_2 \times \mathrm{C}_2,</math> is the 2-[[torsion subgroup]] (i.e., the square of each element is 1), so <math>(\mathbb{Z}/16\mathbb{Z})^\times</math> is not cyclic. The powers of 3, <math>\{1, 3, 9, 11\}</math> are a subgroup of order 4, as are the powers of 5, <math>\{1, 5, 9, 13\}.</math> &nbsp;  Thus <math>(\mathbb{Z}/16\mathbb{Z})^\times \cong \mathrm{C}_2 \times \mathrm{C}_4.</math>

The pattern shown by 8 and 16 holds{{sfn|Gauss|1986|loc=arts. 90–91}} for higher powers  2<sup>''k''</sup>, {{nowrap|''k'' > 2}}: <math>\{\pm 1, 2^{k-1} \pm 1\}\cong \mathrm{C}_2 \times \mathrm{C}_2,</math> is the 2-torsion subgroup, so <math>(\mathbb{Z}/2^k\mathbb{Z})^\times </math> cannot be cyclic, and the powers of 3 are a cyclic subgroup of order {{nowrap|1=2<sup>''k'' &minus; 2</sup>}}, so:<blockquote><math>(\mathbb{Z}/2^k\mathbb{Z})^\times \cong \mathrm{C}_2 \times \mathrm{C}_{2^{k-2}}.</math></blockquote>

===General composite numbers===
By the [[fundamental theorem of finite abelian groups]], the group <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> is isomorphic to a [[Direct product of groups|direct product]] of cyclic groups of prime power orders.

More specifically, the [[Chinese remainder theorem]]<ref>Riesel covers all of this. {{Harvnb|Riesel|1994|pp=267–275}}.</ref> says that if <math>\;\;n=p_1^{k_1}p_2^{k_2}p_3^{k_3}\dots, \;</math>  then the ring <math>\mathbb{Z}/n\mathbb{Z}</math> is the [[Product of rings|direct product]] of the rings corresponding to each of its prime power factors:

:<math>\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/{p_1^{k_1}}\mathbb{Z}\; \times \;\mathbb{Z}/{p_2^{k_2}}\mathbb{Z} \;\times\; \mathbb{Z}/{p_3^{k_3}}\mathbb{Z}\dots\;\;</math>

Similarly, the group of units <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> is the direct product of the groups corresponding to each of the prime power factors:

:<math>(\mathbb{Z}/n\mathbb{Z})^\times\cong (\mathbb{Z}/{p_1^{k_1}}\mathbb{Z})^\times \times (\mathbb{Z}/{p_2^{k_2}}\mathbb{Z})^\times  \times (\mathbb{Z}/{p_3^{k_3}}\mathbb{Z})^\times \dots\;.</math>

For each odd prime power <math>p^{k}</math> the corresponding factor <math>(\mathbb{Z}/{p^{k}}\mathbb{Z})^\times</math> is the cyclic group of order <math>\varphi(p^k)=p^k - p^{k-1}</math>, which may further factor into cyclic groups of prime-power orders.
For powers of 2 the factor <math>(\mathbb{Z}/{2^{k}}\mathbb{Z})^\times</math> is not cyclic unless ''k'' = 0, 1, 2, but factors into cyclic groups as described above.

The order of the group <math>\varphi(n)</math> is the product of the orders of the cyclic groups in the direct product.
The [[Exponent of a group|exponent]] of the group; that is, the [[least common multiple]] of the orders in the cyclic groups, is given by the [[Carmichael function]] <math>\lambda(n)</math> {{OEIS|id=A002322}}.
In other words, <math>\lambda(n)</math> is the smallest number such that for each ''a'' coprime to ''n'', <math>a^{\lambda(n)} \equiv 1 \pmod n</math> holds.
It divides <math>\varphi(n)</math> and is equal to it if and only if the group is cyclic.

==Subgroup of false witnesses==
If ''n'' is composite, there exists a possibly proper subgroup of <math>\mathbb{Z}_n^\times</math>, called the "group of false witnesses", comprising the solutions of the equation <math>x^{n-1}=1</math>, the elements which, raised to the power {{nowrap|''n'' − 1}}, are congruent to 1 modulo ''n''.<ref>{{cite journal | zbl=0586.10003 | last1=Erdős | first1=Paul | author1-link=Paul Erdős | last2=Pomerance | first2=Carl | author2-link=Carl Pomerance | title=On the number of false witnesses for a composite number | journal=[[Mathematics of Computation]] | volume=46 | issue=173 | pages=259–279 | year=1986 | doi=10.1090/s0025-5718-1986-0815848-x| doi-access=free }}</ref>  [[Fermat's Little Theorem]] states that for ''n = p'' a prime, this group consists of all <math>x\in \mathbb{Z}_p^\times</math>; thus for ''n'' composite, such residues ''x'' are "false positives" or "false witnesses" for the primality of ''n''. The number ''x ='' 2 is most often used in this basic primality check, and ''n ='' {{nowrap|1=341 = 11 × 31}} is notable since  <math>2^{341-1}\equiv 1 \mod 341</math>, and ''n ='' 341 is the smallest composite number for which ''x ='' 2 is a false witness to primality. In fact, the false witnesses subgroup for 341 contains 100 elements, and is of index 3 inside the 300-element group <math>\mathbb{Z}_{341}^\times</math>.

===Examples===
====''n'' = 9====
The smallest example with a nontrivial subgroup of false witnesses is {{nowrap|1=9 = 3 × 3}}. There are 6 residues coprime to 9: 1, 2, 4, 5, 7, 8. Since 8 is congruent to {{nowrap|−1 modulo 9}}, it follows that 8<sup>8</sup> is congruent to 1 modulo 9. So 1 and 8 are false positives for the "primality" of 9 (since 9 is not actually prime). These are in fact the only ones, so the subgroup {1,8} is the subgroup of false witnesses. The same argument shows that {{nowrap|''n'' − 1}} is a "false witness" for any odd composite ''n''.
====''n'' = 91====
For ''n'' = 91 (= 7 × 13), there are <math>\varphi(91)=72</math> residues coprime to 91, half of them (i.e., 36 of them) are false witnesses of 91, namely 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, and 90, since for these values of ''x'', ''x''<sup>90</sup> is congruent to 1 mod 91.

====''n'' = 561====
''n'' = 561 (= 3 × 11 × 17) is a [[Carmichael number]], thus ''s''<sup>560</sup> is congruent to 1 modulo 561 for any integer ''s'' coprime to 561. The subgroup of false witnesses is, in this case, not proper; it is the entire group of multiplicative units modulo 561, which consists of 320 residues.

==Examples==

This table shows the cyclic decomposition of <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> and a [[Generating set of a group|generating set]] for ''n'' ≤ 128. The decomposition and generating sets are not unique; for example, 

<math> \displaystyle \begin{align}(\mathbb{Z}/35\mathbb{Z})^\times & \cong (\mathbb{Z}/5\mathbb{Z})^\times \times (\mathbb{Z}/7\mathbb{Z})^\times  \cong \mathrm{C}_4 \times \mathrm{C}_6 \cong \mathrm{C}_4 \times \mathrm{C}_2 \times \mathrm{C}_3 \cong \mathrm{C}_2 \times \mathrm{C}_{12} \cong (\mathbb{Z}/4\mathbb{Z})^\times \times (\mathbb{Z}/13\mathbb{Z})^\times  \\ & \cong (\mathbb{Z}/52\mathbb{Z})^\times \end{align} </math> 

(but <math>\not\cong \mathrm{C}_{24} \cong \mathrm{C}_8 \times \mathrm{C}_3</math>). The table below lists the shortest decomposition (among those, the lexicographically first is chosen – this guarantees isomorphic groups are listed with the same decompositions). The generating set is also chosen to be as short as possible, and for ''n'' with primitive root, the smallest primitive root modulo ''n'' is listed.

For example, take <math>(\mathbb{Z}/20\mathbb{Z})^\times</math>. Then <math>\varphi(20)=8</math> means that the order of the group is 8 (i.e., there are 8 numbers less than 20 and coprime to it); <math>\lambda(20)=4</math> means the order of each element divides 4; that is, the fourth power of any number coprime to 20 is congruent to 1 (mod 20). The set {3,19} generates the group, which means that every element of <math>(\mathbb{Z}/20\mathbb{Z})^\times</math> is of the form {{nowrap|3<sup>''a''</sup> × 19<sup>''b''</sup>}} (where ''a'' is 0, 1, 2, or 3, because the element 3 has order 4, and similarly ''b'' is 0 or 1, because the element 19 has order 2).

Smallest primitive root mod ''n'' are (0 if no root exists)
:0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ... {{OEIS|id=A046145}}

Numbers of the elements in a minimal generating set of mod ''n'' are
:1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ... {{OEIS|id=A046072}}

<div style="overflow:auto">
{|  class="wikitable" style="text-align:center" cellpadding="2"
|+ Group structure of <math>(\mathbb{Z}/n\mathbb{Z})^\times</math>
|-
 ! <math>n\;</math> !! <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> !! <math>\varphi(n)</math> !! <math>\lambda(n)\;</math> !! Generating&nbsp;set
 | width="25" rowspan="33" | &nbsp;
 ! <math>n\;</math> !! <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> !! <math>\varphi(n)</math> !! <math>\lambda(n)\;</math> !! Generating&nbsp;set
 | width="25" rowspan="33" | &nbsp;
 ! <math>n\;</math> !! <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> !! <math>\varphi(n)</math> !! <math>\lambda(n)\;</math> !! Generating&nbsp;set
 | width="25" rowspan="33" | &nbsp;
 ! <math>n\;</math> !! <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> !! <math>\varphi(n)</math> !! <math>\lambda(n)\;</math> !! Generating&nbsp;set
|-
 ! 1
 | C<sub>1</sub> || 1 || 1 || 0
 ! 33
 | C<sub>2</sub>×C<sub>10</sub> || 20 || 10 || 2, 10
 ! 65
 | C<sub>4</sub>×C<sub>12</sub> || 48 || 12 || 2, 12
 ! 97
 | C<sub>96</sub> || 96 || 96 || 5
|-
 ! 2
 | C<sub>1</sub> || 1 || 1 || 1
 ! 34
 | C<sub>16</sub> || 16 || 16 || 3
 ! 66
 | C<sub>2</sub>×C<sub>10</sub> || 20 || 10 || 5, 7
 ! 98
 | C<sub>42</sub> || 42 || 42 || 3
|-
 ! 3
 | C<sub>2</sub> || 2 || 2 || 2
 ! 35
 | C<sub>2</sub>×C<sub>12</sub> || 24 || 12 || 2, 6
 ! 67
 | C<sub>66</sub> || 66 || 66 || 2
 ! 99
 | C<sub>2</sub>×C<sub>30</sub> || 60 || 30 || 2, 5
|-
 ! 4
 | C<sub>2</sub> || 2 || 2 || 3
 ! 36
 | C<sub>2</sub>×C<sub>6</sub> || 12 || 6 || 5, 19
 ! 68
 | C<sub>2</sub>×C<sub>16</sub> || 32 || 16 || 3, 67
 ! 100
 | C<sub>2</sub>×C<sub>20</sub> || 40 || 20 || 3, 99
|-
 ! 5
 | C<sub>4</sub> || 4 || 4 || 2
 ! 37
 | C<sub>36</sub> || 36 || 36 || 2
 ! 69
 | C<sub>2</sub>×C<sub>22</sub> || 44 || 22 || 2, 68
 ! 101
 | C<sub>100</sub> || 100 || 100 || 2
|-
 ! 6
 | C<sub>2</sub> || 2 || 2 || 5
 ! 38
 | C<sub>18</sub> || 18 || 18 || 3
 ! 70
 | C<sub>2</sub>×C<sub>12</sub> || 24 || 12 || 3, 69
 ! 102
 | C<sub>2</sub>×C<sub>16</sub> || 32 || 16 || 5, 101
|-
 ! 7
 | C<sub>6</sub> || 6 || 6 || 3
 ! 39
 | C<sub>2</sub>×C<sub>12</sub>  || 24 || 12 || 2, 38
 ! 71
 | C<sub>70</sub> || 70 || 70 || 7
 ! 103
 | C<sub>102</sub> || 102 || 102 || 5
|-
 ! 8
 | C<sub>2</sub>×C<sub>2</sub> || 4 || 2 || 3, 5
 ! 40
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>4</sub> || 16 || 4 || 3, 11, 39
 ! 72
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>6</sub> || 24 || 6 || 5, 17, 19
 ! 104
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>12</sub> || 48 || 12 || 3, 5, 103
|-
 ! 9
 | C<sub>6</sub> || 6 || 6 || 2
 ! 41
 | C<sub>40</sub> || 40 || 40 || 6
 ! 73
 | C<sub>72</sub> || 72 || 72 || 5
 ! 105
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>12</sub> || 48 || 12 || 2, 29, 41
|-
 ! 10
 | C<sub>4</sub> || 4 || 4 || 3
 ! 42
 | C<sub>2</sub>×C<sub>6</sub> || 12 || 6 || 5, 13
 ! 74
 | C<sub>36</sub> || 36 || 36 || 5
 ! 106
 | C<sub>52</sub> || 52 || 52 || 3
|-
 ! 11
 | C<sub>10</sub> || 10 || 10 || 2
 ! 43
 | C<sub>42</sub> || 42 || 42 || 3
 ! 75
 | C<sub>2</sub>×C<sub>20</sub> || 40 || 20 || 2, 74
 ! 107
 | C<sub>106</sub> || 106 || 106 || 2
|-
 ! 12
 | C<sub>2</sub>×C<sub>2</sub> || 4 || 2 || 5, 7
 ! 44
 | C<sub>2</sub>×C<sub>10</sub> || 20 || 10 || 3, 43
 ! 76
 | C<sub>2</sub>×C<sub>18</sub> || 36 || 18 || 3, 37
 ! 108
 | C<sub>2</sub>×C<sub>18</sub> || 36 || 18 || 5, 107
|-
 ! 13
 | C<sub>12</sub> || 12 || 12 || 2
 ! 45
 | C<sub>2</sub>×C<sub>12</sub> || 24 || 12 || 2, 44
 ! 77
 | C<sub>2</sub>×C<sub>30</sub> || 60 || 30 || 2, 76
 ! 109
 | C<sub>108</sub> || 108 || 108 || 6
|-
 ! 14
 | C<sub>6</sub> || 6 || 6 || 3
 ! 46
 | C<sub>22</sub> || 22 || 22 || 5
 ! 78
 | C<sub>2</sub>×C<sub>12</sub> || 24 || 12 || 5, 7
 ! 110
 | C<sub>2</sub>×C<sub>20</sub> || 40 || 20 || 3, 109
|-
 ! 15
 | C<sub>2</sub>×C<sub>4</sub> || 8 || 4 || 2, 14
 ! 47
 | C<sub>46</sub> || 46 || 46 || 5
 ! 79
 | C<sub>78</sub> || 78 || 78 || 3
 ! 111
 | C<sub>2</sub>×C<sub>36</sub> || 72 || 36 || 2, 110
|-
 ! 16
 | C<sub>2</sub>×C<sub>4</sub> || 8 || 4 || 3, 15
 ! 48
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>4</sub> || 16 || 4 || 5, 7, 47
 ! 80
 | C<sub>2</sub>×C<sub>4</sub>×C<sub>4</sub> || 32 || 4 || 3, 7, 79
 ! 112
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>12</sub> || 48 || 12 || 3, 5, 111
|-
 ! 17
 | C<sub>16</sub> || 16 || 16 || 3
 ! 49
 | C<sub>42</sub> || 42 || 42 || 3
 ! 81
 | C<sub>54</sub> || 54 || 54 || 2
 ! 113
 | C<sub>112</sub> || 112 || 112 || 3
|-
 ! 18
 | C<sub>6</sub> || 6 || 6 || 5
 ! 50
 | C<sub>20</sub> || 20 || 20 || 3
 ! 82
 | C<sub>40</sub> || 40 || 40 || 7
 ! 114
 | C<sub>2</sub>×C<sub>18</sub> || 36 || 18 || 5, 37
|-
 ! 19
 | C<sub>18</sub> || 18 || 18 || 2
 ! 51
 | C<sub>2</sub>×C<sub>16</sub> || 32 || 16 || 5, 50
 ! 83
 | C<sub>82</sub> || 82 || 82 || 2
 ! 115
 | C<sub>2</sub>×C<sub>44</sub> || 88 || 44 || 2, 114
|-
 ! 20
 | C<sub>2</sub>×C<sub>4</sub> || 8 || 4 || 3, 19
 ! 52
 | C<sub>2</sub>×C<sub>12</sub> || 24 || 12 || 7, 51
 ! 84
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>6</sub> || 24 || 6 || 5, 11, 13
 ! 116
 | C<sub>2</sub>×C<sub>28</sub> || 56 || 28 || 3, 115
|-
 ! 21
 | C<sub>2</sub>×C<sub>6</sub> || 12 || 6 || 2, 20
 ! 53
 | C<sub>52</sub> || 52 || 52 || 2
 ! 85
 | C<sub>4</sub>×C<sub>16</sub> || 64 || 16 || 2, 3
 ! 117
 | C<sub>6</sub>×C<sub>12</sub> || 72 || 12 || 2, 17
|-
 ! 22
 | C<sub>10</sub> || 10 || 10 || 7
 ! 54
 | C<sub>18</sub> || 18 || 18 || 5
 ! 86
 | C<sub>42</sub> || 42 || 42 || 3
 ! 118
 | C<sub>58</sub> || 58 || 58 || 11
|-
 ! 23
 | C<sub>22</sub> || 22 || 22 || 5
 ! 55
 | C<sub>2</sub>×C<sub>20</sub> || 40 || 20 || 2, 21
 ! 87
 | C<sub>2</sub>×C<sub>28</sub> || 56 || 28 || 2, 86
 ! 119
 | C<sub>2</sub>×C<sub>48</sub> || 96 || 48 || 3, 118
|-
 ! 24
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>2</sub> || 8 || 2 || 5, 7, 13
 ! 56
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>6</sub> || 24 || 6 || 3, 13, 29
 ! 88
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>10</sub> || 40 || 10 || 3, 5, 7
 ! 120
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>2</sub>×C<sub>4</sub> || 32 || 4 || 7, 11, 19, 29
|-
 ! 25
 | C<sub>20</sub> || 20 || 20 || 2
 ! 57
 | C<sub>2</sub>×C<sub>18</sub> || 36 || 18 || 2, 20
 ! 89
 | C<sub>88</sub> || 88 || 88 || 3
 ! 121
 | C<sub>110</sub> || 110 || 110 || 2
|-
 ! 26
 | C<sub>12</sub> || 12 || 12 || 7
 ! 58
 | C<sub>28</sub> || 28 || 28 || 3
 ! 90
 | C<sub>2</sub>×C<sub>12</sub> || 24 || 12 || 7, 11
 ! 122
 | C<sub>60</sub> || 60 || 60 || 7
|-
 ! 27
 | C<sub>18</sub> || 18 || 18 || 2
 ! 59
 | C<sub>58</sub> || 58 || 58 || 2
 ! 91
 | C<sub>6</sub>×C<sub>12</sub> || 72 || 12 || 2, 3
 ! 123
 | C<sub>2</sub>×C<sub>40</sub> || 80 || 40 || 7, 83
|-
 ! 28
 | C<sub>2</sub>×C<sub>6</sub> || 12 || 6 || 3, 13
 ! 60
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>4</sub>  || 16 || 4 || 7, 11, 19
 ! 92
 | C<sub>2</sub>×C<sub>22</sub> || 44 || 22 || 3, 91
 ! 124
 | C<sub>2</sub>×C<sub>30</sub> || 60 || 30 || 3, 61
|-
 ! 29
 | C<sub>28</sub> || 28 || 28 || 2
 ! 61
 | C<sub>60</sub> || 60 || 60 || 2
 ! 93
 | C<sub>2</sub>×C<sub>30</sub> || 60 || 30 || 11, 61
 ! 125
 | C<sub>100</sub> || 100 || 100 || 2
|-
 ! 30
 | C<sub>2</sub>×C<sub>4</sub>  || 8 || 4 || 7, 11
 ! 62
 | C<sub>30</sub> || 30 || 30 || 3
 ! 94
 | C<sub>46</sub> || 46 || 46 || 5
 ! 126
 | C<sub>6</sub>×C<sub>6</sub> || 36 || 6 || 5, 13
|-
 ! 31
 | C<sub>30</sub> || 30 || 30 || 3
 ! 63
 | C<sub>6</sub>×C<sub>6</sub> || 36 || 6 || 2, 5
 ! 95
 | C<sub>2</sub>×C<sub>36</sub> || 72 || 36 || 2, 94
 ! 127
 | C<sub>126</sub> || 126 || 126 || 3
|-
 ! 32
 | C<sub>2</sub>×C<sub>8</sub>  || 16 || 8 || 3, 31
 ! 64
 | C<sub>2</sub>×C<sub>16</sub> || 32 || 16 || 3, 63
 ! 96
 | C<sub>2</sub>×C<sub>2</sub>×C<sub>8</sub> || 32 || 8 || 5, 17, 31
 ! 128
 | C<sub>2</sub>×C<sub>32</sub> || 64 || 32 || 3, 127
|}
</div>

==See also==

* [[Lenstra elliptic curve factorization]]

==Notes==

{{reflist}}

==References==

The ''[[Disquisitiones Arithmeticae]]'' has been translated from Gauss's [[Classical Latin|Ciceronian Latin]] into [[English language|English]] and [[German language|German]]. The German edition includes all of his papers on number theory: all the proofs of [[quadratic reciprocity]], the determination of the sign of the [[Gauss sum]], the investigations into [[biquadratic reciprocity]], and unpublished notes.

*{{citation
  | last = Gauss  | first = Carl Friedrich
  | author-link = Carl Friedrich Gauss
  | translator-last = Clarke | translator-first = Arthur A.
  | title = Disquisitiones Arithmeticae (English translation, Second, corrected edition)
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | year = 1986
  | isbn = 978-0-387-96254-2}}
*{{citation
  | last = Gauss  | first = Carl Friedrich
  | translator-last = Maser | translator-first = H.
  | title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (German translation, Second edition)
  | publisher = Chelsea
  | location = New York
  | year = 1965
  | isbn = 978-0-8284-0191-3}}
*{{citation
  | last1 = Riesel  | first1 = Hans| author-link = Hans Riesel
  | title = Prime Numbers and Computer Methods for Factorization (second edition)
  | publisher = Birkhäuser
  | location = Boston
  | year = 1994
  | isbn = 978-0-8176-3743-9}}
*{{citation
  | last = Vinogradov | first = I. M. | author-link = Ivan Matveyevich Vinogradov
  | title = Elements of Number Theory
  | publisher = Dover Publications
  | location = Mineola, NY
  | year = 2003
  | isbn = 978-0-486-49530-9
  | chapter = § VI Primitive roots and indices
  | pages = 105–121
  | chapter-url = https://books.google.com/books?id=xlIfdGPM9t4C&pg=PA105}}

==External links==
*{{MathWorld |title=Modulo Multiplication Group |id=ModuloMultiplicationGroup}}
*{{MathWorld |title=Primitive Root |id=PrimitiveRoot}}
*[http://hobbes.la.asu.edu/groups/groups.html Web-based tool to interactively compute group tables] by John Jones
*{{OEIS el|A033948|Numbers that have a primitive root (the multiplicative group modulo n is cyclic)}}
* Numbers n such that the multiplicative group modulo n is the direct product of k cyclic groups:
** k = 2 {{OEIS el|A272592|2 cyclic groups}}
** k = 3 {{OEIS el|A272593|3 cyclic groups}}
** k = 4 {{OEIS el|A272594|4 cyclic groups}}
*{{OEIS el|A272590|The smallest number m such that the multiplicative group modulo m is the direct product of n cyclic groups}} 

[[Category:Finite groups]]
[[Category:Modular arithmetic]]
[[Category:Multiplication]]