Talk:Multiplicative group of integers modulo n

Archives

This page has archives. Sections older than 365 days may be automatically archived by when more than 5 sections are present.

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)[reply]

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)[reply]

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)[reply]

structure and properties sections have a lot of overlap

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

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)[reply]

Inconsistent lead?

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

... the set of integers in $\{0,1,\dots ,n-1\}$ ... form a group under multiplication ...

... the elements ... can be thought of as ... residues modulo n

... it is ... the group of units of the ring of integers modulo n.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Definition of multiplicative group mod n

It says in the first line: 'from the set $\{0,1,\dots ,n-1\}$ of n non-negative integers', however, if n is not prime, then there may not be n non negative integers in the set. Isn't that a mistake? 129.72.239.92 (talk) 18:41, 18 November 2024 (UTC)[reply]

There will always be n non-negative integers in the set. However, they will not all be coprime to n. If n is prime, all but zero will be coprime to n; if n is composite, less than n – 1 integers in the set will be coprime to n.—Anita5192 (talk) 21:14, 18 November 2024 (UTC)[reply]