20171228, 06:50  #1 
"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 
20171228, 12:48  #2  
Dec 2012
The Netherlands
1765_{10} Posts 
Quote:
\[ X^{p1}1=(X1)(X2)(X3)\ldots (X(p1)). \] 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
sets of 3 primes  MattcAnderson  Miscellaneous Math  3  20171018 00:24 
Polynomial Coefficients Integer Sets  carpetpool  carpetpool  1  20170222 08:37 
Does 2^nn2 have a covering set?  Stargate38  And now for something completely different  13  20170121 11:52 
Covering sets  robert44444uk  Computer Science & Computational Number Theory  15  20170104 12:39 
Julia Sets  mfgoode  Miscellaneous Math  2  20060404 00:18 