# Find $X$, $a$ : ALL prime factors of $(X^a - 1)/(X - 1) < X$

where $X$ is an odd prime, and $a$ is an odd integer.

For example, let $X = 37$, $a = 3$, we get $$\frac{37^3-1}{36} = 3 \times 7 \times 67.$$ When factoring numbers such as this, I've noticed that almost all have at least one prime factor larger than $X$ (e.g. 67 > 37). I would like to know for what values of $X$, $a$ are ALL of the prime factors of $(X^a-1)/(X-1)$ less than $X$. For example, let $X = 79$, $a = 3$, we get $$\frac{79^3-1}{78} = 3 \times 7^2 \times 43$$ and $43 < 79$.

My math education level is first year of high school so a transparent explanation, if possible, would be great. I understand basic congruences.

-
It's worth pointing out that since all the factors of X-1 are less than X (trivially), what you're really asking is when all the prime factors of X^a-1 are less than X. Unfortunately, primes and factoring tend to behave 'without rhyme or reason' when it comes to additivity properties (things like relating the factorizations of X+1 and X), so there's not much reason to believe that there's any structure at all to the answers. –  Steven Stadnicki May 29 '12 at 18:55
$\TeX$ will enlighten your question, I believe. –  Sangchul Lee May 29 '12 at 18:55
Cyclotomic polynomials might be relevant. –  anon May 29 '12 at 19:32
another relevant aspect is, whether the exponent $a$ is prime or composite. If it is prime, then the number of primefactors of the expression is small and thus the factors themselves must be large. If $a$ is composite, then the number of involved primefactors is bigger and thus the involved primefactors are smaller. –  Gottfried Helms May 30 '12 at 5:24

In the case $a=3$, the first few odd primes $x$ such that $(x^3-1)/(x-1) = x^2+x+1$ has all its prime factors less than $x$ are $$67, 79, 137, 149, 163, 181, 191, 211, 229, 263, 269, 277, 313, 373, 431, 439, 499, 521, 571, 631, 653, 787, 809, 811, 821, 823, 919, 947, 971, 991, 997$$

In the case $a=5$, the first few are $$7307, 9769, 16631, 26293, 28759, 28771, 36061, 38351, 41201, 51637, 52453, 53899, 66683, 71191, 71473, 74149, 76123, 85781, 90053$$

These do not seem to be in the OEIS.

In the case $a=7$, I found no primes $x$ less than $100000$.

EDIT: the least $x$ for $a=7$ seems to be 493397.

For a random integer $y$ from $1$ to $N$, the probability that all prime factors of $y$ are less than $y^{1/(a-1)}$ is asymptotically $\rho(a-1)$ where $\rho$ is Dickman's function. So heuristically one might expect that, asymptotically, a nonzero fraction of the primes up to $N$ would satisfy your condition for any given $a$. The fraction should be rather small though: $\frac{1}{2 \Gamma(2u+1)} \le \rho(u) \le \frac{1}{\Gamma(u+1)}$, and $\rho(6) \approx 1.9649696 \times 10^{−5}$.

-
"These do not seem to be in the OEIS" - are you like me, in that when the OEIS doesn't have my sequence I recheck the sequence, that I calculated and typed it in correctly, and then doubt myself? The OEIS knows a tremendous amount of random (to me anyway) stuff. –  mixedmath May 30 '12 at 0:51
Mr. Israel, I appreciate your examples and leads. What I meant to ask was what are the characteristics of X,a? For example, in the case of a=3, are there an infinite number of X meeting the condition, and if so is there a formula that generates all of them? For a=7 are there no X satisfying the given condition and if so how does one prove it? –  Nick May 30 '12 at 1:35
As I indicated, heuristically I would expect infinitely many $x$ for each $a$, in fact a nonzero (but very small) fraction of all primes should have this property. But that's only heuristic, on the basis that $(x^a-1)/(x-1)$ shouldn't behave too differently than a random integer. A proof may be out of reach of the current state of the art. And it's very unlikely that you could generate them by a manageable formula. –  Robert Israel May 30 '12 at 2:39

(This is more a comment than an answer, but because I want to show images I'll put it in an answer-box)

I've played around with this and considered the number of primefactors (with multiplicity) of $$\small f(p,a) = {p^a - 1 \over p-1 } \qquad p \in \mathbb{P}$$ $$\small n(p,a) = \text{ number of primefactors in } f(p,a)$$ for $\small a=5,6,7$ and $\small 1 \lt p \lt 200000 \qquad$ (I used $\small p \lt 20000$ for $\small a=7$).

The idea is, that if we have $\small n(p,a)<a$ , then at least one primefactor in $\small f(p,a)$ must be bigger than $\small p$.

If the exponent a is prime, then we have "few" primefactors, and if the exponent a is composite then we'll have "many" primefactors. Here are three images of the frequency distributions for $\small a=5,6,7$

Distribution for a=5. For $\small n(p,5) \lt 5$ (on the x-axis) we must have a primefactor $\small q \gt p$ :

Distribution for a=7 . For $\small n(p,7) \lt 7$ (on the x-axis) we must have a primefactor $\small q \gt p$ :

Distribution for a=6:

-
The number of prime factors of $x$, counting multiplicity, is generally denoted $\Omega(x)$. Quite a bit is known about the asymptotic distribution of this. Renyi and Turan showed that it obeys a "central limit theorem": if $\alpha(n) = \dfrac{\Omega(n) - \log \log n}{\sqrt{\log \log n}}$, then for any fixed $y$, as $n \to \infty$ the fraction of the integers $x \in [3,n]$ for which $\alpha(x) \le y$ approaches $\Phi(y)$, where $\Phi$ is the standard normal cumulative distribution function. –  Robert Israel May 30 '12 at 7:36
Mr Helms, I am looking at your amazing graphs with great interest, if not with great understanding (my math education level is no more than first year of high school). To make sure I understand your function n(p,a) = number of primefactors of f(p,a): What would n(73,3) equal? Also, by what means did you generate these graphs? –  Nick May 30 '12 at 13:29
@Nick: $\small f(73,3) = {73^3-1 \over 73-1} = 5403$ and $\small 5403 = 3^1 \cdot 1801^1$ so $\small n(73,3) = 2$ , the number of primefactors . Here we count the primefactors also multiple if their exponent exceeds 1. I've done the computations using Pari/GP. If you like I can copy/paste the procedure into my answer. –  Gottfried Helms May 30 '12 at 16:52
I don't think this is likely to shed much light on the original question, because you only have an "if", not "if and only if". Both $\Omega(f(137,3))$ and $\Omega(f(139,3))$ are $3$, but the largest prime factor of $f(137,3)$ is $73$ while the largest prime factor of $f(139,3)$ is $499$. –  Robert Israel May 30 '12 at 19:01
Mr Israel and Mr Helms: I want to thank both of you for considering my question. You have each given me so much to think about, it will take me awhile to try and digest it all. Is there a way I could contact you both if I have further questions in the future? I understand others need for privacy and I value it highly for myself, so I would be careful not presume on either your time or solitude. regards, Nick –  Nick May 30 '12 at 20:43