Talk:Multiplicative group of integers modulo n

Section Table: 5 should be a generator for n=14?

[5]¹ = [5]

[5]² = [5][5] = [11]

[5]³ = [5][11] = [13]

[5]⁴ = [5][13] = [9]

[5]⁵ = [5][9] = [3]

[5]⁶ = [5][3] = [1]

[5]⁷ = [5][1] = [5]

And so on. 123.243.217.67 (talk) 04:04, 22 April 2012 (UTC)

Yes, 5 is a generator of the group for n=14, which is isomorphic to C6, so it has two generators: 3 and 5. However, I think the table is only aiming to show one example set of generators, not all possibilities - all the other Cn entries only show one generator also. Gandalf61 (talk) 16:13, 22 April 2012 (UTC)

In relation to the subject, the paragraph "Generators" does not clarify that there are usually more than one primitive roots in a cyclic group (for instance the group Z/7Z has as primitive roots both "3" and "5". Does anyone else thinks that this should explicitly be metnioned? For instance, the phrase "The single generator in the cyclic case is called a primitive root modulo n." could be changed as "Every single generator in the cyclic case is called a primitive root modulo n". Does anyone else thinks so too? 2A02:587:4526:EA00:A99A:EB35:54D2:8BC8 (talk) 05:12, 18 August 2017 (UTC)

group of false witnesses section

A better name imo would be "subgroup of false positives", but wikipedians shouldn't make these namings(although maybe we did at Mersenne number and inadvertently at Sphenic number). But maybe i'll get lucky and number theorists will start saying "group of false positives", and we could then change the section title.Rich (talk) 23:40, 5 November 2012 (UTC)

I don’t think the section belongs here at all. The groups $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ have many subgroups, in fact every finite abelian group can be realized as such a subgroup, and the group of “false witnesses” does not seem to be particularly special. Many other notions of a pseudoprime also give rise to various subgroups of $(\mathbb {Z} /n\mathbb {Z} )^{\times }$. The group of “false witnesses” doesn’t tell much about the structure of $(\mathbb {Z} /n\mathbb {Z} )^{\times }$, rather it tells something about Fermat pseudoprimes, so if anything it would be relevant for the Fermat pseudoprime article, not here. This is especially striking in view of the context of the article (cf. WP:UNDUE)—this material on a rather marginal topic occupies almost a half of the “Structure” section which otherwise gives essential information on the description of $(\mathbb {Z} /n\mathbb {Z} )^{\times }$. Added to that is the lack of references.—Emil J. 14:31, 9 November 2012 (UTC)

Group structure sections usually discuss subgroups.-Rich Peterson216.86.177.36 (talk) 00:47, 11 November 2012 (UTC)

My response above sounds sarcastic, which is what I meant to avoid, sorry. I actually tried phrasing the above several ways to try to avoid a sarcastic note. It does seem to me, though, that subgroups, especially those with number theoretic connections, should be discussed, or at least made note of, in this section. It does seem it is taking a large share of the section, but as we gradually add other facts to it, it will balance out. Any article that isn't complete might have unbalanced sections. For example, should we add to the structure section a discussion of the quadratic residues? Best wishes, Rich Peterson198.189.194.129 (talk) 23:08, 13 November 2012 (UTC)

structure and properties sections have a lot of overlap

198.189.194.129 (talk) 19:49, 16 November 2012 (UTC)

To clarify, i don't think ther's not so much that there is repetition, but I'm not sure why a given fact is in the structure section instead of the properties section or vice versa.198.189.194.129 (talk) 20:58, 16 November 2012 (UTC)

Inconsistent lead?

Stirred up by a recent edit + revert, I excerpt from the lead:

1. ... the set of integers in $\{0,1,\dots ,n-1\}$ ... form a group under multiplication ...
2. ... the elements ... can be thought of as ... residues modulo n
3. ... it is ... the group of units of the ring of integers modulo n.
4. This group ... $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ ... is ... finite ... order is ... $\varphi (n).$

Taking n as prime, (1) and (2) talk about n objects, whereas (3) and (4) talk about (n - 1) objects, at least to my understanding. Does this need correction, or am I misconstruing something? Purgy (talk) 12:25, 1 June 2018 (UTC)

Putting due emphasis on the skipped apposition "coprime to n" renders my remark as misconstruing. Nevertheless, I take my sloppiness and the IP's idea as a nudge to think about a possible preemphasis for this special 0. Purgy (talk) 18:33, 2 June 2018 (UTC)

Thanks. The zero may indeed be a bit misleading, since it's only needed for the stupid case n=1 where 0 is coprime to n. I'd be fine with assuming n>1 in the article if anyone prefers, but I believe the current wording makes it clear we're looking at (a subset of) all possible residues. Tokenzero (talk) 17:48, 5 June 2018 (UTC)

I agree. With or without the zero, it is mathematically correct, since zero is not coprime to n, but since this article is about "the multiplicative group of integers modulo n," I believe the zero should be included in the set $\{0,1,\dots ,n-1\}$ of n integers from which the group is extracted.—Anita5192 (talk) 18:27, 5 June 2018 (UTC)

I agree that the current wording is confusing. Before coming here I was indeed confused as to why the 0 was there. I am not familiar enough with the topic to do it myself, but maybe at least a footnote remembering that the 0 is only needed for the n=1 case would be useful here? Luca (talk) 18:26, 20 March 2019 (UTC)

The set $\{0,1,\dots ,n-1\}$ is the traditional way of representing the integers modulo n because this is the set of all remainders when integers are divided by n. Since this is the set from which the multiplicative group of integers modulo n is formed, the 0 is necessary.—Anita5192 (talk) 19:02, 20 March 2019 (UTC)

Decomposition does not match direct product

In the huge table, why exactly is $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ decomposed as C₂×C₂×C₁₂ for n = 112? According to what is written in the article, since 112 is 16·7, the part with 16 turns into C₂×C₄, and the part with 7 becomes C₆. Same goes about n = 105 = 3·5·7: the direct product gives us C₂×C₄×C₆ again, but the table says C₂×C₂×C₁₂. For n = 99 = 3²·11, the most natural form is C₆×C₁₀; so why C₂×C₃₀? Of course, considering decomposition for coprime numbers, we can see that C₆×C₁₀ ≅ C₂×C₃×C₁₀ ≅ C₂×C₃₀ and C₄×C₆ ≅ C₄×C₃×C₂ ≅ C₁₂×C₂, but what makes us try to extract С₂ as a separate factor? Ambidexter (talk) 23:38, 16 April 2020 (UTC)

It seems the choice was to take the lexicographically smallest sequence of possible group orders, among those of shortest length. This way isomorphic groups look identical. Tokenzero (talk) 15:56, 17 April 2020 (UTC)

Makes sense. So, for n = 2⁴·3²·11, we get C₂×C₄×C₆×C₁₀, but after that we ought to decompose it to C₂×C₄×C₂×C₃×C₂×C₅ and find a way to recombine coprime orders so that we get a better set of four cyclic groups? As far as I understand, we take 3, 4 and 5 (all of them being pairwise coprime) and end up with C₂×C₂×C₂×C₆₀. Shouldn't this algorithm be somehow mentioned in the article? Currently the transition from theory (direct product, powers of 2…) to examples is kind of abrupt. Ambidexter (talk) 19:53, 17 April 2020 (UTC)

OK, I tried to rephrase the table's description, feel free to improve it. Probably not worth describing a concrete algorithm in detail (but in short, one can say prime powers are pushed as far right as possible; formally, first decompose into prime powers: C₂×C₄×C₂×C₃×C₂×C₅, then for each prime sort it's powers: C₂×C₂×C₂×C₄, C₃, C₅, and then merge them starting from the end of each sorted list). Tokenzero (talk) 14:32, 18 April 2020 (UTC)