Covering sets for a^n-1

[carpetpool]

If p is prime, and a is an integer 1 < a < p, then a^(p-1) = 1 (mod p).

From this, a^(p-1)-1 divides p, and assuming p > 2, a^(p-1)-1 is a reducible polynomial. Therefore, let d_n denote all the possible divisors of p-1, in order. For at least one d_n, p must divide the d_nth cyclotomic polynomial evaluated at a. Furthermore, if a is a primitive root mod p, then p divides the p-1th cyclotomic polynomial evaluated at a. This implies the solutions to (here Phi(n,x) is the nth cyclotomic polynomial evaluated at x).

Phi(p-1, a) = 0 (mod p)

are precisely the primitive roots mod p.

If D_n are all the divisors of p-1 with D_n < p-1, that is all divisors of p-1 NOT including p-1, and p does not divide the D_nth cyclotomic polynomial at a, for all D_n then p MUST divide the p-1th cyclotomic polynomial at a.

Bottom line, factor a^(p-1)-1 into irreducible polynomials I, and one of these polynomials when evaluated at a will be a multiple of p, if a is not 0 (mod p).

To see this let's look at a few examples;

Take p = 5.

p-1 = 4 = 2^2, with divisors [1, 2, 4]

This implies, for any a, 5 divides either a-1, a+1, a^2+1, or a = 5m for some integer m (assume not).

a-1 = 0 (mod 5) for a = 1 (mod 5)
a+1 = 0 (mod 5) for a = 4 (mod 5)
a^2+1 = 0 (mod 5) for a = 2, 3 (mod 5)

Furthermore one can find a set of three polynomials (each defining the second, and fourth cyclotomic fields) with degrees 1, 1, and 2 which include all non-zero residues (mod 5) as solutions to one of the three polynomials:

a^4-1 = (a+1)(a-1)(a^2+1)

a+1 = 0 (mod 5) for a = 4 (mod 5)
a+4 = 0 (mod 5) for a = 1 (mod 5)
a^2+1 = 0 (mod 5) for a = 2, 3 (mod 5)

Hence, (a+1)(a+4)(a^2+1) = a^4 + 5*a^3 + 5*a^2 + 5*a + 4 = 0 (mod 5) if a is not 0 (mod 5).

The general "trick" to this (for any p) is given polynomials defining the D_nth cyclotomic fields, for D_n all divisors of p-1 not including p-1, one needs to find a polynomial P(x) defining the p-1th cyclotomic field with fixed solutions to

P(a) = 0 (mod p).

Let's take a look at p = 7.

a^6-1 = (a+1)(a-1)(a^2+a+1)(a^2-a+1)

a+1 = 0 (mod 7) for a = 6 (mod 7)
a-1 = 0 (mod 7) for a = 1 (mod 7)
a^2+a+1 = 0 (mod 7) for a = 2, 4 (mod 7)
a^2-a+1 = 0 (mod 7) for a = 3, 5 (mod 7)

which covers all non-zero residues (mod 7) as solutions to one of the four polynomials.

Using the same methods described earlier, we have

a+1 = 0 (mod 7) for a = 6 (mod 7)
a+4 = 0 (mod 7) for a = 3 (mod 7)

This leaves us to find two polynomials defining the third cyclotomic field, which have a = 1, 2, 4, 5 (mod 7) as solutions. Additionally, I found these two polynomials which have the remaining residues (mod 7) as solutions:

a+1 = 0 (mod 7) for a = 6 (mod 7)
a+4 = 0 (mod 7) for a = 3 (mod 7)
a^2+3 = 0 (mod 7) for a = 1, 5 (mod 7)
a^2+a+1 = 0 (mod 7) for a = 2, 4 (mod 7)

Hence (a+1)(a+4)(a^2+3)(a^2+a+1) = a^6+6*a^5+13*a^4+27*a^3+34*a^2+27*a+12 = 0 (mod 7) if a is not 0 (mod 7).

From this, I attempted to find a covering set for p = 13 given the following information:

a+1 = 0 (mod 13) for a = 12 (mod 13)
a+4 = 0 (mod 13) for a = 9 (mod 13)
a^2+1 = 0 (mod 13) for a = 5, 8 (mod 13)
a^2+3 = 0 (mod 13) for a = 6, 7 (mod 13)
a^2+a+1 = 0 (mod 13) for a = 3, 9 (mod 13)

So we would need a degree-4 polynomial P(a) (defining the 12th cyclotomic field) with fixed solutions:

P(a) = 0 (mod 13) if a = 1, 2, 4, 10, 11 (mod 13)

which is impossible given P(a) is of degree 4 and therefore only has 4 solutions.

So now what? I have still yet to answer this question:

Given the sequence s_(a,n) = a^n-1, and the condition that if n is prime, then s_(a,n-1) = 0 (mod n).

a_1 = a-1
a_2 = (a-1)*(a+1)
a_3 = (a-1)*(a^2+a+1)
a_4 = (a-1)*(a+1)*(a^2-1)
a_5 = (a-1)*(a^4+a^3+a^2+a+1)
a_6 = (a-1)*(a^2+a+1)*(a^2-a+1)
a_7 = (a-1)*(a^6+a^5+a^4+a^3+a^2+a+1)
a_8 = (a-1)*(a+1)*(a^2+1)*(a^4+1)
a_9 = (a-1)*(a^2+a+1)*(a^6+a^3+1)
a_10 = (a-1)*(a^4+a^3+a^2+a+1)*(a^4-a^3+a^2-a+1)
......

By replacing each of the irreducible polynomials I which appear in the factorization of a_n with a polynomial defining the same field as I, and define the new sequence S(a,n) is it possible to obtain the condition that if n is prime, then S(a,n-1) = 0 (mod n)?

That is, let e(O) be an element in terms of O where O is an nth root of unity. For any given n, let d_n denote all the divisors of n. For each d_n, take the minimal polynomial of e(O) where O is a d_nth root of unity, and let S(a,n) be the product of all these polynomials. Does an element e(O) exist such that if n is prime, then for any integer a NOT 0 (mod n), S(a,n-1) = 0 (mod n). This must be true for ALL primes n.

[Nick]

Originally Posted by carpetpool

Bottom line, factor a^(p-1)-1 into irreducible polynomials I, and one of these polynomials when evaluated at a will be a multiple of p, if a is not 0 (mod p).

For any prime number \(p\), in the ring of polynomials with coefficients in the integers modulo \(p\) we have
\[ X^{p-1}-1=(X-1)(X-2)(X-3)\ldots (X-(p-1)). \]