4
$\begingroup$

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!

$\endgroup$
1
  • 3
    $\begingroup$ Hint : the product of two polynomials is the same as the product of their Gcd and their lcm. $\endgroup$ Jul 13 '17 at 17:53
3
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ I think you want $1+ap=bq$ for $a,b \in \mathbb N$. $\endgroup$
    – lhf
    Jul 13 '17 at 18:49
  • $\begingroup$ @lhf I don't see why I need that. $\endgroup$ Jul 13 '17 at 18:50
  • $\begingroup$ Because $a$ or $b$ is negative if $1=ap+bq$. $\endgroup$
    – lhf
    Jul 13 '17 at 18:58
  • $\begingroup$ @lhf Then, we might use the fact that $1$ is the modular inverse of itself. $\endgroup$ Jul 13 '17 at 19:05
  • $\begingroup$ @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. $\endgroup$ Jul 13 '17 at 20:50
0
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.