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.

  • 2
    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.2012-05-29
  • 0
    $\TeX$ will enlighten your question, I believe.2012-05-29
  • 2
    [Cyclotomic polynomials](http://en.wikipedia.org/wiki/Cyclotomic_polynomial) might be relevant.2012-05-29
  • 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
    "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.2012-05-30
  • 0
    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?2012-05-30
  • 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)

  • 1
    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.2012-05-30
  • 0
    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?2012-05-30
  • 0
    @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.2012-05-30
  • 0
    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$.2012-05-30
  • 0
    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, Nick2012-05-30
  • 0
    @Nicj: you're welcome, however due to decreasing health it might happen I answer only sporadically. Also you might be interested on this little treatize http://go.helms-net.de/math/expdioph/CyclicSubgroups_work.pdf which tries to shed some systematic light on questions like this. Miracuously: I began this treatize several times but seem to be unable to finish it seriously, perhaps in another life... It might be stimulating new views/questions anyway.2012-05-30
  • 0
    @Nick: you're welcome to email me (my email address is visible on my home page).2012-05-31