Revision history [back]

Some notes as a complement to @nbruin's answer.

Denote by $\Phi_n$ the cyclotomic polynomial of degree $n$.

Note that $\Phi_n$ has degree $\phi(n)$ where $\phi$ is Euler's phi function. In the case of a prime power, the fomula is simple enough, and $\phi(p^m) = p^m - p^{m-1} = p^{m-1}(p-1)$.

In the case at hand, $p = 37$, $m = 5$, $n = 37^5 = 69,343,957$, we get:

sage: euler_phi(37^5)
67469796
sage: 37^5 - 37^4
67469796

So the degree of $\Phi_n$, which is also the degree of the cyclotomic field as an extension of $\mathbb{Q}[x]$, is 67,469,796.

The number of nonzero monomials of this polynomial is much less in this case though, since, for $n = p^m$, $\Phi_n = \Phi_p(x^{p^{m-1}})$.

So the number of nonzero monomials is the same as in $\Phi_{37}$, ie it is $37 - 1 = 36$.

Sage can deal with this polynomial easily if you define it as a sparse polynomial.

sage: F = CyclotomicField(37)
sage: P = F.polynomial()
sage: P
x^36 + x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
sage: 37^4
1874161
sage: R.<x> = PolynomialRing(QQ, sparse=True)
sage: P = R(P)
sage: Q = P(x^(37^4))
sage: Q
x^67469796 + x^65595635 + x^63721474 + x^61847313 + x^59973152 + x^58098991 + x^56224830 + x^54350669 + x^52476508 + x^50602347 + x^48728186 + x^46854025 + x^44979864 + x^43105703 + x^41231542 + x^39357381 + x^37483220 + x^35609059 + x^33734898 + x^31860737 + x^29986576 + x^28112415 + x^26238254 + x^24364093 + x^22489932 + x^20615771 + x^18741610 + x^16867449 + x^14993288 + x^13119127 + x^11244966 + x^9370805 + x^7496644 + x^5622483 + x^3748322 + x^1874161 + 1

You could try computing in the polynomial ring $R$, modulo this polynomial, and see how far that gets you...