Talk:Multiplicative group of integers modulo n/Archive 1

Archive 1

Examples

This article lacks some simple examples — Preceding unsigned comment added by 89.1.125.149 (talk) 23:42, 5 April 2007 (UTC)

I have added some examples to the article. Gandalf61 19:57, 6 April 2007 (UTC)

You can't use the ring homomorphism from the integers to the integers mod n to show that the multiplication in the latter system is associative and commutative: the existence of a ring homomorphism assumes that the integers mod n is a ring which assumes associativity of multiplication. The argument still works, you just have to call the mapping something other than a ring homomorphism. Oronyatekha (talk) 18:54, 26 October 2008 (UTC)

It now assumes the homomorphism and shows that the coprime classes are closed under multiplication and how to find inverses. Virginia-American (talk) 14:30, 22 November 2008 (UTC)

Good for inverses, commutativity is trivial too, but associativity still needs to be shown. (By the way, I spent some time looking for a proof of the associativity and couldn't find any. It is not so simple as it seems.) Jsedenka (talk) 16:29, 3 January 2009 (UTC)

As the article says, associativity of multiplication in the multiplicative group of integers modulo n is inherited from associativity of "ordinary" integer multiplication. Basically, you show that:

$(a\otimes b)\otimes c=((a\times b)\times c))\mod n=(a\times (b\times c))\mod n=a\otimes (b\otimes c)$

where $\otimes$ is multiplication modulo n. Gandalf61 (talk) 18:04, 3 January 2009 (UTC)

In section entitled Structure, under Powers of 2

... Modulo 16 there are eight relatively prime classes 1, 3, 5, 7, 9, 11, 13 and 15. $\{\pm 1,\pm 7\}\cong C_{2}\times C_{2},$ is the 2-torsion subgroup (ie. the square of each element is 1), so $(\mathbb {Z} /16\mathbb {Z} )^{\times }$ is not cyclic. The powers of 3, {1,3,9,11} are a subgroup of order 4, as are the powers of 5, {1,5,9,13}. Thus ...

That way of explaining it left me with a question: What happened to relatively prime class 15? —Preceding unsigned comment added by ExcellentCompression (talk • contribs) 19:10, 30 March 2009 (UTC)

The table shows that $(\mathbb {Z} /16\mathbb {Z} )^{\times }$ is generated by −1 ≡ 15 and 3. The powers of 3 are the subgroup $\{1,3,9,11\};\$ each of these times 15 ≡ −1 is the set $\{-1,-3,-9,-11\}\equiv \{15,13,7,5\}\$ which accounts for the rest of the group. I'm not sure that answers your question or not. Virginia-American (talk) 21:06, 30 March 2009 (UTC)

General composite number

I removed the section "General composite numbers" because I believe it is not correct. According the Wolfram Math reference the general structure is more complex than this. It even does not match the structures in the table, for example for the number 35. — Preceding unsigned comment added by 91.127.93.3 (talk) 22:47, 22 July 2011 (UTC)

That section looks correct to me, so I have restored it. What exactly do you think is wrong with it ? For 35 we have

$(\mathbb {Z} /35\mathbb {Z} )^{\times }\cong (\mathbb {Z} /5\mathbb {Z} )^{\times }\times (\mathbb {Z} /7\mathbb {Z} )^{\times }\cong C_{4}\times C_{6}\cong C_{4}\times C_{2}\times C_{3}\cong C_{2}\times C_{12}$

which agrees with the entry in the table. Gandalf61 (talk) 13:51, 23 July 2011 (UTC)

I did not realize that $C_{4}\times C_{6}\cong C_{2}\times C_{12}$. Sorry for the inconvinience. — Preceding unsigned comment added by 91.127.93.3 (talk) 20:51, 24 July 2011 (UTC)

Section Generators: inconsistency?

The recent edit and its revert of section Generators should be looked at a little more closely, I think. Note that φ(n) = λ(n) when n = 1, so at the very least, this statement must be qualified to exclude 1 if it is in fact to be excluded. Also to say Z₁^× has no members is not too obviously true; it would seem to me that it should be the multiplicative group of the trivial ring, and thus has one member (0 is invertible in this ring). The next paragraph then lists Z_n^× for n = 1 explicitly as a cyclic group. So, from a strict mathematical perspective, is it or isn't it? What is clear is that the section as it now stands is inconsistent. — Quondum^☏✎ 21:59, 11 February 2012 (UTC)

I thought I'd just add that explicit mention of the case n = 1 in the section may be merited, if someone has a solid basis to work from. I note that the table in the next section does not list the case n = 1, So this remains a minor (implied only) inconsistency between the sections. That (ℤ/1ℤ)^× = ({0},×) ≝ the trivial group ≝ C₁ can be confusing, as with many trivial cases. — Quondum^☏✎ 06:59, 12 February 2012 (UTC)

I agree there is an inconsistency and it needs to be resolved. If the multiplicative group of integers modulo 1 existed, then it would have no members, since all integers are multiples of 1. But a group must have at least one member (it must have an identity element). Therefore the the multiplicative group of integers modulo 1 does not exist. The Mathworld page confirms that the multiplicative group is cyclic if and only if n is 2, 4, a power of an odd prime or twice a power of an odd prime. I have edited the article to make it consistent. Gandalf61 (talk) 08:47, 12 February 2012 (UTC)

"All integers are multiples of 1". All integers are also relatively prime to 1. We don't form the group by eliminating the multiples of n, we form the group from the residue classes that are relatively prime to n. Virginia-American (talk) 13:39, 12 February 2012 (UTC)

As Gandalf61 says, Z₁ will have one equivalence class, {0}, and so the collection of nonzero classes Z₁^× is empty. A group certainly has to be nonempty so the n=1 case is nonexistent. Rschwieb (talk) 15:20, 12 February 2012 (UTC)

I can see there may be some disagreement about (ℤ/1ℤ)^×. I nevertheless conclude at this point that simply excluding this case from consideration (as has now been done) is appropriate in this article. — Quondum^☏✎ 18:14, 12 February 2012 (UTC)

Modulo 1 there is one residue class. It contains all the integers. Every integer, including 0, is relatively prime to 1. The group is not the collection of nonzero classes, it is the collection of invertable classes, i.e. those relatively prime to the modulus, 1 in this case.

Another consideration is the order of the group. The article states that it is φ(n). φ(1) = 1. φ(n) is often defined as "the number of positive integers less than n and relatively prime to n". This is not strictly correct; it actually is "the number of positive integers not exceeding n and relatively prime to n". The two formulations are the same except when n = 1, because gcd(n, n) = |n|. 1 is the only positive integer coprime to itself. Virginia-American (talk) 19:31, 12 February 2012 (UTC)

I agree exactly with what you have said here (though some of the others may not). My approach is that the article is better making no statement about the case of n=1, and it does so by simply failing to consider it. To include it does nothing other than invite debate. Including it does not seem to enrich the field (unlike the trivial ring), even though the underlying detail is enlightening with regard to this trivial case. In any event, such material would require a source to have encyclopedic value. — Quondum^☏✎ 21:32, 12 February 2012 (UTC)

Whoa... I really don't want to get into an edit war over something that is basically not interesting. I challenge Gandalf61 or Rschwieb or anyone else to supply a referemce that supports the statement

If the multiplicative group of integers modulo 1 existed, then it would have no members, since all integers are multiples of 1. But a group must have at least one member (it must have an identity element). Therefore the the multiplicative group of integers modulo 1 does not exist.

The fact that Mathworld just lists 2,4, powers of odd.. and omits 1 is a simple oversight on their part, like it is in this article. If 1 were an exception I would expect mathworld to point this out. I doubt that I can find a reference that discusses the integers mod 1, but I also am quite sure there is no reference that states 1 is an exception to the general rule that the order of the group is given by φ(n), or that the group doesn't exist for n = 1. Virginia-American (talk) 23:26, 12 February 2012 (UTC)

You're right that I shouldn't have said "nonzero classes" before to describe the group. I hastily thought the group would have to be contained there since it is for n>1. This is because in all of those cases, the residue has multiplicative identity not equal to zero, and this identity is automatically in the multiplicative group. That is what happens when you allow the class of 0 (which is the same as the class of 1) to be a unit. Trying to include this case with the rest (n>1) is basically akin to people wanting to define fields so that the field with one element is a field. In short, the case n=1 is omitted for good reason: it does not contribute anything. It should definitely be excluded in the article. Rschwieb (talk) 00:37, 13 February 2012 (UTC)

I think that reason exists to omit n=1, but it relates purely to the fact that this is an encyclopedia and that we are not aware of any source whatsoever that deals with this evidently controvertial case. The field with one element serves as a cautionary example, though there are counterexamples such as the trivial ring that would support its inclusion. And while it would be interesting to debate this case here, until we can find some reference dealing with this case, I feel the article cannot make any statement about it, though doing so would make the article more complete. So if anyone wants to pursue this, finding a reference would be useful. — Quondum^☏✎ 06:38, 13 February 2012 (UTC)

I don't see what fields or rings with one element have to do with this. The article is about a group, and the trivial group is well-defined, if boring.

Probably the easiest thing is simply to make a new section, titled "1", immediately preceeding the "powers of 2" section. It would state something along thses lines:

Modulo 1, any two integers are congruent (cf. the definition from Ireland and Rosen: If a, b, m are integers, m ≠ 0, we say that a is congrunent to b mod m if m divides a−b.) (which is a rephrasing of the first sentence of the Disquisitiones Arithmeticae.) So there is only one congruence class mod 1. Also, for any integer n, positive, negative, or zero, gcd(n, 1) = 1. (1 divides n, 1 divides 1, and 1 is the largest number dividing 1.) So every number in this single congruence class is relatively prime to the modulus. Therefore, the multiplicative group of relatively prime classes is the trivial group with one element. And in fact, φ(1) = 1. For similar reasons, λ(1) = 1. The trivial group is cylic. (It has a single generator, the identity)

Because of this vacuous or trivial nature, modulus 1 is usually ignored. (e.g., the table in this article)

Virginia-American (talk) 13:18, 13 February 2012 (UTC)

This entire discussion is about a ring with one element: Z₁. Of course it is an additive and multiplicative group too. The whole point is that for n>1 Z_n is never a multiplicative group (with the operation inherited from Z), but for n=1 it is. The idea to mention the trivial case is fine, but the suggested paragraph has overblown detail. Something more like: "The case n=1 is exceptional and is usually treated separately, if at all. Z₁ has only has one element, the class of zero, which is necessarily invertible due to the small size of the set. This stands in contrast with every other case n>1, where the class of zero is not invertible. For this reason the behavior of φ and λ when n=1 does not fit nicely with all other cases. By inspection, φ(1) = 1 and λ(1) = 1." Rschwieb (talk) 14:20, 13 February 2012 (UTC)

I thought it fitted perfectly with the rule for φ and λ when n=1. My point at the start was that we would have to explain the omission precisely because it does fit the rule. So the only explanation for that is needed n=1 is to preempt misunderstanding of the logic (e.g. the need to point out that there is one invertible element, not zero). — Quondum^☏✎ 14:56, 13 February 2012 (UTC)

Oh, haha, I had thought the reason for the "inconsistency" title for this section was because that they disagreed. Then I would alter my recommendation to: "The case n=1 is exceptional and is usually treated separately, if at all. The case n=1 fits the pattern for φ and λ established for n>1: φ(1) = 1 and λ(1) = 1. The details for the n=1 case are slightly different since Z₁ has only has one element, the class of zero, which is necessarily invertible due to the small size of the set. This stands in contrast with every other case n>1, where the class of zero is not invertible." Rschwieb (talk) 16:01, 13 February 2012 (UTC)

Heh, no, it related to internal inconsistency of the mentioned section in this respect at the time that I started this section. Plus there were other mentions elsewhere that needed to be made consistent, but I thought they'd follow naturally. I think we probably could have a briefer mention that it fits the φ–λ pattern, and the invetibility is a bit obscure. But we seem to be headed somewhere on this. Unless others voice dissenting opinions. — Quondum^☏✎ 17:09, 13 February 2012 (UTC)

I put in a section for n = 1 and cleaned up (ignored) the case n = 1 elsewhere. Virginia-American (talk) 11:28, 14 February 2012 (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)