A344197 Numbers m > 5 such that x^m + x^5 + 1 is irreducible over GF(2) while x^m + x^5 + x^4 + x + 1 = x^m + (x + 1)^5 is not.

20, 300, 2660, 4500

Offset

1,1

Comments

Conjecture: Given e >= 0, odd numbers r, k > 0, a > 2^e*r*k, consider the following two statements:

(A) x^m + (x^k + 1)^(2^e*r) is irreducible over GF(2);

(B) x^m + x^(2^e*r*k) + 1 is irreducible over GF(2),

then:

(i) (A) implies (B);

(ii) if (B) is true and (A) is false, then:

(a) gcd(m,r) > 1;

(b) if prime p | gcd(m,r*k), then p*ord_p(2) | m;

(c) if e > 0, then m is odd.

Here ord(2,p) is the multiplicative order of 2 modulo p.

In other words, assuming that (B) is true, (A) is false if and only if (a), (b), (c) hold. (For the "if" part, note that if d = gcd(m,2^e*r) > 1 then x^m + (x^k + 1)^(2^e*r) must be reducible, since it is divisible by x^(m/d) + (x^k + 1)^(2^e*r/d).)

Here is the case r = 5, k = 1, e = 0, and (ii) means that m is in this sequence if and only if x^m + x^5 + 1 is irreducible and m is a multiple of 20.

Links

Table of n, a(n) for n=1..4.

Example

20 is a term because x^20 + x^5 + 1 is irreducible over GF(2) but x^20 + x^5 + x^4 + x + 1 is not: x^20 + x^5 + x^4 + x + 1 = (x^4 + x + 1)*(x^8 + x^7 + x^4 + x^3 + x^2 + x + 1)*(x^8 + x^7 + x^6 + x + 1).

Prog

(PARI) isA344197(n) = polisirreducible(Mod(x^n+x^5+1, 2)) && !polisirreducible(Mod(x^n+x^5+x^4+x+1, 2))

Crossrefs

Similar sequences: A344177 (r=3, k=1), A344198 (r=3, k=3), A344199 (r=3, k=5), this sequence (r=5, k=1), A344200 (r=5, k=3).

Sequence in context: A250014 A291256 A250015 * A138794 A077758 A202270

Adjacent sequences: A344194 A344195 A344196 * A344198 A344199 A344200

Keyword

nonn,hard,more

Author

Jianing Song, May 11 2021

Status

approved