<s>[INST] 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$
 [/INST] 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*}
</s>