1911 Encyclopædia Britannica/Number/Theory of Numbers

24. Theory of Numbers.—The theory of numbers is that branch of mathematics which deals with the properties of the natural numbers. As Dirichlet observed long ago, the whole of the subject would be coextensive with mathematical analysis in general; but it is convenient to restrict it to certain fields where the appropriateness of the above definition is fairly obvious. Even so, the domain of the subject is becoming more and more comprehensive, as the methods of analysis become more systematic and more exact.

The first noteworthy classification of the natural numbers is into those which are prime and those which are composite. A prime number is one which is not exactly divisible by any number except itself and 1; all others are composite. The number of primes is infinite (Eucl. Elem. ix. 20), and consequently, if n is an assigned number, however large, there is an infinite number (a) of primes greater than n.

If m, n are any two numbers, and m>n, we can always find a definite chain of positive integers (q₁, r₁), (q₂, r₂), &c., such that

m＝q₁n+r₁, n＝q₂r₁+r₂, r₁＝q₃r₂+r₃, &c.

with n>r₁>r₂>r₃ . . .; the process by which they are calculated will be called residuation. Since there is only a finite number of positive integers less than n, the process must terminate with two equalities of the form

r_h−2＝q_hr_h−1+r_h,  r_h−1＝q_h+1r_h.

Hence we infer successively that $r_{h}$ is a divisor of $r_{h-1},r_{h-2},\dots r_{1}$, and finally of $m\$ and $n\$. Also $r_{h}$ is the greatest common factor of $m,n$: because any common factor must divide $r_{1},r_{2},$ and so on down to $r_{h}$; and the highest factor of $r_{h}$ is $r_{h}$ itself. It will be convenient to write $r_{h}=\operatorname {dv} (m,n)$. If $r_{h}=1$, the numbers $m,n$ are said to be prime to each other, or co-primes.

25. The foregoing theorem of residuation is of the greatest importance; with the help of it we can prove three other fundamental propositions, namely:—

(1) If $m,n$ are any two natural numbers, we can always find two other natural numbers $x,y$ such that

$\operatorname {dv} (m,n)=xm-yn$.

(2) If $m,n$ are prime to each other, and $p\$ is a prime factor of $mn$, then $p$ must be a factor of either $m\$ or $n\$.

(3) Every number may be uniquely expressed as a product of prime factors.

Hence if $n=p^{\alpha }q^{\beta }r^{\gamma }\dots$ is the representation of any number $n\$ as the product of powers of different primes, the divisors of $n\$ are the terms of the product $(1+p+p^{2}+\dots +p^{\alpha })(1+q+\dots +q^{\beta })(1+r+\dots +r^{\gamma })\dots$ their number is $(\alpha +1)(\beta +1)(\gamma +1)\dots$ ; and their sum is $\textstyle \prod (p^{\alpha +1}-1)\div \prod (p-1)$. This includes $1$ and $n$ among the divisors of $n$.