Editing Number theory (section)

=== Other subfields ===
{{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?{{Main|Arithmetic combinatorics|Additive number theory}}

Combinatorics in number theory starts with questions like the following: Does a fairly "thick" [[infinite set]] <math>A</math> contain many elements in arithmetic progression: <math>a</math>,
<math>a+b, a+2 b, a+3 b, \ldots, a+10b</math>? Should it be possible to write large integers as sums of elements of <math>A</math>?{{Main|Computational number theory}}[[File:Computer History Museum (4145886786).jpg|thumb|A [[Lehmer sieve]], a primitive [[digital computer]] used to find [[primes]] and solve simple [[Diophantine equations]]]]There are two main questions: "Can this be computed?" and "Can it be computed rapidly?" Anyone can test whether a number is prime or, if it is not, split it into prime factors; doing so rapidly is another matter. Fast algorithms for [[primality test|testing primality]] are now known, but, in spite of much work (both theoretical and practical), no truly fast algorithm for factoring.