So, today I came up with a method for factoring polynomials whose coefficients are either $-1$ or $1.$
Let me explain with examples.
Example No. 1. Factorize $P(x)=x^8+x^7+1$
Solution. It is known that if this polynomial can be represented as a product of at least two other polynomials, then any of the coefficients must also be either -1 or 1, and the degree of at least one of them does not exceed 8:2=4. We will be looking for him.
Now we substitute x=3 and get $P(3)=8749 = 13 \cdot 673$, that is, the divisors of 8749 are 1, 13, 673, 8749. The minimum value of a polynomial with the described properties is $3^1-1=2$, and the maximum is $3^4+3^3+3^2+3+1=(3^5-1):2=121$.
There is only 1 divisor of the number 8749, which is between the numbers 2 and 121. This is 13. We are looking for a polynomial whose value at $x = 3$ is 13, for this we convert 13 to the ternary system - it will be $111$. So our estimated polynomial is $x^2+x+1$. Dividing the polynomial $x^8+x^7+1$ by $x^2+x+1$, we find that it is divisible, and since we have already shown that $x^2+x+1$ was the only possible polynomial, the factorization is complete: $x^8+x^7+1=(x^2+x+1)(x^6-x^4+x^3-x+1)$
Example No. 2. Factorize $P(x)=x^7-x^6+x^5+x^3+1$
Solution. We substitute $x=3$ and get $P(3)=1729=7\cdot13\cdot19$, look for the divisors of 1729, which are between 2 and $(3^{7//2+1}-1)/2=40$, this is 7, 13 and 19. Similarly, we convert them into the ternary system and get $7_{10}=21_3$, $13_{10}=111_3$ and $19_{10}=201_3$. Therefore, the corresponding polynomials are $x^2-x+1$, $x^2+x+1$ and $x^3-x^2+1$ (because in the ternary system $2=10-1$). As last time, we check each polynomial for divisibility and find that $x^7-x^6+x^5+x^3+1=(x^2-x+1)(x^2+x+1 )(x^3-x^2+1)$.
However, I assume that this method was discovered by someone else before me. And so I ask, was he already known?
