Solution 1
First, note that if we reverse the order of the coefficients of each factor, then we will obtain a polynomial whose coefficients are exactly the coefficients of p(x) in reverse order. Therefore, if p(x)=(1−x)a1(1−x2)a2(1−x3)a3⋯(1−x32)a32, we define the polynomial q(x) to be q(x)=(x−1)a1(x2−1)a2(x3−1)a3⋯(x32−1)a32, noting that if the polynomial has degree n , then the coefficient of xn−1 is −2 , while the coefficients of xn−k for k=2,3,…,32 are all 0 .
Let Pn be the sum of the n th powers of the roots of q(x) . In particular, by Vieta's formulas, we know that P1=2 . Also, by Newton's Sums, as the coefficients of xn−k for k=2,3,…,32 are all 0 , we find that P2−2P1P3−2P2P4−2P3P32−2P31=0=0=0⋮=0. Thus Pn=2n for n=1,2,…,32 . Now we compute P32 . Note that the roots of (xn−1)an are all n th roots of unity. If ω=e2πi/n , then the sum of 32 nd powers of these roots will be an(1+ω32+ω32⋅2+⋯+ω32⋅(n−1)). If ω32=1 , then we can multiply by (ω32−1)/(ω32−1) to obtain 1−ω32an(1−ω32n). But as ωn=1 , this is just 0 . Therefore the sum of the 32 nd powers of the roots of q(x) is the same as the sum of the 32 nd powers of the roots of (x−1)a1(x2−1)a2(x4−1)a4(x8−1)a4(x16−1)a16(x32−1)a32. The 32 nd power of each of these roots is just 1 , hence the sum of the 32 nd powers of the roots is P32=232=a1+2a2+4a4+8a8+16a16+32a32.(1) On the other hand, we can use the same logic to show that P16=216=a1+2a2+4a4+8a8+16a16.(2) Subtracting (2) from (1) and dividing by 32, we find a32=25232−216. Therefore, a32=227−211 .
Solution 2
By a limiting process, we can extend the problem to that of finding a sequence b1,b2,… of integers such that (1−z)b1(1−z2)b2(1−z3)b3⋯=1−2z. (The notation comes from the Alcumus version of this problem.)
If we take logarithmic derivatives on both sides, we get n=1∑∞1−znbn⋅(−nzn−1)=1−2z−2, and upon multiplying both sides by −z , this gives us the somewhat simple form n=1∑∞nbn⋅1−znzn=1−2z2z. Expanding all the fractions as geometric series, we get n=1∑∞nbnk=1∑∞znk=n=1∑∞2nzn. Comparing coefficients, we get d∣n∑dbd=2n for all positive integers n . In particular, as in Solution 1, we get b1+2b2+4b4+8b8+16b16+32b32b1+2b2+4b4+8b8+16b16+32b32=232,=216, from which the answer b32=227−211 follows.
Remark: To avoid the question of what an infinite product means in the context of formal power series, we could instead view the problem statement as saying that (1−z)b1(1−z2)b2⋯(1−z32)b32≡1−2z(modz33); modular arithmetic for polynomials can be defined in exactly the same way as modular arithmetic for integers. Uniqueness of the bn 's comes from the fact that we have (1−z)b1⋯(1−zn−1)bn−1≡1−2z(modzn) for all n≤33 by further reduction modulo zn (as zn∣z33 for n≤33 ), so we could uniquely solve for the bn 's one at a time. (This idea can be pushed further to explain why it's fine to pass to the infinite product version of the problem.)
To convert the above solution to one that works with polynomials modulo z33 , note that the derivative is not well-defined, as for instance, 1 and 1+z33 are equivalent modulo z33 , but their derivatives, 0 and 33z32 , are not. However, the operator f(z)↦zf′(z) is well-defined. The other key idea is that for any n , modulo zn , polynomials of the form 1−zf(z) are invertible, with inverse 1−zf(z)1≡1−zf(z)1−(zf(z))n=1+zf(z)+⋯+(zf(z))n−1). Therefore, for the polynomial in the problem, call it g(z) , we can still form the expression zg′(z)/g(z) , which is what we originally got by taking the logarithmic derivative and multiplying by z , and expand it to eventually get n=1∑32nbnk=1∑32znk≡n=1∑322nzn(modz33), which gets us the same relations (for n≤32 ).
Solution 3
From the starting point of Solution 2, (1−z)b1(1−z2)b2(1−z3)b3⋯=1−2z, taking reciprocals and expanding with geometric series gives us n=1∏∞(k=0∑∞zkn)bn=n=0∑∞2nzn. On the right, we have the generating function for the number of monic polynomials of degree n over the field F2 of two elements, and on the left, we have the factorisation of this generating function that considers the breakdown of any given monic polynomial into monic irreducible factors. As such, we have the interpretation bn=number of monic irreducible polynomials of degree n over F2. From here, to determine bn , we analyse the elements of F2n , of which there are 2n in total. Given α∈F2n , if the minimal polynomial fα of α has degree d , then d∣n and all other roots of fα appear in F2n . Moreover, if d∣n and f is an irreducible polynomial of degree d , then all roots of f appear in F2n . (These statements are all well-known in the theory of finite fields.) As such, for each d∣n , there are precisely dbd elements of F2n of degree d , and we obtain the same equation as in Solution 2, d∣n∑dbd=2n. The rest is as before.