Arithmetic Tutorial from The Amateur Logician:
Even vs. Odd Numbers
Prime vs. Composite Numbers
Sieve of Eratosthenes
Deficient, Perfect, and Superabundant Numbers
Multiple, Superparticular, Superpartient and their Reciprocals
Plane Numbers: Triangular, Square, Pentagonal, etc.
Solid Numbers: Pyramid, Cube, Scalene, etc.
Basic Definitions. . .
• Prime Number: a positive integer greater than one whose only positive divisors are one and itself.
• Composite Number: a positive integer greater than one that has a positive divisor other than one and itself.
Knowing a number’s factors tells us a lot about that number. If it has a factor of two, for example, we know it is even. Most fundamentally, the most important factors consist of prime numbers. When thinking about the “structure” of natural numbers multiplicatively, the prime numbers are like the “atoms” of natural numbers.
Prime Numbers:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, …
In Book VI of The Elements, Euclid tells us that a “prime number is that which is measured by a unit alone.” That is what makes it a kind of “atom.” A prime number is divisible only by itself and the number one. In contrast, a “composite number is that which is measured by some other number” (ibid). Think of composite numbers as “composed” of smaller numbers. Composite numbers are divisible by one, itself, and at least one other number.
For example, 5 is prime. It’s divisible only by 5 and 1. The next number, 6, is composite because not only 6 and 1 divides it, 2 and 3 do as well.
Euclid’s Proposition 31 (Book VI):
“Any composite number is measured by some prime number.”
Proposition 32:
“Any number either is prime or is measured by some prime number.”
This brings us to the Fundamental Theorem of Arithmetic!
After that, we’ll look at one of the most amazing proofs that there must be an unending number of prime numbers. Euclid’s proof, which appears as Proposition 20 in Book IX, is one of the most beautiful proofs in all of mathematics.
Another issue to be raised: Is one a prime number? Although it is divisible only by one and itself, the answer is no. This exclusion preserves the uniqueness stated in the Fundamental Theorem of Arithmetic, since treating one as prime would undermine it. Let’s now examine the theorem.
Fundamental Theorem of Arithmetic
Without a formal proof at present, let’s take a “divide and conquer” take. We can take any natural number greater than one, and express it uniquely as a product of primes.
☀ We start with a positive integer greater than one.
☀ If it happens to be prime, we’re done.
☀ If that number is not, we break it up into factors.
☀ Are those primes? Stop.
☀ If not, break up again. Etc.
☀ Eventually, we’ll end up with all primes.
For example, 70 is a positive integer. It has factors 2 and 35, since 70 = 2*35. 2 is prime. 35 is composite. 35 has factors 5 and 7, since 35 = 5*7. 5 and 7 are prime.
Thus, 70 = 2*5*7.
The Fundamental Theorem of Arithmetic is intuitively clear. The statement of a unique outcome is why we don’t consider one a prime number. For example, 10 = 2*5. If one is a prime, it would also be true that 10 = 1*2*5. And so, we wouldn’t have one unique possibility.
Interestingly, there are different number systems in which don’t exhibit unique factorization. Imagine a number system only consisting of even integers: {0, ±2, ±4, ±6, ±8, …}. In this universe, there are no odd numbers. Technically speaking, in abstract algebra, it still forms a “ring.” We can add and multiply even integers without leaving this universe.
Factoring is possible in this universe. However, “primes” can’t be broken down into smaller evens. So, 2, 6, 10, 14, 18, … are “primes.” For instance, 6 is a prime because it cannot be broken down into smaller even numbers. Also, uniqueness is gone. Take 36. It can be factored into 6*6 or 2*18.
Infinitely Many Primes…!
Euclid’s Proposition 32 (Book IX):
“Prime numbers are more than any assigned multitude of prime numbers.”
Think in the concrete!
Pick a number: 6 = 2*3. Next, add one: 2*3+1.
Any prime that divides this number can’t be 2 or 3.
By the Fundamental Theorem of Arithmetic, there must exist a prime number that divides it. Thus, because it can’t be 2 or 3, there must exist a prime greater than 2 or 3.
While worded with modern mathematics, this is the essence of Euclid’s amazing proof. Notice the use of the Fundamental Theorem of Arithmetic. We’re thinking about how m can be expressed as a product of primes. m+1 won’t be divisible by any arbitrary number of primes. This means that there must be more than n primes. Incredible!
This proof technique is so simple yet so profound. We can take that technique to then prove that there are arbitrarily long “deserts” of consecutive composites with no primes.
Pick a number n. There will be a run of n numbers that are all composite until the next prime number is reached. Let’s look at that next!
Prime Regularity…?
There are lots of runs of consecutive composite numbers.
Example: 8, 9, 10 is a run of three composites
Example: 24, 25, 26, 27, 28 is a run of five composites
Example: 90, 91, 92, 93, 94, 95 is a run of six composites
Note that the numbers 11, 29, and 96 are primes.
Also, 7, 23, and 89 are primes.
Question: Is there a max run of consecutive composite numbers?
The answer is, in fact, no! Pick any natural number n, there exists a run of n consecutive composite numbers. We’ll logically deduce that n might as well be 890,457,581,011. There exists such a run! There are “deserts” of composite numbers within the natural numbers. Amazing!
Let’s utilize Euclid’s proof technique here. Consider that 2*3+2 is composite. That’s because 2 divides 2*3 and 2 divides the plus 2. Likewise, 2*3 + 3 is composite because 3 divides 2*3 and 3 divides the plus 3.
The journey can be as long as we want. We start a journey with a prime number and then go through a desert of composite numbers until reaching the next prime number. Cool!