# Prove that $q^i \equiv 1 \pmod {n!}$ for all $q, n \in \mathbb{Z^+}$ where the prime factors of $q$ are greater than $n$

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.

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

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!}\,.$$
• What I was trying to say is that there will always exist $q^i$ where $q^i \equiv 1 \pmod {n!}$ – user587054 Oct 13 '18 at 15:08
• 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. – Batominovski Oct 13 '18 at 15:51