From: Alexander Vardy <vardy(AT)montblanc.ucsd.edu>
Date: Fri, 5 Apr 2002 15:02:58 -0800 (PST)
Comments on and program for A069098.


A recent conversation re-kindled my interest in a very old
sequence of mine (now A069098).

 Let  Z_q  be the ring of integers modulo  q . A minimal annihilator 
polynomial over  Z_q  is a monic polynomial  M_q(x)  of the least 
possible degree, such that 
 
M_q(alpha) = 0  in Z_q for all  alpha in Z_q
   
When  q  is prime, it is trivial to show that  deg M_q(x) = q 
and the polynomial  M_q(x) = x^q - x  is the unique minimal annihilator.
In general, it is not too difficult to prove that  deg M_q(x) = chi(q) 
where  chi(q)  is the smallest integer such that  chi(q)!  
is divisible by  q  (try this!). The function  chi(q)  is known
as the Smarandache function. What is more interesting is the exact 
number of distinct minimal annihilators over  Z_q  for a general  q .

The exhaustive search program
I wrote ~10 years ago is quite inefficient. A better program is likely
to produce a few more terms ( q = 22  is a stumbling point because 
 chi(22) = 11 , the highest value of  chi(q)  for  q < 22  is 7).
What happens beyond that is an interesting open problem.

Alex

/**************************************************************************
*                                                                         *
* annihilators.c: produces all the minimal annihilators by exhaustive     *
*                 search                                                  *
*                                                                         *
* Written by: Alexander Vardy                                             *
*             IBM Almaden Research Center, K65/802                        *
*	      650 Harry Rd., San Jose, CA 95120                           *
*	      Tel: (408)927-2232                                          *
*	      e-mail: vardy(AT)almaden.ibm.com                               *
*                                                                         *
*      Date: January 8, 1993.                                             *
*                                                                         *
*                                                                         *
***************************************************************************/



/**************************************************************************
*                                                                         *
*                            INCLUDES                                     *
*                                                                         *
**************************************************************************/


#include <stdio.h>
#include <stdlib.h>

/**************************************************************************
*                                                                         *
*                            DEFINES                                      *
*                                                                         *
**************************************************************************/

#define q      6
#define chi    3



/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*
*                                                                         *
*                                 MAIN                                    *
*                                                                         *
*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/

void main()
{

/*--------------------------INTERNAL VARIABLES---------------------------*/

int g[chi+1]; 

int alpha;

int power_alpha,g_alpha;

int N;

int i,j;



/*------ Find all the minimal annihilators by exhaustive serach --------*/

     N = 0;
     fprintf(stdout,"** Minimal annihilators found for q = %d:
", q);

     for ( j = 0; j <= chi; j++ ) g[j] = 0;
     g[chi] = 1;
     
     do
     {
          /* generate g(x) */

        next_g:
        for ( i = 1; i <= chi; i++ ) 
        {
           if ( g[i] < (q-1) ) 
           { 
              (g[i])++;
              for ( j = 1; j < i; j++ ) g[j] = 0;
              break;
           }
        }
        if ( i >= chi ) goto exit_loop;


         /* check if g(x) is an annihilator */

        for ( alpha = 1; alpha < q; alpha++ ) 
        {
          g_alpha = 0;
          for ( i = 1, power_alpha = 1; i <= chi; i++ ) 
          {
            power_alpha = (alpha*power_alpha) % q;
            g_alpha += (g[i]*power_alpha) % q;
          }
        
          if ( (g_alpha % q) != 0 )  goto next_g;
      
        }


         /* print out the new annihilator */

        N++;
        for ( j = 0; j <= chi; j++ ) 
        fprintf(stdout,"%6d ", g[j]);
        fprintf(stdout,"
");

     }
     while (0 == 0);
     exit_loop:;


     fprintf(stdout,"** Total number of minimal annihilators found: %d
",N);



} /* end MAIN */