 mersenneforum.org Covering sets for a^n-1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2017-12-28, 06:50 #1 carpetpool   "Sam" Nov 2016 5×67 Posts Covering sets for a^n-1 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. Last fiddled with by carpetpool on 2017-12-28 at 06:51   2017-12-28, 12:48   #2
Nick

Dec 2012
The Netherlands

176510 Posts Quote:
 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)).$  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Miscellaneous Math 3 2017-10-18 00:24 carpetpool carpetpool 1 2017-02-22 08:37 Stargate38 And now for something completely different 13 2017-01-21 11:52 robert44444uk Computer Science & Computational Number Theory 15 2017-01-04 12:39 mfgoode Miscellaneous Math 2 2006-04-04 00:18

All times are UTC. The time now is 08:48.

Mon Oct 3 08:48:05 UTC 2022 up 46 days, 6:16, 0 users, load averages: 0.81, 1.07, 1.15

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔