[GAP Forum] Idempotents modulo N

[Jean-Claude Arbaut]

Hello GAP users,

GAP can compute idempotents, like this :
a := Idempotents(MatrixAlgebra(Integers mod 3, 2));
List(a, x -> x*x - x);

For Integers mod n, it also works, but it's not very fast. However, it's a
fairly easy task, using chinese remainder theorem, and if n = p1^k1 * ... *
ps^ks, then there are 2^s solutions.
Here is a program to compute them, in case it can be useful.

IdempotentsMod := function(n)
   local a, m, s, r;
   m := List(Collected(FactorsInt(n)), v -> v[1]^v[2]);
   s := Length(m);
   a := [];
   for r in IteratorOfTuples([0, 1], s) do
      Add(a, ChineseRem(m, r));
   od;
   Sort(a);
   return List(a, x -> ZmodnZObj(x, n));
end;

For example :

n := 2000000;
Idempotents(Integers mod n);
IdempotentsMod(n) = last;

Length(IdempotentsMod(Factorial(50)));


Jean-Claude Arbaut