This is a reply to three people, so don't don't skip this unless you're skipping the whole topic. Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6} {-1, 1}, {-4, 4} {-3, -1, 1, 3}, {-4, -2, 2, 4} {-4, -3, -2, -1, 1, 2, 3, 4} ---------------------------- The last one is not a group. The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand. I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element. I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is. I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.) Then, for each identity element I, multiply it by all other numbers 2 through N. If I*J is not J, it's not the right identity element for J. Otherwise, keep multiplying J by itself until I either get I back (win) or I get 0 (fail). If I didn't fail, add the group to the list. At the end, eliminate duplicates and list them all. Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times. Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime. In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things. Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Mod N, the identity elements are those numbers I such that I^2 = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of identity elements mod N appear to be given by A034444. Mod 30, there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups: Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.