# A limit concerning prime numbers

Let $p$ be a fixed prime and $r$ a fixed prime power. Let $x_{p'}$ denote the largest divisor of a positive integer $x$ such that $x_{p'}$ is not divisible by $p$. (For example, $60_{2'}=15$.) I would like to prove:

Claim: $\dfrac{(r^n-1)_{p'}}{n}\rightarrow\infty$ as $n\rightarrow \infty$.

Sorry if this is obvious and thank you for your help.

-
What is $p'$ supposed to be? –  Yemon Choi Jul 6 '13 at 21:41
@Yemon Choi: I have edited the post and defined $x_{p'}$ explicitly. I thought that this notation is common in number theory. –  Hung Nguyen Jul 6 '13 at 22:55

This is true, and due to Walter Feit (On large Zsigmondy Primes, PAMS 1988). (What he shows [Theorem B in the quoted paper] is the following:

Let $N$ be a positive integer. Then, for all but finitely many pairs of integers $<a, n>$ with $a>1$ and $n>2$ there exists a Zsigmondy prime with $|a^n-1|_p > n N +1.$ A Zsigmondy prime is one with multiplicative order of $a$ modulo $p$ being equal to $n$ (so, one that divides $a^n-1$ but not lower powers of $a$). The norm is the $p$-adic valuation (so, the largest power of $p$ dividing the number). )

A very nice proof of this fact (and lots of other cool stuff) is in the short paper:

On Zsigmondy Primes

Moshe Roitman,

PAMS 1997

-
This is helpful. Thank you very much. –  Hung Nguyen Jul 7 '13 at 13:45

If $p'=p$, this is in fact false. Let $r=1+p$ for $p$ odd. Then

$$r^n = (1+p)^n = \sum_{i=0}^n p^i \left ( \begin{array}{c} n \\ i \end{array}\right) = 1 + np + \sum_{i=2}^n p^i \left ( \begin{array}{c} n \\ i \end{array}\right) = 1 + np + np^2 \sum_{i=2}^n \frac{p^{i-2}}{i} \left ( \begin{array}{c} n-1 \\ i-1 \end{array}\right)$$

As long as $p$ is odd, the $(i)_p \leq p^{i-2}$, so $\left(\sum_{i=2}^n \frac{p^{i-2}}{i} \left ( \begin{array}{c} n-1 \\ i-1 \end{array}\right) \right)_p\geq 1$ , so that term does not affect the $p$-part of $(r^n-1)$, which is $(np)_p \leq pn$.

-
I used $p'$ to mean the set of primes not equal $p$. Sorry for the confusion. –  Hung Nguyen Jul 6 '13 at 22:57
Ah then this follows from what I wrote - since the $p$-part is $O(n)$, the non-$p$-part increases exponentially. –  Will Sawin Jul 6 '13 at 23:00
Since $r$ is a fixed prime power, it is unlikely to be $p+1$... –  Igor Rivin Jul 7 '13 at 5:12
The same reasoning works for anything that is $1$ mod $p$. For other things, you can ignore the powers that are not $1$ mod $p$, which means you can assume $n$ is a multiple of the least $k$ such that $r^k\equiv 1$ mod $p$, but then you can just replace $r$ with $r^k$. –  Will Sawin Jul 7 '13 at 10:04

A theorem of Zsigmondy says that for $n$ large enough (which means $n$ at least 7 in the worst case, for $r=2$), $r^n - 1$ has a prime factor $q$ which does not divide $r^m - 1$, for any $m$ less than $n$. So in fact something stronger holds. Let $f_n$ be the greatest prime factor of $r^n - 1$, then $f_n/n$ greater than $\log n$ eventually, as $f_n$ is greater than the $n$th prime for $n$ sufficiently large.

(I see a missing piece, which I will try to repair. Of course, the largest prime factor among the factors of $r^m - 1$ for $m \lt n$ is greater than the $n$th prime, but I believe one can leverage this into a proof of the above.)

-
Can you explain why $f_n$ is greater than $n$th prime for $n$ sufficiently large? –  Hung Nguyen Jul 7 '13 at 1:48
I thought I could. A possible attack is to show f_n is really large for n prime, and then apply that fact recursively, but I think a proof by contradiction will be easier. –  The Masked Avenger Jul 7 '13 at 4:08
The argument does show that the OP's statement holds with $\limsup$ instead of $\lim...$ –  Igor Rivin Jul 7 '13 at 5:14
If I read Igor Rivin's post correctly, then it seems Walter Feit proved for prime powers $g_n$ that they are large enough, and so that if I replace $f_n$ greatest prime factor with $f_n$ greatest prime power factor, this modified statement is a consequence of Feit's Theorem B. –  The Masked Avenger Jul 7 '13 at 6:24