The theory of numbers, by Robert D. Carmichael ...

14

THEORY OF NUMBERS

Let a be a number which is less than p and suppose that b
is a number less than p such that ab is divisible by p, and let
b be the least number for which ab is so divisible. Evidently
there exists an integer m such that
mb<p < (m+ i)b.
Then p - mb <b. Since ab is divisible by p it is clear that mab
is divisible by p; so is ap also; and hence their difference
ap-mab, =a(p-mrb), is divisible by p. That is, the product
of a by an integer less than b is divisible by p, contrary to the
assumption that b is the least integer such that ab is divisible
by p. The assumption that the theorem is not true has thus
led to a contradiction; and thus the theorem is proved.
III. If neither of two integers is divisible by a given prime
number p their product is not divisible by p.
Let a and b be two integers neither of which is divisible
by the prime p. According to the fundamental theorem of
Euclid there exist integers m, n, a, f such that
a=mp+a, o<a<p,
b=np+-3, o</3<p.
Then ab= (mp+a)(np +/) = (mnp-pi-cz +t) p+-a.
If now we suppose ab to be divisible by p we have aft divisible
by p. This contradicts II, since a and 3 are less than p. Hence
ab is not divisible by p.
By an application of this theorem to the continued product
of several factors, the following result is readily obtained:
IV. If no one of several integers is divisible by a given prime
p their product is not divisible by p.
~ 7. THE UNIQUE FACTORIZATION THEOREM
I. Every integer greater than unity can be represented in one
and in only one way as a product of prime numbers.
In the first place we shall show that it is always possible
to resolve a given integer m greater than unity into prime