How many groups have 2019 elements? What are these groups?

2019 is a semiprime, i.e. the product of two primes, 3 and 673. For every semiprime *s*, there are either one or two distinct groups of order *s*.

As explained here, if *s* = *pq* with *p* > *q*, all groups of order *s* are isomorphic if *q* is not a factor of *p* − 1. If *q* does divide *p − *1 then there are exactly two non-isomorphic groups of order *s*, one abelian and one non-abelian. In our case, 3 does divide 672, so there are two groups of order 2019. The first is easy: the cyclic group of order 2019. The second is more complex.

You could take the **direct product** of the cyclic groups of order 3 and 673, but that turns out to be isomorphic to the cyclic group of order 2019. But if you take the **semidirect product** you get the other group of order 2019, the non-abelian one.

## Semidirect products

Starting with two groups *G* and *H*, the direct product *G* × *H* is the Cartesian product of *G* and *H* with multiplication defined componentwise. The semidirect product of *G* and *H*, written [1]

also starts with the Cartesian product of *G* and *H* but defines multiplication differently.

In our application, *G* will be the integers mod 673 with **addition** and *H* will be a three-element subgroup of the integers mod 673 with multiplication [2]. Let *H* be the set {1, 255, 417} with respect to multiplication [3]. Note that 1 is its own inverse and 255 and 417 are inverses of each other.

### Product

Now the group product of (*g*_{1}, *h*_{1}) and (*g*_{2}, *h*_{2}) is defined to be

(*g*_{1} + *h*_{1}^{−1}*g*_{2}, *h*_{1} *h*_{2})

So, for example, the product of (5, 255) and (334, 417) is (5 + 417*334, 255*417) which reduces to (645, 1) working mod 673.

(We haven’t defined the semidirect product in general, but the procedure above suffices to define the semidirect product for any two groups of prime order, and so it is sufficient to find all groups of semiprime order.)

Note that our group is non-abelian. For example, if we reverse the order of multiplication above we get (263, 1).

### Identity

The identity element is just the pair consisting of the identity elements from *G* and *H*. In our case, this is (0, 1) because 0 is the additive identity and 1 is the multiplicative identity.

### Inverse

The inverse of an element (*g*, *h*) is given by

(−*gh*, *h*^{−1}).

So, for example, the inverse of (600, 255) is (444, 417).

## Python code

The goal of this post is to be concrete rather than general.

So to make everything perfectly explicit, we’ll write a little Python code implementing the product and inverse.

def hinv(h): if h == 255: return 417 if h == 417: return 255 if h == 1: return 1 def prod(x, y): g1, h1 = x g2, h2 = y g3 = (g1 + hinv(h1)*g2) % 673 h3 = (h1*h2) % 673 return (g3, h3) def group_inv(x): g, h = x return ((-g*h)%673, hinv(h)) x = (5, 255) y = (334, 417) print(prod(x, y)) print(prod(y, x)) print(group_inv((600, 255)))

The following code verifies that our group satisfies the axioms of a group.

from itertools import product identity = (0, 1) h_list = [1, 255, 417] def elem(x): g, h = x g_ok = (0 <= g <= 672) h_ok = (h in h_list) return (g_ok and h_ok) group = product(range(673), h_list) assert(len([g for g in group]) == 2019) # closed under multiplication for x in group: for y in group: assert( elem(prod(x, y)) ) # multiplication is associative for x in group: for y in group: for z in group: xy_z = prod(prod(x, y),z) x_yz = prod(x, prod(y,z)) assert(xy_z == x_yz) # identity acts like it's supposed to for x in group: assert( prod(x, identity) == x ) assert( prod(identity, x) == x ) # every element has an inverse for x in group: ginv = group_inv(x) assert( elem(ginv) ) assert( prod(x, ginv) == identity ) assert( prod(ginv, x) == identity )

## Related posts

[1] The symbol for semidirect product is ⋊. It’s U+22CA in Unicode and `\rtimes`

in LaTeX.

[2] In general, the semidirect product depends on a choice of an action of the group *H* on the group *G*. Here the action is multiplication by an element of *H*. Different actions can result in different groups. Sometimes the particular choice of action is made explicit as a subscript on the ⋊ symbol.

[3] How did I find these numbers? There are 672 non-zero numbers mod 673, so I picked a number, it happened to be 5, and raised it to the powers 672/3 and 2*672/3.

Another way to look at this is that the multiplication in this group is just multiplication of matrices of the form

[1 0

g h^-1]

where all entries live in Z/673. (Is there any reason to use h^-1 instead of h in the construction?) If you construct this group as a subgroup of GL(2, Z/673) rather than from whole cloth, you only need to check that it is closed under matrix multiplication, and all the other properties follow automatically.