# Prove that for every pair of coprime positive integers $p,q$, $(x^{pq}-1)(x-1)$ is divisible by $(x^p-1)(x^q-1)$.

Prove that for every pair of coprime positive integers $p,q$ the expression $(x^{pq}-1)(x-1)$ is divisible by $(x^p-1)(x^q-1)$.

My attempts:

$x^{pq}-1=(x^p)^q-1$ which is divisible by $x^p-1$

again, $x^{pq}-1=(x^q)^p-1$ which is divisible by $x^q-1$.

But how to prove that it is divisible by their products? Just now an idea struck me. Can I consider gcd of $x^p-1$ and $x^q-1$ as $x-1$ ?. If yes, then we are done!

• Hint : the product of two polynomials is the same as the product of their Gcd and their lcm. Jul 13 '17 at 17:53

To answer your question, if the exponents are not coprime, you can try to prove the general formula: $$\gcd(x^m-1,x^n-1)=x^{\gcd(m,n)}-1,$$ from which you can deduce that $\;(x^{mn}-1)(x^{\gcd(m,n)}-1)$ is divisible by $\;(x^m-1)(x^n-1)$.

Regarding $x$ as a complex variable, then the roots of $(x^p-1)(x^q-1)$ are the $p$-th roots of unity and the $q$-th roots of unity. Since $p$ and $q$ are coprime the two sets of roots have intersection only $1$. Now $x^{pq}-1$ has roots which include both previous sets since $x^p=1$ or $x^q=1$ both imply $x^{pq}=1$. Thus $(x^p-1)(x^q-1)$ divides $(x^{pq}-1)(x-1)$ where the extra factor of $x-1$ is needed because $1$ is a double root. If $r=\gcd(p,q)$ and $s=\textrm{lcm}(p,q)$ then a similar argument works but now $(x^p-1)(x^q-1)$ divides $(x^s-1)(x^r-1)$.

You are on the right path. After what you've done, all that's left to prove that $\gcd(x^p-1,x^q-1)=x-1$.

To show that, let the $\gcd$ be $d$.Then, $x-1 \mid d$ since $x-1 \mid x^p-1$ and $x-1 \mid x^q-1$. Also, we have, $x^p \equiv 1 \equiv x^q \pmod{d}$. Then, $$x=x^1=x^{ap+bq} \text{[for some }a, b \in \mathbb{Z} \text{ by Eucledian algorithm]} = x^{ap} \cdot x^{bq} \equiv 1 \cdot 1 \equiv 1 \pmod{d}$$

Hence, $d \mid x-1$. So, $d = x-1$.

• I think you want $1+ap=bq$ for $a,b \in \mathbb N$.
– lhf
Jul 13 '17 at 18:49
• @lhf I don't see why I need that. Jul 13 '17 at 18:50
• Because $a$ or $b$ is negative if $1=ap+bq$.
– lhf
Jul 13 '17 at 18:58
• @lhf Then, we might use the fact that $1$ is the modular inverse of itself. Jul 13 '17 at 19:05
• @lhf Negative exponents on $x$ are well-defined since $x^p\equiv 1\pmod{d}$ implies $x$ is a unit mod $d$. But in fact Bezout is not needed since the order of $x$ divides the coprimes $p$ and $q$ so the order must be $1$. See this answer for more on this type of proof. Jul 13 '17 at 20:50

Hint  With $\,f_n := (x^n-1)/(x-1),\,$ we seek to show $\,f_p f_q\mid f_{pq}$ which follows immediately from the fact that $f_n$ is a  strong divisibility sequence,  thus $\,f_p,f_q\mid f_{pq}\,$ by $\ p,q\mid pq,\,$ and, furthermore,$\,(f_p,f_q) = f_{\large (p,q)}\! = f_1 = 1,\,$ so by coprimality we have $\,f_p f_q\mid f_{pq}$