Yes, there was a fundamental theoretical error in my algorithm. I don't know if there's an *efficient* way to fix it, but I remain hopeful. Hopefully someone with a deeper knowledge of Number Theory, specifically of the *non-cyclic *multiplicative groups modulo *n*, will read this and advise.

Here's a theoretical description of my error. This requires no knowledge of Maple, or even programming, to understand; just knowledge of Number Theory.

**Definitions and Notations:**

All lowercase variables represent nonnegative integers. All lowercase variables other than *n* represent nonnegative integers less than *n*.

*Multiplicative group modulo n*: Let **Z**[*n*]* denote the multiplicative group modulo *n*, in other words, the set of positive integers less than *n *that are coprime with *n*. This is also called the __group of units modulo n__.

*Order*: The __order__ of *g *in **Z**[*n*]* is the smallest positive integer *e* such that *g^e *= 1 (mod *n*).

*Totient (Euler's totient)*: The __totient__ of *n *is the number of positive integers less than *n* and coprime with *n*. Thus, totient(*n*) = |**Z**[*n*]*|, and the order of any element is a divisor of the totient. When used as a prefix functional operator symbol, it is usually denoted by the lowercase Greek letter *phi*. The totient can be very easily calculated from the prime factorization of *n*.

*Carmichael's lambda function*: The *Carmichael function* of *n* is the largest order of any element of **Z**[*n*]*. It is also called the *reduced totient*. It is a divisor of the totient, and the order of any element is a divisor of it. Its prefix functional operator symbol is usually lowercase Greek *lambda*. It can also be easily calculated from the prime factorization of *n*.

*Primitive root*: An element of **Z**[*n*]* of order totient(*n*) is called a *primitive root* of *n*. Primitive roots only exist for some *n*. When they do exist, the number of them is totient(totient(*n*)).

**Cyclic vs Non-cyclic groups of units:**

The assumption that *n* is NOT of the form 1, 2, 4, *p^k*, 2**p^k* (where *p* is an odd prime) is equivalent to all of the following:

**Z**[*n*]* is not a cyclic group.
- Carmichael(
*n*) < totient(*n*).
- There does not exist an element in the group whose order is totient(
*n*).
- The group does not have a primitive root.

**The specific false assumptions that I made:**

Let *L* = Carmichael(*n*). Let *G* = { *g* in **Z**[*n*]* | order(*g*) =* L *}.

**Falsehood 1:** I had assumed that for every *x *in **Z**[*n*]* there existed *g *in *G *and integer *e* such that *g^e** *= *x *(mod *n*). In other words, I assumed that the powers of the elements of *G *"generated" the whole group (hence the symbol *G*).

However, that does seem to be true for __most__ *x*. When it's true, we have this proposition:

**Proposition:** order(*x*) = *L / *gcd(*e*, *L*).

The consequence of this false belief was that I was trying to use that process to find __all__ *x* of that order.

**Falsehood 2: **I had assumed that |*G| = *totient(totient(*n*)). Although this is certainly true if **Z**[*n*]* has a primitive root, in general |G| <> totient(totient(*n*)). For example, for *n* = 8, *G *= {3,5,7}, so |*G*| = 3, but totient(totient(*n*)) = 2.

The consequence of this false belief was that my algorithm may stop trying to find new elements of *G *too soon.

**Reduction of the size of ***G *for more efficient computation:

This process, which is already implemented in my algorithm, can be used to replace *G* with a much smaller subset *GR *that has identical computational power:

Define an equivalence relation **R*** *on *G* via *g* **R** *h* iff there exists an *e* such that *g^e = h *(mod *n*). Any such *e* is necessarily coprime with *L*, so the size of the equivalence classes is totient(*L*). Let *GR *be any system of representatives of the equivalence classes. So, the size of *GR *is |*G|*/totient(*L*). (If **Z**[*n*]* has primitive roots, then *GR *has a single element, which could be any of the primitive roots.)

The way that this is implemented in my algorithm is more efficient than the naive interpretation of the definition of ~~R~~ may imply: Immediately after any *g* in *G* is found, all members of its equivalence class are cached and removed from further consideration.

**Conjecture: **For all postive integers *n*,

totient(totient(*n*)) / totient(Carmichael(*n*)) = totient(*n*) / Carmichael(*n*).

This seems to be true even if |*G*| <> totient(totient(*n*)).

**Questions; Request for assistance:**

**1. Pseudo-primitive roots:**

So, how can I enlarge *GR* so that it can function akin to a "set of primitive roots"? In other words, how can it be made into some sort of "basis" or minimal set of generators which can generate all of **Z**[*n*]*? Would taking products of distinct elements of *GR *be sufficient enlargement? What if they were only *pairwise* products of distinct elements? Should I use pseudo-primitive roots of *n* (see ?NumberTheory, PseudoPrimitiveRoot)? A potential problem with that with respect to computational efficiency is that I'd like to avoid computing pseudo-primitive roots that are equivalent under relation ~~R~~ (defined in the previous section) to ones already computed.

**2. Counting elements of a given order:**

If I could count all the elements of a given order before they are generated, the speed of the algorithm could be greatly improved. I realize that there is no simple closed-form formula for this, but perhaps there is a recurrence relation (perhaps akin to partitions of an integer). Computationally, a recurrence would be just as good as a closed-form.