Number Theory/Elementary Divisibility

=Elementary Properties of Divisibility=
Divisibility is a key concept in number theory. We say that an integer formula_1 is divisible by a nonzero integer formula_2 if there exists an integer formula_3 such that formula_4.
For example, the integer 123456 is divisible by 643 since there exists a nonzero integer, namely 192, 
such that 
formula_5.
We denote divisibility using a vertical bar: formula_6 means "a divides b".
For example, we can write formula_7.
If formula_2 is not divisible by formula_1, we write formula_10. For example, formula_11.
The following theorems illustrate a number of important properties of divisibility. 
Theorem 1.
Suppose formula_12 and formula_13 are integers and formula_14 and formula_15. Then
formula_16.
Proof:
Let formula_12 and formula_13 be integers and suppose formula_14 and formula_15.
Then there exist integers formula_21 and formula_22 such that formula_23 and formula_24. Thus
formula_25
We know that formula_26 is also an integer, hence formula_16.
Corollary.
Suppose formula_28 and formula_29 are integers and formula_14 and formula_31.
Then formula_32 and formula_33.
Proof:
Letting formula_34 and formula_35 in Theorem 1 yields 
formula_36. Similarly, letting formula_37 and formula_38
yields formula_39. Finally, setting s=0, yields formula_33.
Theorem 2.
If formula_41 are integers, and formula_42 and formula_43, then formula_44.
Proof:
Let formula_45 and formula_3 are integers, and suppose formula_42 and formula_43.
Then 
formula_49 and formula_50 for some integers formula_51 and formula_52.
Then
formula_53, and hence formula_44.
Theorem 3.
Let formula_55 be integers. Then formula_56 if and only if formula_57
Proof:
Let formula_55 be integers. Suppose formula_59.
Then there exists an integer formula_60 such that
formula_61.
So it follows that
formula_62 and hence formula_63.
For the reverse direction, we suppose formula_63.
Then there exists an integer formula_65 such that
formula_66, so formula_67
We know that c is non-zero, hence
formula_68 i.e., formula_69.
Thus, formula_6.
Prime and composite numbers.
A natural number "p" greater than one is a prime number if it has exactly two distinct natural number divisors, itself and 1. The first eleven such numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. There are an infinite number of primes, however, as will be proven below. 
A natural number greater than one that is not prime is composite. Thus, 4, 6, 8, 9, 10, 12, 14, 15 and 16 are the first few composite numbers.
Note that the number 1 is the only natural number that is neither prime nor composite.
Theorem 4.
Fundamental Theorem of Arithmetic (FTA)
Every composite positive integer "n" is a product of prime numbers. Moreover, these products are unique up to the order of the factors.
Proof:
We prove this theorem by contradiction.
Suppose there exists a positive composite integer that is not a product of prime numbers; let "N" be the smallest such integer. Since "N" is composite, it can be written as "N" = "a" "b" for some
integers "a" and "b" with "a", "b" &gt; 1. 
Since "N" is not a product of primes, at least one of "a" and "b" is not a product of primes; without loss of generality, let's say "a" is not a product of primes.
Then, since "a"&gt;1, "a" is composite, and hence "a" is a positive composite number that is not a product of prime numbers.
But, since "a"&lt;"N" this contradicts our assumption that "N" is the smallest such number.
Hence, there does not exist a smallest such number, and therefore there do not exist composite positive integers which are not the product of prime numbers.
Proof of uniqueness is left to the reader.
Alternative Proof:
This is an inductive proof.
The statement ""k" is composite implies that "k" is a product of prime numbers" is true when formula_71.
Let formula_72 be an integer formula_73.
Suppose the statement is true for all formula_74.
formula_75 is either composite or prime.
If formula_75 is prime, then the statement is true for formula_77
If formula_75 is composite, then formula_75 is divisible by some prime formula_80, so formula_77 can be written "k=pa" where "p" is prime and "a" is an integer with &lt;math&gt;1. Then "a" is either prime, or composite; if it is composite, then it is a product of prime numbers by our induction hypothesis.
Hence formula_75 can be written as a product of primes.
It follows that the statement is true for all formula_83 and hence by induction for all formula_84.
Proof of uniqueness is left to the reader.
Theorem 5.
There are infinitely many primes.
Proof:
Suppose that there are only formula_85 primes.
Let these primes be: formula_86. 
Let formula_87 
Then either formula_88 is prime, or it is a product of primes.
If is is a product of primes, it must be divisible by a prime formula_89 for some formula_90.
However,
formula_91
which is clearly not an integer: formula_88 is not divisible by formula_89. 
Hence, formula_94 is not a product of primes.
This is a contradiction, as by Theorem 4, all numbers can be expressed as a product of primes.
Therefore, either formula_94 is prime or it is divisible by some prime greater than formula_96.
We conclude that the assumption that there are only formula_97 primes is false.
Thus there are "not" a finite number of primes, i.e., there are infinitely many primes.
Theorem 6.
The Division Algorithm (Division with smallest non-negative remainder)
Let "a" and "b" be integers where formula_98. Then there exist uniquely determined integers "q" and "r" such that
formula_99
and formula_100.
Proof:
We define the set
formula_101
which is nonempty and bounded from above. Hence it has a maximal element which we denote by "q".
We set formula_102. It is formula_103 and formula_104.
This implies
formula_105
which contradicts to the maximality of "q" in "M".
We now prove the uniqueness of "q" and "r":
Let formula_106 and formula_107 be two integers which satisfy formula_108 and formula_109
and thus formula_110 which implies formula_111. This also shows formula_112 and we are done. 
Index