# Prove that for infinitely many $n$ the greatest prime factor of $a^n-1$ is greater than $n\log_a n$

This problem from Andreescu Problems from the book Page 331 problem 29 :

Let $a$ be an integer greater than 1. Prove that for infinitely many $n$ the greatest prime factor of $a^n-1$ is greater than $n\log_a n$

• You shouldn't change the problem text like that. There are many more possible values for $n$ than for $a^k$, and that might ruin the prime decomposition properties. Specifically, just because there are infinitely many $n$ that fulfill a property doesn't mean there are infinitely many $a^k$ that fulfill the same. What if it turns out to be relevant whether $n$ is prime, for instance? That happens for infinitely many $n$, but at most one $a^k$. – Arthur Oct 31 '16 at 8:05

By Zsigmondy's theorem, for every pair $(a,n)$ with $a\ge2$ and $n\ge7$, there is a prime $P$ such that $P$ divides $a^n-1$, but $P$ does not divide $a^k-1$ for any $1\le k<n$; in other words, the multiplicative order of $a$ modulo $P$ is precisely $n$. Due to Fermat's theorem, the multiplicative order divides $P-1$, so $P\equiv1\pmod{n}$.

Hence, for $n\ge7$ there is a prime divisor $P$ of $a^n-1$ with $P\in\{n+1,2n+1,3n+1,\ldots\}$. Our goal is to make the small elements in this set composite.

Take three large consecutive primes, $q<q_1<q_2$ and let $Q=\prod_{p<q}p$ be the product of primes up to $q-1$. Chose a positive integer $n$ such that \begin{align*} qn+1 &\equiv 0 \pmod{Q} \\ (q-1)n+1 &\equiv 0 \pmod{q_1} \\ (q+1)n+1 &\equiv 0 \pmod{q_2} \\ \end{align*} By the Chinese Remainder Theorem, this system has a solution modulo $Qq_1q_2$. Instead of the smallest positive solution, let $n$ be the second one with $Qq_1q_2 < n < 2 Qq_1q_2$. Now consider the numbers $$n+1, \quad 2n+1, \quad \ldots, \quad (q-1)n+1, \quad qn+1, \quad (q+1)n+1, \quad \ldots, \quad (2q-1)n+1. \tag{1}$$ By the definition, the middle three terms, $(q-1)n+1$, $qn+1$, and $(q+1)n+1$ are divisible by $q_1$, $Q$ and $q_2$, respectively, so they are composite. The remaining elements are of the form $qn+1\pm kn$ with some $2\le k<q$; every prime divisor $p$ of $k$ divides $qn+1\pm kn$ as well. So the numbers in (1) are all composite. Therefore, $P \ge 2qn+1$.

From the Prime Number Theorem we can get \begin{gather*} n < 2Qq_1q_2 < e^{(1+\varepsilon)q} \\ P > 2qn > \frac{2\ln n}{1+\varepsilon} n > n\cdot \log_a n. \end{gather*}