A344198 - OEIS

%I #27 May 18 2021 08:46:46

%S 12,18,30,36,54,60,84,156,198,390,540,1950,4788

%N Numbers m > 9 such that x^m + x^9 + 1 is irreducible over GF(2) while x^m + x^9 + x^6 + x^3 + 1 = x^m + (x^3 + 1)^3 is not.

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

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

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

%C then:

%C (i) (A) implies (B);

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

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

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

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

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

%C 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).)

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

%C If the conjecture is true, this is also numbers m >= 10 such that x^m + x^9 + 1 is irreducible over GF(2) while x^m + x^9 + x^8 + x + 1 is not (the case r = 9, k = 1, e = 0).

%e 18 is a term because x^18 + x^9 + 1 is irreducible over GF(2) but x^18 + x^9 + x^6 + x^3 + 1 is not: x^18 + x^9 + x^6 + x^3 + 1 = (x^6 + x^3 + 1)*(x^12 + x^9 + 1).

%o (PARI) isA344198(n) = polisirreducible(Mod(x^n+x^9+1, 2)) && !polisirreducible(Mod(x^n+x^9+x^6+x^3+1, 2))

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

%K nonn,hard,more

%O 1,1

%A _Jianing Song_, May 11 2021