On Sun, Apr 24, 2016 at 11:06 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
4 14 16 26
Note that that's isomorphic to the other one of the two abstract groups of order 4, the one that isn't a cyclic group.
Inspired by that, here's an absurdly bold conjecture with remarkably little evidence: *Every* finite abelian group is isomorphic to some multiplicative group mod N. Someone prove me wrong.
Your conjecture is not hard to prove, if you know the fundamental theorem of Abelian groups (every abelian group is the direct product of cyclic groups) and Dirichlet's theorem on primes in arithmetic progressions (if a and b are relatively prime, there are infinitely many primes of the form an + b). Let's say we're looking for the subsemigroups of Z/N* that are groups. Let the prime factorization of N be N = Prod_{i=1}^n p_i^{e_i}. Let's first solve this for n = 1, that is, for N a prime power. The only possible identity elements are 0 and 1, since those are the only solutions of X^2 = X mod p^n. The only possible group with identity 0 is the 1-element group, since if 0 is the multiplicative identity and a is in the group, a = a * 0 = 0. If the identity is 1, then any element of it must be relatively prime to p. The set of all p^n - p^{n-1} of these form a cyclic group. This has one subgroup for every divisor of its order. For the general case, The identity element has to be either 0 or 1 mod p_i^{e_i} for each i. So there are 2^N possible identity elements, one for each subset of {1, 2, ... n}. So let's fix a subset S of {1, 2, ... n}, call the complement of S in {1, 2, ... n} S', and let's find all the groups with an identity element that is 1 mod p_i^{n_i} for i in S, and 0 mod p_i^{n_i} for i in S'. Such a group is still a group mod p_i^{n_i} for i in S', which must be the 1-element group, so all its elements are multiples of p_i^{n_i}. So for the chosen identity element, we can divide all the group elements by Prod_{i in S'} p_i^n_i, and we are left with the multiplicative group of Z mod M, where M = Prod_{i in S} p_i^{e_i}, which is the product of the cyclic groups of order phi(p_i^{e_i}) for i in S. The original problem asked us to count these groups. While there is a formula, it's fairly involved; see for example http://math.ubbcluj.ro/~calu/nrsubgroup.pdf But the new question of whether every abelian group arises in this way is much easier. If we want to find the cyclic group of order M, we need to find a prime power p^n such that M divides phi(p^n). But this is easy, by Dirichlet's theorem. We can even require n = 1. We're then looking for a prime p such that M divides p-1, that is p must be of the form k * M +1. There are infinitely many such primes, so we can find as many cyclic groups of any desired order as we like, Since any finite abelian group is the direct product of cyclic groups, we can obtain any abelian group in this way. Andy