← Complete problem index

PROJECT EULER · #0797

Cyclogenic Polynomials

Statement only · UnsolvedOriginal problem ↗

A monic polynomial is a single-variable polynomial in which the coefficient of highest degree is equal to 1.

Define F to be the set of all monic polynomials with integer coefficients (including the constant polynomial p(x)=1). A polynomial p(x)F is cyclogenic if there exists q(x)F and a positive integer n such that p(x)q(x)=xn1. If n is the smallest such positive integer then p(x) is n-cyclogenic.

Define Pn(x) to be the sum of all n-cyclogenic polynomials. For example, there exist ten 6-cyclogenic polynomials (which divide x61 and no smaller xk1):

x61x4+x3x1x3+2x2+2x+1x2x+1x5+x4+x3+x2+x+1x4x3+x1x32x2+2x1x5x4+x3x2+x1x4+x2+1x3+1

giving

P6(x)=x6+2x5+3x4+5x3+2x2+5x.

Also define

QN(x)=n=1NPn(x).

It's given that Q10(x)=x10+3x9+3x8+7x7+8x6+14x5+11x4+18x3+12x2+23x and Q10(2)=5598.

Find Q107(2). Give your answer modulo 1000000007.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.