|
| |
|
|
A261524
|
|
Odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 1, where the polynomials are over GF(2).
|
|
5
|
|
|
|
3, 7, 9, 15, 21, 27, 31, 33, 35, 39, 45, 49, 51, 57, 63, 69, 73, 75, 77, 81, 85, 87, 91, 93, 99, 105, 111, 117, 119, 123, 127, 129, 133, 135, 141, 147, 153, 155, 159, 161, 165, 171, 175, 177, 183, 189, 195, 201, 203, 207, 213, 217, 219, 225, 231, 237, 243, 245, 249, 255, 259, 261, 267, 273, 279, 285, 287, 291, 297, 301
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
From the Golomb/Lee reference: "Theorem 7 (Welch’s Criterion): For any odd integer t, the irreducible polynomials of primitivity t divide trinomials iff gcd( 1 + x^n, 1 + (1+x)^n ) has degree greater than 1."
All Mersenne numbers (A000225) >= 3 are terms, as all primitive polynomials (over GF(2)) divide some trinomial.
All numbers of the form (2j-1)*(2^k-1); j>=1, k>=2 (A261871), are in the sequence. - Bob Selcoe, Sep 03 2015
If n is in the sequence, then so is every odd multiple of n, because 1+x^n divides 1+x^(k*n) and 1+(1+x)^n divides 1+(1+x)^(k*n).
The first few members of the sequence that are not multiples of other members are 3, 7, 31, 73, 85, 127, 2047, 3133, 4369, 8191, 11275 (see A261862). (End)
Also odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 0. This is because degree(gcd( 1 + x^n, 1 + (1+x)^n )) cannot be 1 since gcd( 1 + x^n, 1 + (1+x)^n ) is divisible by neither x nor x+1.
In general, let p be a prime, gcd(m,p) = 1, q > 1 be a power of p that is congruent to 1 modulo m. In the finite field F_q, the roots to x^m-1 are the nonzero ((q-1)/m)-th powers, so gcd(x^m-1, (x+1)^m-1) != 1 if and only if there are two nonzero ((q-1)/m)-th powers in F_q that differ by 1. If we homogenize, this is equivalent to x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m) having solutions in (F_q)* (dehomogenize by setting y = 1).
Let p be a prime, gcd(m,p) = 1. Suppose that q > 1 is the smallest power of p that is congruent to 1 modulo m, then gcd(x^m-1, (x+1)^m-1) != 1 in F_p[x] if m > q^(3/4): set k = (q-1)/m and A_1, A_2 both be the set of nonzero ((q-1)/m)-th powers in F_q (so |A_1| = |A_2| = m). Let N be the number of solutions to x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m) has solutions in (F_q)*, then by Theorem 7.1 of the László Babai link, we have N > m^2*(q-1)/q - (q-1)*sqrt(q) >= 0.
In particular, let p and r be distinct primes, r >= 5, t >= 1. Let Zs(d,p,1) is the d-th Zsigmondy number with parameters (p,1), then gcd(x^(Zs(r^t,p,1))-1, (x+1)^(Zs(r^t,p,1))-1) != 1 in F_p[x]. This is because for d != 2, Zs(d,p,1) = Phi_d(p)/r if d is of the form r^{t'}*ord(p,r) and Phi_d(p) otherwise (see A323748), where ord(a,k) is the multiplicative order of a modulo k, Phi_d(x) is the d-th cyclotomic polynomial. Here d = r^t, so Zs(d,p,1) = Phi_d(p)/r if p == 1 (mod r), Phi_d(p) otherwise. Note that Phi_{r^t}(p) = 1 + p^(r^(t-1)) + p^(2*r^(t-1)) + ... + p^((r-1)*r^(t-1)) > q^(3/4) = p^(3/4*r^t) since r >= 5. It is easy to show that Zs(p^r,p,1) <= q^(3/4) can only happen with r = 5, p == 1 (mod 5) and p <= 601, then we can check that gcd(x^(Zs(r^t,p,1))-1, (x+1)^(Zs(r^t,p,1))-1) = gcd(x^((p^4+p^3+p^2+p+1)/5)-1, (x+1)^((p^4+p^3+p^2+p+1)/5)-1) != 1 in F_p[x] in this case.
For another example, m = (2^(2^t)+1)*(2^(2^(t+1))+1) is a term of this sequence for all t >= 0, since in the case we have q = 2^(2^(t+2)), so m = q^(3/4) + 2^(2^(t+1)) + 2^(2^t) > q^(3/4).
Conjecture 1: Zs(d,2,1) is a term if and only if d is odd and d != 1, 15, 21. Verified for odd numbers up to 91.
Conjecture 2: for a prime p >= 3, gcd(x^(Zs(d,p,1))-1, (x+1)^(Zs(d,p,1))-1) != 1 if and only if d is an odd prime power > 1 other than (d,p) = (7,3), (7,9), (13,3), (37,3), (43,3), (79,3).
Note that the comment above shows that both conjectures are true for powers > 1 of a prime r >= 5. (End)
|
|
|
LINKS
|
|
|
|
MAPLE
|
filter:= proc(n) degree(Gcd(1+x^n, 1+(1+x)^n) mod 2)>1 end proc:
|
|
|
MATHEMATICA
|
okQ[n_] := Exponent[PolynomialGCD[1+x^n, 1+(1+x)^n, Modulus -> 2], x] > 1;
|
|
|
PROG
|
(PARI) W(n)=my(e=Mod(1, 2)); poldegree(gcd(e*(1+x^n), e*(1+(1+x)^n))) > 1;
forstep(n=1, 301, 2, if( W(n) , print1(n, ", ") ) );
(Sage)
x = polygen(GF(2), 'x')
[n for n in range(1, 10^3, 2) if gcd( 1+x^n, 1+(1+x)^n ).degree() > 1]
(PARI) isA261524(n, p=2) = my(d=znorder(Mod(p, n)), c=ffgen(p^d, 'c), g=ffprimroot(c)); forstep(e=0, p^d-2, (p^d-1)/n, if((g^e+1)^n==1, return(1))); return(0) \\ Jianing Song, Oct 14 2023, based on the equivalence of gcd(x^m-1, (x+1)^m-1) != 1 and two ((q-1)/m)-th powers in F_q differing by 1 (see Comments)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
