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.
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
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$.
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.)
