Question 1

For n > 1 define the divisor length k of n to be the number of terms in the sequence
a₁ , a₂ , a₃ , ... , a_k
where a₁ is the number of divisors of n, a_i is the number of divisors of a_i-1 and a_k is the first entry in the sequence with value 2.
Write a GAP function p(n) which returns the divisor length of n.
Have GAP print a list of length 100 whose nth entry is the divisor length of n.
Write a program to find the smallest positive integer with divisor length 6 and find this integer.

Solution 1

Note that p(n) returns p(|n|) if n is negative and p(1) = 1.

p:=function(n) local l,count;
l:=Length(DivisorsInt(n));
count:=1;
while l>2 do
  count:=count+1;
  l:=Length(DivisorsInt(l));
od;
return count;
end;

List([1..100], x->p(x));

[ 1, 1, 1, 2, 1, 3, 1, 3, 2, 3, 1, 4, 1, 3, 3, 2, 1, 4, 1, 4, 3, 3, 1, 4, 2, 
  3, 3, 4, 1, 4, 1, 4, 3, 3, 3, 3, 1, 3, 3, 4, 1, 4, 1, 4, 4, 3, 1, 4, 2, 4, 
  3, 4, 1, 4, 3, 4, 3, 3, 1, 5, 1, 3, 4, 2, 3, 4, 1, 4, 3, 4, 1, 5, 1, 3, 4, 
  4, 3, 4, 1, 4, 2, 3, 1, 5, 3, 3, 3, 4, 1, 5, 3, 4, 3, 3, 3, 5, 1, 4, 4, 3 ]

Now find the first number with divisor length 6.

i:=1;
while p(i)<6 do
  i:=i+1;
od;
i;

5040

Question 2

Show that the dihedral group of order 24 has a subgroup of order k for every k dividing 24.

Let G be a group of order n which does not have a subgroup of order k for every k dividing n.
Find all such groups of order less than 50.

[Hint: ConjugacyClassesSubgroups(G) will give a list of conjugacy classes of subgroups of G and Representative will allow the selection of one subgroup from each conjugacy class.]

Solution 2

G:=DihedralGroup(24);

<pc group of size 24 with 4 generators>

lis:=ConjugacyClassesSubgroups(G);
l:=List(lis,Representative);

[ Group( <identity> of ... )^G, Group( [ f1*f2 ] )^G, Group( [ f3*f4 ] )^G, 
  Group( [ f1 ] )^G, Group( [ f4 ] )^G, Group( [ f1, f3*f4 ] )^G, 
  Group( [ f1*f2, f3*f4 ] )^G, Group( [ f2*f4^2, f3*f4 ] )^G, 
  Group( [ f4, f3 ] )^G, Group( [ f4, f1*f2 ] )^G, Group( [ f4, f1 ] )^G, 
  Group( [ f1, f2*f4^2, f3*f4 ] )^G, Group( [ f4, f3, f1 ] )^G, 
  Group( [ f4, f3, f1*f2 ] )^G, Group( [ f4, f3, f2 ] )^G, 
  Group( [ f4, f3, f1, f2 ] )^G ]

List(l,Size);

[ 1, 2, 2, 2, 3, 4, 4, 4, 6, 6, 6, 8, 12, 12, 12, 24 ]

DivisorsInt(24);

[ 1, 2, 3, 4, 6, 8, 12, 24 ]

Hence there is a subgroup of that order for each divisor.

For the next part we first loop over group orders up to 50
and then loop over the number of groups of that order.

nfac is the number of distinct divisors of the group order
lis is a list of representatives, one for each conjugacy class of subgroups
nsub is the number of distinct orders of subgroups

for gporder in [2..50] do
 for i in [1.. NumberSmallGroups(gporder)] do
   G:=SmallGroup(gporder,i);
   nfac:=Length(DivisorsInt(gporder));
   lis:=List(ConjugacyClassesSubgroups(G), Representative);
   nsub:=Length(Set(List(lis,Size)));
   if nfac <> nsub then Print("Order ", gporder," group number ",i,"\n"); fi;
 od;
od;

Order 12 group number 3
Order 24 group number 3
Order 36 group number 3
Order 36 group number 9
Order 36 group number 11
Order 48 group number 3
Order 48 group number 50

Question 3

Write a GAP function to check whether a number n is congruent to 1 mod 4. Write a function which, given a prime p, returns a square root of -1 mod p (that is a number whose square is congruent to -1 mod p) if such a number exists and returns "fail" otherwise.
Create a list P of all prime numbers less than 100 which are congruent to 1 mod 4.
Use your two functions to check that for every prime p in P there is a square root of -1 mod p.

Let SL(2, p) be the group of 2 2 matrices of determinant 1 with entries in GF(p). Let x and y be the following two elements of SL(2, p)

where n is some element of GF(p) and z is a square root of -1 mod p.
Find those primes p in P for which there is an n in GF(p) such that both (i) and (ii) below hold.
    (i)    x does not have order 10;
   (ii)    x y xⁱ y²ⁱ xⁱ y = 1 for some i < 20.

Solution 3

We define the square root of -1 mod p

sqroot:= function(p) local n;
for n in [2..p-1] do
  if (n^2 +1) mod p = 0 then return n;
break;
  fi;
od;
return fail;
end;

function( p ) ... end

The next function returns true if the number is of the form 4m+1

is1mod4:=function(n);
 if n mod 4 = 1 then
  return true;
 else
  return false;
 fi;
end;

function( n ) ... end

We construct a list of primes less than 100 congruent to 1 mod 4

P:=Filtered(Primes,i-> (i < 100) and is1mod4(i));

[ 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97 ]

Now construct and test matrices x and y

for p in P do;
id:= Identity(Z(p));
z:=sqroot(p);
for n in [2..p-2] do
 x:=id*[[0,-1],[1,n]];
  if Order(x) = 10 then continue; fi;
 y:= id*[[z,-1],[-n*z,n-z]];
   for j in [1..50] do
    if x*y*x^j*y^(2*j)*x^j=y^-1 then
      Print("Prime = ",p,", Power = ",j,", Entry n in x = ",n,"\n");
    fi;
   od;
 od;
od;

Prime = 29, Power = 6, Entry n in x = 4
Prime = 29, Power = 21, Entry n in x = 4
Prime = 29, Power = 36, Entry n in x = 4
Prime = 37, Power = 8, Entry n in x = 34
Prime = 37, Power = 27, Entry n in x = 34
Prime = 37, Power = 46, Entry n in x = 34
Prime = 61, Power = 14, Entry n in x = 39
Prime = 61, Power = 45, Entry n in x = 39