Bezout's Identity

Theorem 3:  Bezout's Identity

Let $a$ and $b$ be nonzero integers with greatest common divisor $d$.  Then, there exists integers $x$ and $y$ such that $ax + by = d$.

Proof:

(1)  For integers $a,b$ let $S$ be a set that includes all $ax+by$ where $ax + by > 0$

(2)  The set is non-empty since it contains either $a$ or $-a$ where $y=0$ and $x=1$ or $x=-1$

(3)  By the Well-Ordering Principle, $S$ has a minimal element $as + bt$ and let $d = as+bt$

(4)  Using Euclid's Divsion Lemma, there exists $q_1, q_2, r_1, r_2$ such that:

• $a = q_1d + r_1$
• $b = q_2d + r_2$

(5)  It follows that:

• $r_1 = a - q_1d = a - q_1(as + bt) = a(1 - q_1s)  + b(-q_1t)$ which must equal $0$ since $r_1 < d$ but $d$ is the least element in $S$.  The same argument applies to $r_2$ so that $r_2 = 0$

(6)  Then, $d$ divides both $a$ and $b$.

(7)  Let $c$ be any common divisor of $a$ and $b$ such that $a =cu$ and $b = cv$

(8)  $d = as + bt = cus + cvt = c(us + vt)$ so that it follows that $c$ divides $d$ and further that $c \le d$

Euclid's Division Lemma

Theorem 2:  Euclid's Division Lemma

Given two integers $a$ and $b$ with $b \ne 0$, there exist unique integers $q$ and $r$ such that:

• $a = bq+r$
• $0 \le r < |b|$

Note:  Where $|b|$ is the absolute value of $b$.

Proof:

(1)  Case 1:  $a \ge 0$

(2)  Let $S$ be the set of all integers $a - bk$ where $k$ is an integer and $a - bk \ge 0$

(3)  $S$ is non-empty since either $a = a - b\times0 \ge 0$ which is in $S$

(4)  By the Well-Ordering Principle, there exists an integer $q$ such that $a - bq$ is the least element in $S$

(5)  Let $r = a - bq$.  $0 \le r$ by definition of $S$.  Further $r < b$ since if $r \ge b$, then it is not the least element since $r - b = a - bq - b = a - b(q+1) \ge 0$ would be less than $r$ and an element in $S$.

(6)  $r,q$ must be unique.  Assume that there exists $r', q'$ such that $a = qb + r = q'b + r'$  and $|r - r'| > 0$ and $|q - q'| > 0$.  Then, $b > |r - r'| = b|q - q'| > b$ which is impossible.

(7)  Case 2:  $a < 0$  In this case, let $a' = -a$.  It now follows that $a' \ge 0$ and there exists unique $r,q$.  It now follows that $a = -(bq +r) = b(-q) -r$  If $r > 0$, then $a = b(-q+1) + (b-r)$ with $0 < b-r < b$

Well-Ordering Principle

Theorem 1:  Well-Ordering Princple

Every non-empty set of non-negative integers contains a least element

Proof:

(1)  Assume that there exists a non-empty set $S$ of positive integers that does not contain a least element.

(2)  Let $P(n)$ be true if $n$ is an element of $S$

(3)  $P(0)$ is false.  If true, then $0$ would be the least element for $S$

(4)  Assume that for all $i \le n, P(i)$ is false. 

(5)  It follows that $P(n+1)$ is false.  If not, then $n+1$ would be the least element for $S$.

(6)  But, then by the Principle of Mathematical Induction, there is no positive integer in $S$

(7)  This contradicts our assumption in (1) that $S$ is non-empty.  Therefore, we can reject our assumption in step (1).

Note:  This is an example of a proof by contradiction.

Principle of Mathematical Induction

Axiom 1:  Principle of Mathematical Induction

A proof by induction consists of 2 steps:

(1)  Base Case:  Proves that the statement is true for one case independent of all other cases.

(2)  Inductive Case: Proves that if the statement holds for any case $n=k$, then it must also hold for $n=k+1$

The principle can be understood with the analogy of a ladder.  if we can climb on the bottom rung of a ladder and for each rung, we can climb to the next, then it follows that we can climb as high as we like up to the top of the ladder. 

This principle is very important in the establishment of advanced mathematical arguments.

The Prime Numbers

The Ancient Greeks loved to classify numbers.  Numbers that could be represented as the ratio of two whole numbers were rational numbers.  Numbers such as $\sqrt{2}$ which could not were irrational numbers.  A perfect number, such as 6,  is equal to the sum of its proper divisors.  Amicable numbers, such as 220 and 284, are pairs of numbers where each is the sum of the proper divisors of the other.

Without a doubt, the most important of these classifications was the concept of a prime number.  A prime number is any positive integer that has exactly two divisors.  $5$ is a prime number but $8$ is not.  $1$ is not, $0$ is not, and negative numbers are not.  While the definition is clear, one might immediately ask, why should one care.

There are two big reasons why we should care.  If mathematics is the study of patterns, some of the most amazing and surprising patterns relate to prime numbers.  Investigating prime numbers turns out to be a royal path to deep mathematical insights.  For example, one of the most important problems in mathematics today is the Reimann Hypothesis which concerns the relationship between prime numbers and the complex zeta function.  By the way, if anyone solves it, there's a million dollar prize waiting to be claimed.

The other reason to care about primes is that their properties have become fundamental to the very running of global eCommerce.   Prime numbers start out very common and become surprisingly rare as one starts to consider very large numbers.  It turns out that determining whether a number is prime can take a significant computation effort if the prime is large enough.  In fact, one of the great pursuits of spare computation capacity is the search for new primes.  Each time a new largest prime is discovered, it is worthy of a news headline.  For example, here is a news headline from NPR in 2018.

Because there are an infinite number of primes (more about that later) and because it is possible to find primes up to the limits of current computational power, they have become an excellent foundation for security.  Indeed, this is the foundation of public key encryption.  For example, RSA, one of the earliest public key encryptions is based on the difficulty of factoring the product of two large prime numbers.

But let's start smaller.  Let's focus on fundamental patterns.  For me, there are two incredibly surprising facts about primes that can serve as a starting point.  Of course, one or both may not be surprising to you.  First, each positive number is characterized by a unique combination of primes.

If I take any set of primes (for example $2,3,5$) at a specific power (for this example, we'll choose the power of $1$), then there is ONLY one number equal to their product.  In this case, $30$.  This property is called unique factorization.  The natural numbers are characterized by unique factorization.  If there is a prime that divides one but not the other number, they are not equal.  If there is a power of a prime that divides one but not the other,  they are not equal.    From this perspective, they provide an opportunity to simplify reasoning about very large numbers.  If I have two very complicated equations which I want to compare, I can quickly see that they are not equal if a prime divides one but does not the other.  For example, I can say without a doubt for all integer values of $x$ and $y$, the following will never be equal:

$$4^x \ne 7^y$$

I mentioned in a previous post that natural numbers are just one of many types of numbers.  One of the most surprising facts for me is that not all number systems are characterized by unique factorization.  In other words, there are numbers where they are products of different primes and yet they are still equal.  With our intuitions about the concept of number from the whole numbers and the integers, this may seem impossible.  If don't believe me, you can check it out for yourself.  For example, not all quadratic integers are characterized by unique factorization.  Even the great genius Leonhard Euler (pronounced Oiler) was not beyond making a bad assumption about unique factorization.  If you are interested, I provide the details of his mistake here.

Unique factorization is such as an important properties of integers that the theorem that establishes unique factorization is called the Fundamental Theorem of Arithmetic.

In my next blog post, I will walk through a simple proof of this fundamental theorem.

The Natural Numbers

A number, as a concept, is a surprisingly ambiguous term.  There are whole numbers, fractions, negative numbers, real numbers, irrational numbers, imaginary numbers, and transcendental numbers.  It may not be intuitively obvious what they all have in common.  There are also mathematical operations that are not defined and are probably not numbers at all such as $\dfrac{1}{0}$ (see here) or $0^0$ (see here).  The concept of infinity is another difficult to nail down concept.  Is it a number?  It turns out that there are different types of infinity.  For example, the number of counting numbers (1, 2, 3, ...) is less than the number of points in an infinitely divisible line (see here).  I will tackle these more advanced topics later

Historically, the concept of number began with the activities of counting and measuring.  Counting led to the whole numbers which did not include 0 at the very beginning and measuring led to simple fractions (more complicated fractions require a more complicated number system).  

The most important historical breakthroughs which we pretty much take for granted today are:

• Invention of number symbols  (typically, the earliest form of writing that comes after use of tally scratches and tally scratch groupings) (For context, see history of writing and history of ancient numeral systems)
• Discovery of zero (For context, see history of zero)
• Positional Notation which allows all numbers to be represented by a finite set of digits (For context, see here)
• Negative numbers (For context, see history of negative numbers)
• Irrational numbers which showed that not all measurements are ratios of whole numbers (For context, see history of irrational numbers)
• The Decimal System (For context, see here.  Not all societies used Base 10.  The Ancient Babylonians for example used a Sexagesimal System which is Base 60).

In mathematics, the set of positive whole numbers and zero is called the Natural Numbers and is represented by N;.    When combined with the set of negative numbers, it becomes the sets of Integers which is represented by Z. (Why Z, it comes from the German word Zahlen for 'numbers')

The study of the properties of Integers is called number theory and this will be the primary focus of this blog.    

In my view, the most surprising and deepest insight in all of mathematics is that natural numbers, despite their appearances of being the simplest of mathematical objects, contain some of the most challenging and important problems known to mathematics.  

These challenges have led to the development of public key cryptography which today powers the global economy.  Innovations such as block chain, which build on top of the complexity of mathematical problems, will further transform our economic, social, and political institutions that depend on hierarchy and centralized authority.  

One popular definition of Mathematics is "the study of patterns" (see here for an interesting overview).  Many of the most surprising and profound patterns can be found in Number Theory.

A Change In Direction

Starting today, I will update this blog on a regular basis.  I will use this blog as an exploration of the fundamental properties of primes as well as an attempt to generalize ideas.

If the past is any indication, my attempts will usually reflect a misunderstanding of a fundamental or a mistake in one step of my argument.  So, when I make my attempts, I will make sure to provide a thorough explanation of the mistakes that I made.

I will organize the blog posts as an attempt at a book.  So, as the blog proceeds, I will re-edit previous blog posts in the attempt to create a consistent narrative.  So, in theory, a person could start on the first blog post and proceed from there or start on what will become the table of contents and jump from there into any topic of interest.

I will start with very elementary ideas.  This will be a very personal journey.  So, I will proceed from the elementary ideas based on my interests and my attempt to generalize standard results.

I hope that others will find this interesting.  I warn everyone that while I am a serious amateur, I will make mistakes.  These blog posts will be primarily interesting to other amateurs.  For serious math students, I strongly recommend going to the blogs of professional mathematicians such as Terence Tao and Andrew Granville who are two of the most amazing writers and brilliant mathematicians.

Since I am an amateur, I will also make every effort to call out my sources and so that if my argument is unclear, it is possible to go to the source to find a professional explanation.

Most importantly, enjoy.  The journey is the purpose.  :-)