MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Uep Jul 6 '13 at 22:55
up vote 3 down vote accepted

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

share|cite|improve this answer
This is helpful. Thank you very much. – Uep 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$.

share|cite|improve this answer
I used $p'$ to mean the set of primes not equal $p$. Sorry for the confusion. – Uep 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.)

share|cite|improve this answer
Can you explain why $f_n$ is greater than $n$th prime for $n$ sufficiently large? – Uep 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.