Editing Number theory (section)

=== Probabilistic number theory ===
{{Main|Probabilistic number theory}}

Probabilistic number theory starts with questions such as the following: Take an integer {{mvar|n}} at random between one and a million. How likely is it to be prime? (this is just another way of asking how many primes there are between one and a million). How many prime divisors will {{mvar|n}} have on average? What is the probability that it will have many more or many fewer divisors or prime divisors than the average?

Much of probabilistic number theory can be seen as an important special case of the study of variables that are almost, but not quite, mutually [[statistical independence|independent]]. For example, the event that a random integer between one and a million be divisible by two and the event that it be divisible by three are almost independent, but not quite.

It is sometimes said that [[probabilistic combinatorics]] uses the fact that whatever happens with probability greater than <math>0</math> must happen sometimes; one may say with equal justice that many applications of probabilistic number theory hinge on the fact that whatever is unusual must be rare. If certain algebraic objects (say, rational or integer solutions to certain equations) can be shown to be in the tail of certain sensibly defined distributions, it follows that there must be few of them; this is a very concrete non-probabilistic statement following from a probabilistic one.

At times, a non-rigorous, probabilistic approach leads to a number of [[heuristic]] algorithms and open problems, notably [[Cramér's conjecture]].