Hi,
I have no idea where to look for, so I'm hoping you can give me some pointers.
I'm interested by numbers of form $p-1$ when $p$ is a prime number. Do they have a name, so that I can google them?
More precisely, I'm interested in their factors. Ok, obviously 2 is a factor, but what about the others? Are there a lot of small factors? Do we know the rate of the growth of its larger factor, is it linear, logarithmic?
Thanks.
Two extremes of this problem are Fermat primes and Sophie Germain primes. If either class had infinitely many members, that would contribute to an answer of your question. There is literature about the distribution of prime factors (cf. Riesel and Knuth), but I do not know the literature regarding the restriction to numbers of the form prime - 1 .
If I had to start anywhere for questions like this, I would choose one or all three of the following:
Richard Guy's Unsolved problems in Number Theory,
Hans Riesel's book on computer methods for primality proving and factorization,
Prime Numbers: a Computational perspective, by Crandall and Pomerance.
Forgive my memory if the titles or authors are missing or incorrectly spelled.
Gerhard "Ask Me About System Design" Paseman, 2010.06.08
Let me address "Are there a lot of small factors?" which does have an answer without resorting to conjectures. It follows from the sieve theory that there is a small constant $C$ (like 6 - I don't recall it exactly, but I am pretty sure it is known explicitly), such that for infinitely many primes $p$, the integer $p-1$ has at most $C$ prime factors. See sections 8, 9 in H. Halberstam, H.-E. Richert, Sieve Methods, LMS Monographs, Academic Press, London, 1974.
There is a curious reason why I was interested in this question. In a particular problem in computational group theory, the length of the longest subgroup chain was an important parameter. It is obviously bounded by the number of prime factors (with multiplicities) in the order of the group. Now, for a few prime factors like 2 and 3, the pioneers of group theory (Burnside et al.) classified all such groups (they are all solvable). But beyond a certain point this naive approach to classification could not continue: conjecturally, there are infinitely many primes $p$ for which $|PSL(2,p)|=p(p-1)(p+1)/2$ has 6 prime factors. If I recall correctly, the current state of art implies that you can remove the word "conjecturally" when you replace 6 with 13.
These numbers do have lots of factors. Write $\omega(n)$ for the number of distinct prime factors of $n$. Then Halberstam proves (MR0073627) that
$\sum_{p \leq X} \omega(f(p)) \log{p}\sim X \log{\log{X}}$
where $f(x)$ is any fixed irreducible polynomial with integral coefficients which is not identically an integer multiple of $x$; in particular this applies with $f(x)=x-1$. Thus $p-1$ has, on average, $\log{\log{p}}$ distinct prime divisors.
I don't feel particularly qualified to answer this question, but I should mention that primes are expected to be "random modulo local obstructions". By this, I mean that aside from properties derived from being mutually coprime, you should not expect anomalous behavior. Some of this heuristic thinking has been codified into precise conjectures, such as Schinzel's hypothesis H, and the Hardy-Littlewood prime tuples conjecture.
If you want to apply this to the distribution of factors of $p-1$ as $p$ ranges over odd primes, you should first eliminate local considerations (namely noting that the numbers are all even), and then you should expect the rest of the factorizations to behave a lot like the factors of random integers. For example, we expect there to be infinitely many primes of the form $2p+1$ for $p$ a prime (called a Sophie Germain prime), and we expect infinitely many "very smooth" cases with many small factors. If you want finer information like the expected asymptotic distribution of Sophie Germain primes, you may have to wrestle with the expected error terms on the randomness, and I don't know how this is done precisely.
You should look at the paper by Erdos and Odlyzko "On the density of odd integers of the form $(p − 1)/2^n$ and related questions" in Journal of number theory, vol. 11 (1979) pp 257-263. Among other things they prove the the set of odd divisors of $p-1$ (where $p$ runs over primes) has a positive density.
As far as the largest prime factor of $p-1$ there is a result of Fouvry "Theoreme de Brun-Titchmarsh: application au theoreme de Fermat", Invent. Math. v. 79 (1985) pp 383-407, in which he proves that the set of primes $p$ for which the largest prime factor of $p-1$ is $\ge p^{.6687}$ has positive relative density in the set of all primes.
