Nearly ten years ago, Donald Preece and I wrote the first draft of a set of notes on primitive lambda-roots. We could never decide what do do with them: they were too short for a monograph, too long (and expository) for a research paper. We discussed it but didn’t get around to doing anything with them apart from putting them on the web.
Now we can no longer discuss them, but I would like them to be read and used. So I have decided to put the current version (with some very minor changes, mainly bringing the references up to date) with my lecture notes.
Below is a slightly edited version of the preface of the notes.
The most important examples of finite commutative rings with identity are undoubtedly the rings Zn of integers mod n, for n∈N.
In the case where n is a prime number p, Zp is a field: its non-zero elements form a multiplicative group. This group is cyclic, of order n−1, and its generators are the primitive roots mod p.
If n is not prime, then Zn is not a field: an element x is invertible if and only if it is coprime to n, that is, gcd(n,x) = 1. The invertible elements of Zn form a group U(n), the group of units mod n; its order is φ(n), where φ is Euler’s phi-function.
If this group is cyclic, its generators are again called primitive roots. However, this is a rare event: it occurs only if n is an odd prime power, or twice an odd prime power, or 4.
To replace this, Carmichael introduced his lambda-function λ(n), the exponent of U(n), that is, the smallest number m such that every unit x satisfies xm = 1. A primitive lambda-root (or PLR) is a unit whose order is λ(n). Clearly, primitive lambda-roots exist for all n. They are the object of our study.
The role of finite fields in combinatorial constructions is well known. Our motivation is the fact that, with some ingenuity, the methods can be extended to Zn in some cases, with PLRs playing the role of primitive roots. The first chapter gives a couple of examples, the construction of terraces and difference sets.
Three other features of the text should be noted.
- Our aim is expository; we begin with an account of the algebra we need, and end with a short discussion of the role of the lambda-function in the RSA cryptosystem.
- We pose many open problems along the way. We hope that other researchers will find something to their taste here, as Thomas Müller and Jan-Christoph Schlage-Puchta have already done in one case.
- We have implemented many of our calculations in GAP, and a file of documented GAP code accompanies the notes, to make further exploration easy.
The notes are here. I haven’t found a way yet of publishing the GAP code in a satisfactory format; you can extract it from the notes if you are in a hurry.