Factoring $n^{pq}-1$

95 Views Asked by At

I know that $$ n^{pq}-1=(n^{p(q-1)}+n^{p(q-2)}+\cdots+n^p+n^0)(n^p-1)=(n^{p(q-1)}+\cdots+n^p+n^0)(n^{p-1}+\cdots+n+1)(n-1),$$

is there another way to factor this? I remembered there's a way to factor them with two products of sums with both exponents $p$ and $q$ but I don't remember how.

1

There are 1 best solutions below

1
On BEST ANSWER

We have that $$x^n - 1 = \prod_{d | n} \Phi_d(x),$$

where $\Phi_d(x)$ is the $d$-th cyclotomic polynomial. The polynomials $\Phi_d(x)$ are irreducible, so you can't do any better than this.

For example, when $p, q$ are prime and $\mathrm{gcd}(p, q) = 1$ we have $$n^{pq} - 1 = \Phi_1(n)\Phi_p(n)\Phi_q(n)\Phi_{pq}(n)$$

Here $\Phi_1(n) = n - 1$, $\Phi_p(n) = n^{p - 1} + \ldots + n + 1$, $\Phi_q(n) = n^{q - 1} + \ldots + n + 1$.

Im not sure of a general expression for $\Phi_{pq}(n)$ other than as a product $$\prod_{1 \leq k \leq pq \\ \gcd(k, pq) = 1} \left(n - e^{2\pi i\frac{k}{pq}}\right).$$