6
$\begingroup$

The question originally states:

Let $n$ and $q$ are positive integers, such that all prime divisors of $q$ are greater than $n$. Show that $$(q-1)(q^2-1)(q^3-1)...(q^{n-1}-1) \equiv 0 \pmod {n!}$$

I decided it would be easier to attempt and prove that there will always be at least one $q^i \equiv 1 \pmod {n!}$ but failed. I was hoping to get some assistance (maybe a hint) on this question since I never dealt with factorial and a modular question.

$\endgroup$
  • 2
    $\begingroup$ Note: $q$ having all prime divisors greater than $n$, is the same as to say that $q$ and $n!$ are co-prime. $\endgroup$ – Jakobian Oct 13 '18 at 11:41
  • $\begingroup$ @Jakobian I already tried using the fact that they are coprime but failed. $\endgroup$ – user587054 Oct 13 '18 at 12:25
1
$\begingroup$

For each prime natural number $p\leq n$, the largest nonnegative integer $r$ such that $p^r$ divides $n!$ is $r=e_p(n)$, where $$e_p(n):=\sum_{k=1}^\infty\,\left\lfloor\frac{n}{p^k}\right\rfloor\,.$$ We shall prove that if $E_{p,q}(n)$ is the largest nonnegative integer $r$ such that $p^r$ divides $\prod\limits_{k=1}^{n-1}\,\left(q^k-1\right)$, then $$e_p(n)\leq E_{p,q}(n)\,.$$

Let $v_p$ be the $p$-adic valuation (that is, $e_p(n)=v_p(n!)$ and $E_{p,q}(n)=v_p\left(\prod\limits_{k=1}^{n-1}\,\left(q^{k}-1\right)\right)$). We have for every positive integer $k$ that $$v_p\left(q^{k(p-1)}-1\right)=v_p\left(q^{p-1}-1\right)+v_p(k)\geq 1+v_p(k)$$ by the Lifting-the-Exponent Lemma. (The inequality $v_p\left(q^{p-1}-1\right)\geq 1$ is due to Fermat's Little Theorem.)

In particular, we see that $$E_{p,q}(n)\geq \sum_{k=1}^{\left\lfloor\frac{n-1}{p-1}\right\rfloor}\,v_p\left(q^{k(p-1)}-1\right)\geq \sum_{k=1}^{\left\lfloor\frac{n-1}{p-1}\right\rfloor}\,\left(1+v_p(k)\right)\,.$$ Since $e_p(n)=\displaystyle \sum_{k=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\,v_p(pk)= \sum_{k=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\,\left(1+v_p(k)\right)$ and $\left\lfloor\dfrac{n-1}{p-1}\right\rfloor \geq \left\lfloor\dfrac{n}{p}\right\rfloor$, we conclude that $$E_{p,q}(n)\geq \sum_{k=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\,\left(1+v_p(k)\right)=e_p(n)\,.$$


It is however not true that $q^i\equiv 1\pmod{n!}$ for some $i\in\{1,2,\ldots,n\}$. For example, take $n:=6$ and $q:=11$. Then, $$q^1-1=10\not\equiv0\pmod{6!}\,,$$ $$q^2-1=120\not\equiv0\pmod{6!}\,,$$ $$q^3-1=1330\equiv 610\equiv\not\equiv0\pmod{6!}\,,$$ $$q^4-1=14640\equiv 240\not\equiv0\pmod{6!}\,,$$ $$q^5-1=161050\equiv 490 \not\equiv0\pmod{6!}\,.$$ and $$q^6-1=1 1771560\equiv 360\not\equiv 0\pmod{6!}\,.$$

$\endgroup$
  • $\begingroup$ What I was trying to say is that there will always exist $q^i$ where $q^i \equiv 1 \pmod {n!}$ $\endgroup$ – user587054 Oct 13 '18 at 15:08
  • $\begingroup$ If you mean there will always exist an integer $q$ such that $q^i\equiv 1\pmod{n!}$, then it is a true statement since $q=1$ works. If you say, for any $q$ such that $\gcd(q,n!)=1$, there will always exist a positive integer $i$ such that $q^i\equiv1 \pmod{n!}$, then this is also true by picking $i=\phi(n!)$, where $\phi$ is Euler's totient function. However, if you say, for any $q$ such that $\gcd(q,n!)=1$, there will always exist a positive integer $i\in\{1,2,\ldots,n\}$ such that $q^i\equiv1 \pmod{n!}$, then the second part of my answer illustrates that this is false. $\endgroup$ – Batominovski Oct 13 '18 at 15:51
  • $\begingroup$ I understand now why my step was false, but now is there a different step I can possibly take. $\endgroup$ – user587054 Oct 13 '18 at 15:55

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.