Understanding Proofs by Euclid — 101

Author(s): Pratik Shukla

Any Composite Number is Measured by Some Prime Number.

Originally published on Towards AI the World’s Leading AI and Technology News and Media Company. If you are building an AI-related product or service, we invite you to consider becoming an AI sponsor. At Towards AI, we help scale AI and technology startups. Let us help you unleash your technology to the masses.

In this series of articles, we are going to understand the proof of some famous theorems and propositions by the Greek mathematician Euclid. Here we are going to understand the proofs provided by Euclid himself in his time. There are other methods available to prove a theorem, but we think that it’s always best to start from scratch. The propositions are mentioned in his book named “Euclid’s Elements”.

Before getting into the proof of the proposition, let’s first understand some basic terms associated with it.

Every positive number is either composite or prime or unit (1).

What are natural numbers?

• Natural numbers are those numbers that are used for counting.
• It contains all the positive integers.
• Examples: 1, 2, 3, …

What are prime numbers?

• A prime number is a natural number greater than one which is not a product of two smaller natural numbers.
• A prime number is a positive integer that has only two divisors: 1 and itself.
• Please note that Prime Numbers ⊂ Natural Numbers.
• Examples: 2, 3, 5, 7, …

What are composite numbers?

• A composite number is a positive integer that can be formed by multiplying two smaller positive integers.
• A composite number is a positive integer that has at least one divisor other than 1 and itself.
• Please note that Composite Numbers ⊂ Natural Numbers.
• Examples: 4, 6, 8, …

What does it mean by the term “measured by”?

When we say that b measures a, then it means that a is divisible by b. In other words, we can say that the result of a/b is an integer. To put it in a different way, we can also say that if a is measured by b, then a is divisible by b.

Examples:

• 2 measures 6.
• 3 measures 9.
• 16 measures 64.

An Important Definition:

A composite number is that which is measured by some number.

Unstated Principle Used:

Any decreasing sequence of numbers is finite.

Now, let us get started with the proposition and its proof.

Proposition:

Any composite number is measured by some prime number.

Goal:

Our goal is to prove the proposition that says that any composite number is measured by some prime number.

Proof:

• In this proof, we are representing each number as a straight line. The length of the line represents its value. The longer the line, the higher the number.
• Let A be a composite number.

• The goal is to prove that A is measured by some prime number.
• From the definition, we can say that since A is a composite number then some number B measures it. Since B is measuring A, it is obvious that B≤A. For now, ignore the case when B=A. So, that leaves us with the condition B<A.
• In this proof, we are ignoring the case when B=A. The reason behind it is that if B=A then A/B will give us 1. But, at this point, 1 is of no use to us in the derivation of the proposition because it is neither a composite number nor a prime number.
• In short, for the next number, we are only considering the numbers which are strictly less than the current number.

• Now, if B is a prime number then our proposition is proven.
• But, if B is a composite number then some number C measures it. Here, C<B<A.

• Now, note that since C measures B and B measures A, we can say that C measures A.
• Next, if C is prime then our proposition is proven.
• But, if C is a composite number then some number measures it.
• Here, note that C<B<A. Each generated number is strictly less than the current number. For example, if the next number is D then D<C<B<A.

• Now, this investigation is continued this way, then some prime number will be found which measure the number before it, which will also measure A.
• If a prime number is not found then an infinite sequence of numbers measures the number A, each of which is less than the others, which is impossible in numbers because any decreasing sequence of numbers is always finite. Here we are having a decreasing sequence of natural numbers (1, 2, 3, …).
• Also, note that the minimum possible value for prime numbers (2) is less than the minimum possible value for composite numbers (4). So, while we keep on decreasing the number, we will always find a prime number that measures the composite number.
  For example, if we get the composite number (4) then there is a prime number (2) that measures it.

The whole process can be understood by the following diagram.

We hope you loved reading this proof and learned something new from it. If you have any suggestions or questions, please feel free to add a comment. Happy Learning!

References:

1. http://aleph0.clarku.edu/~djoyce/java/elements/elements.html
2. http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII31.html
3. http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/defVII11.html

Understanding Proofs by Euclid — 101 was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Join thousands of data leaders on the AI newsletter. It’s free, we don’t spam, and we never share your email address. Keep up to date with the latest work in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI