3
$\begingroup$

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.

  • 0
    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.2012-05-30

2 Answers 2

3

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$

See http://oeis.org/A091490

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

  • 0
    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.2012-05-30
0

(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) , 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$ :

enter image description here
(source: helms-net.de)

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

enter image description here
(source: helms-net.de)

Distribution for a=6:

enter image description here
(source: helms-net.de)

  • 0
    @Nick: you're welcome to email me (my email address is visible on my home page).2012-05-31