"Sam"
Nov 2016
5·67 Posts

Covering sets for a^n1
If p is prime, and a is an integer 1 < a < p, then a^(p1) = 1 (mod p).
From this, a^(p1)1 divides p, and assuming p > 2, a^(p1)1 is a reducible polynomial. Therefore, let d_n denote all the possible divisors of p1, 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 p1th cyclotomic polynomial evaluated at a. This implies the solutions to (here Phi(n,x) is the nth cyclotomic polynomial evaluated at x).
Phi(p1, a) = 0 (mod p)
are precisely the primitive roots mod p.
If D_n are all the divisors of p1 with D_n < p1, that is all divisors of p1 NOT including p1, and p does not divide the D_nth cyclotomic polynomial at a, for all D_n then p MUST divide the p1th cyclotomic polynomial at a.
Bottom line, factor a^(p1)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.
p1 = 4 = 2^2, with divisors [1, 2, 4]
This implies, for any a, 5 divides either a1, a+1, a^2+1, or a = 5m for some integer m (assume not).
a1 = 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 nonzero residues (mod 5) as solutions to one of the three polynomials:
a^41 = (a+1)(a1)(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 p1 not including p1, one needs to find a polynomial P(x) defining the p1th cyclotomic field with fixed solutions to
P(a) = 0 (mod p).
Let's take a look at p = 7.
a^61 = (a+1)(a1)(a^2+a+1)(a^2a+1)
a+1 = 0 (mod 7) for a = 6 (mod 7)
a1 = 0 (mod 7) for a = 1 (mod 7)
a^2+a+1 = 0 (mod 7) for a = 2, 4 (mod 7)
a^2a+1 = 0 (mod 7) for a = 3, 5 (mod 7)
which covers all nonzero 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 degree4 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^n1, and the condition that if n is prime, then s_(a,n1) = 0 (mod n).
a_1 = a1
a_2 = (a1)*(a+1)
a_3 = (a1)*(a^2+a+1)
a_4 = (a1)*(a+1)*(a^21)
a_5 = (a1)*(a^4+a^3+a^2+a+1)
a_6 = (a1)*(a^2+a+1)*(a^2a+1)
a_7 = (a1)*(a^6+a^5+a^4+a^3+a^2+a+1)
a_8 = (a1)*(a+1)*(a^2+1)*(a^4+1)
a_9 = (a1)*(a^2+a+1)*(a^6+a^3+1)
a_10 = (a1)*(a^4+a^3+a^2+a+1)*(a^4a^3+a^2a+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,n1) = 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,n1) = 0 (mod n). This must be true for ALL primes n.
Last fiddled with by carpetpool on 20171228 at 06:51
