The Binary Root

We can use polynomial to express binary number. For example,

$x^4+x^2+x+1 \implies 10111$

$x^3+x \implies 1010$

---

Part I (sum of roots)

Since $\alpha,\beta$ are both smaller than $10^4$ , they can have at most 4 digits . Given that the sum of two roots is a binary number, both polynomials cannot have two or more same elements from the set

$\left\{x^3,x^2,x,1\right\}$

We have 5 cases to deal, but the pattern is obvious. For case 1, we choose nothing from the set for one of the root $\alpha$ , then we will have $2^4$ numbers of $\beta$ . For case 2, we choose 1 element from the set for $\alpha$ , then we left $2^3$ numbers for $\beta$ . This pattern is the same for the other cases, add it all together we get

${4 \choose 0} \times 2^4 + {4 \choose 1} \times 2^3+{4 \choose 2} \times 2^2+{4 \choose 3} \times 2^1+{4 \choose 4} \times 2^0 = 81$

Most of these combinations are double counted $(\alpha,\beta)=(\beta,\alpha)$ , except for when $\alpha = \beta$ , which is the only combination, $(0,0)$ .

Hence, the number of combinations for $p$ is $40+1=41$ .

Part II (product of roots)

Given that the product of two binary roots (polynomials) is also a binary number, which implies that we cannot have two sets with any combination of elements that will have the same power after the production.

Obviously, we only have the sum of power $3+0=1+2$ . (We don't have to worry about $3+1=2+2$ ) since these will not even made it into Part I )

Hence, only 2 combinations we should exclude, which is

$(x^3+x)(x^2+1)$ and $(x^3+x^2)(x+1)$

In conclusion, we have $41-2=39$ combinations of $p,q$ .

[Thanks for reading, for any questions, please comment below]