3
$\begingroup$

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$

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Arthur Oct 31 '16 at 8:05
3
+25
$\begingroup$

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

| cite | improve this answer | |
$\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.