Operations with Prime Factorization

In a previous post I discussed the advantages and disadvantages of using decimal notation when performing certain operations on numbers. Let's look at four operations and at how well decimal notation and prime factorization do with them.

The operations will be: addition, multiplication, maximum, and least common multiple.

I left off subtraction, division, minimum, and greatest common multiple because they will behave similarly to their counterparts above. In case you are wondering, I take max(a, b) to be the largest of numbers a and b, and lcm(a, b) to be the least common multiple. Performing the "max" function can be equivalent to comparing the 2 numbers.

Here's how the notations pan out:

Addition - We have a simple alogithm for addition in decimal notation. In factorized notation, addition does not seem possible. The best way to add 2 numbers in factorized notation is to convert them to decimal notation.

Multiplication - In decimal notation, we have a good algorithm for it, but it is more complex than the addition algorithm. In factorized notation, it is very easy: just add the exponents.



24 x 50 = 1200

Maximum - This is easy in decimal notation. In factorized notation, comparisons don't seem possible. The best way to compare seems to be just to convert the numbers back into decimal.

Least Common Multiple - In decimal notation, this is tough, and it usually done through tables of multiples and searching for commonality. In most cases, we're bettor off converting to factorized notation first. In factorized notation, we get the least common multiple simply by taking the maximum of each exponent.





So of these four, we found two that work well with decimal notation (addition, maximum) and two that work well with factorized notation (multiplication, least common multiple).

There is an even deeper observation here. In factorized notation, the exponents are actually written in decimal. When we perform an operation on the exponents, this corresponds to a different operation on the factorized numbers.

For example, take addition, an operation that's easy to do on decimal numbers. When the exponents of a factorized number are added, we have performed a corresponding operation on the numbers themselves, in this case multiplication. In fact, many operations have this relationship. Here is a table of it:

operation performed on the exponents - operation performed on the factorized number
addition - multiplication
subtraction - division
maximum - least common multiple
minimum - greatest common factor
is x greater than y - is x divisible by y
is x less than y - does x divide y

Yes, to find the greatest common factor of two numbers, all you need to do is factorized, and take the minimum of the exponents. And to find out if one number divides another, check that all the exponents in the factorized form are smaller.

This is all nice to know, but the fact remains that doing place-value-easy operations on factorized numbers is a pain in the neck, and it's very difficult to prove any conjecture about them. A conjecture like - for example - the twin primes conjecture. Primes exist and manipulate in the factorized realm. The twin prime conjecture is asking when they differ by two, and subtraction is in the place-value realm.

Defining Universal Sets

We've already defined whole numbers casually by {0, 1, 2, ...} and formally using Peano's Axioms. Let's analyze the Peano Axioms and understand why they work.

Set theory isn't something that came naturally in mathematics. The general idea comes naturally to us, of course, but it's so difficult to actually formalize that it wasn't done until Georg Cantor's work in the 19th century. Even then, there were problems. Bertrand Russell found a paradox in "naive set theory" in 1901, and even still inconsistencies may exist. Today, much work has been done in axiomatic set theory. I'm not going to get in to these axioms, but I will talk about how I like to define sets.

Most sets that we think of, such as {1, 4, 5} are subsets of some universe. In this case, the universe can be whole numbers, or it can be integers or reals. Defining these subsets isn't hard, it's defining the universal sets that proves tricky. Once you have the universal set, subsets can be defined using some rule that separates values in the subset from values outside the subset.

So how do we define these universal sets? My ideas on this have been shaped by ideas in computer science, which looks at data structures and functions. The way I tend to look at it, there are 3 ingredients that define U.

1) Constructors. These are functions that accept as input members of various other well-defined sets and possibly U as well, and use these inputs to construct a value in U.

2) Induction Rules. Suppose that X is a subset of U. We need a way to prove or disprove that X contains all of U.

3) Equality Rules. We need to know which members of the set are equal to one another. If we do not know this, we cannot know the precise structure of the set. How do we know that our definition of equality is legit? It needs to be defined for all values on U, which we can prove using our induction rules, and it must also satisfy the 3 properties of equivalence relations. That is,
Reflection: a = a
Symmetry: a = b implies b = a
Transition: if a = b and b = c then a = c.

Once these 3 rules are defined, we have a functioning universal set.

Notations: Formalizing Place-Value

Notation matters.

In my last post I called prime factorization a "notation" for the natural numbers. It is a formal way of representing them. Mathematically speaking, a notation is just a correspondence between 2 sets: the notation set, and the objective set. Every member of the objective set has a corresponding notation.

For example, take place-value notation, which is a notation for all whole numbers including zero. The whole numbers are defined one way, and they are the objective set. The place-value notation is defined another, and let's call it the notation set. We can place a correspondence between the two, which is just an "onto" function from the notation set to the objective set.

First, let's define the set of whole numbers using the following 5 rules. These 5 rules are a derivation of Peano's Axioms for Whole Numbers.

0 is a whole number.


For every whole number n, there is a whole number n', the increment of n.

Let X be a subset of the whole numbers. If 0 is in X and for every n in X, n' is also in X, then X contains all whole numbers. This is the principle of mathematical induction.

Equality:
For all whole numbers n, the increment n' is not equal to 0.


For all whole numbers n and m, n' = m' implies that n = m.

Using the principle of mathematical induction, these 2 rules for equality sufficiently define equality on all whole numbers. With these 5 rules, we can prove everything that we know about whole numbers. This includes the rules for addition, subtraction, multiplication, division, as well as the properties of prime numbers and number theory. They will also be the basis for one day proving or disproving the twin prime conjecture.

Now that the whole numbers have been straightened out, we'll take a look at our place-value notation. In this version of place-value, zero is represented not by 0, but by [], the empty list of digits, and 12:3 is equivalent to 123, just so that we have some notation for meaning "append onto".

Let D be the set of digits in this place value system, and for arguments sake let it contain 10 digits, with a correspondence to the first 10 whole numbers. This correspondence will be mapped by the function f.


f(0) = 0
f(1) = 0'
f(2) = 0''
...
f(9) = 0'''''''''

Of course, we can let this contain d digits and make this more general. I wrote down some basic rules for place-value notation.

[] is in the place-value notation.


For every value n in the place-value notation, n:d is also in the place-value notation, where d is a digit.

Let X be a subset of the place-value notation. If [] is in X and for every n in X and every digit d, n:d is also in X, then X contains all of the place-value notation.

Equality:

For all place-value n and digit d, n:d is equal to [] if and only if n=[] and d=0.

For all place-values and and digits and .


Now that place-value notation has been defined, with 5 rules that look strikingly similar to the 5 rules of whole numbers, we may define a correspondence between the 2. Every place-value gets mapped to a whole number. We'll call this function g.


g([]) = 0
g(n:d) = 10*g(n) + f(d)

First of all, note that this function is now properly defined for everything in the place value notation because of its version of the induction principle. Furthermore, and this would require a formal proof, we can show that equal inputs produces equal outputs.

The multiplication and addition operators on whole numbers can be defined on whole numbers using the axioms we have, even though I haven't done it explicitly here.

Now in order to prove that the function g specifies a notation (that is, it's onto), we need to show that for each whole numbers n, there exists some place value m such that g(m) = n.

Once that is proven (and it can be) then place-value notation can be used as a substitute for W and in fact we can write whole numbers using place-value notation and not have to worry about converting between the two because we know that there is a correspondance.

Prime Factorization

When dealing with the natural numbers, we often want to factorize them. That is, find numbers that multiply to the original number. A composite number is a number that can be decomposed through factoring.

For example, 6 is a composite number. It can be rewritten as 2 x 3. The number 7, on the other hand, is not composite. The only natural numbers that multiply to 7 are 1 and 7. Because there is still a 7 in the product, we have not decomposed it into smaller numbers.

The number 7 is a prime number. A prime number is a natural number that is divisible by only 2 distinct numbers: itself and 1. Prime numbers are not composite. Every natural number is either prime or composite, except for 1, which is neither.

There are an infinite number of prime numbers. This is an important fact given the goal of this blog, so later on I'm going to describe some of the proofs of this. For reference, all of the primes less than 50 are listed below.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

Because the primes form an infinite sequence, we can index them. For example, lets let denote the prime number for all .

In other words , , , , etc.

We can form a new notation for numbers out of this. There's a theorem that let's us do that, and it's called the fundamental theorem of arithmetic, or FTA. This theorem states that all natural numbers can be uniquely factorized into prime numbers. Let's look at some examples.

The number 12 can be factorized into 2 x 2 x 3, which are all prime numbers. No other number has the same factorization. This can be written compactly using exponents.



Now consider the number 490.



This example showcases rules that we'll need for writing numbers in factorized form. I have included the "3" term, even though it appears zero times in the product 2 x 5 x 7 x 7 = 490. The zero term serves as a placeholder, just as the decimal number 304 also requires a placeholder. I don't include a term for the prime number 11, because a leading zero would be superfluous, just as we don't normally write 032.

For the record, terms like are equal to 1, so they don't affect the product at all. 1 is written as the null product (no prime numbers multiplied together). There is no way of writing zero in this form. Therefore, it is a notation for natural numbers (which doesn't include zero) and not for whole numbers.

In the next few posts, I'm going to discuss this notation in more depth using more symbolic notation and mathematical language, and then go further into what this notation is good for.

Place-Value Notation: Some Pros and Cons

Just so there will be no confusion, I'm going to say that the set of whole numbers (represented by W) contains zero. The natural numbers or counting numbers (represented by N) do not contain zero. As far as I know, definitions vary and there is no agreed upon standard, so this is just my personal preference:

It's convenient that every whole number can be represented as a finite sequence of digits. For example, the number 123 is represented in decimal as - well - '1', '2', and '3' in that order. Each representation is unique. When I write 123, it's entirely clear to which number I refer. Likewise, there is no alternate way of writing 123, so long as we disqualify 0123 for its leading zero.

We've all been working with place-value notation our entire lives, so we may forget why it's so useful. Think about the most common operations that you perform on whole numbers:

Comparison
Addition
Subtraction
Multiplication
Division

Three of these operations can be carried out very simply with place-value notation. When performing addition, subtraction, or comparisons on paper, we only need to look at each column of digits once.

This is so efficient that computers and electronic systems perform these operations similarly to the way we do them by hand. Granted, they are using a base-2 system where the only possible digits are 0 and 1, but it is nonetheless a place-value numbering system.

Multiplication and Division are a little bit more difficult to do, but still manageable. In the multiplication algorithm , each digit must be multiplied with every digit of the other number. This is fundamentally more complex than addition.

Imaging trying to perform these operations with Roman numerals. If those hadn't been replaced with a place-value system (base 10 or otherwise), western civilization could not have advanced technologically as much as it has.

One thing about mathematics is that notation matters. If your concrete representation of abstract concepts does not mesh well with the operations you'd like to perform on those objects, not only will your calculations be slower, but you may overlook techniques that in an alternate notation are plainly obvious.

Believe it or not, some operations are actually quite difficult to perform with our place-value system. Consider the following operations.

Finding the least common multiple of 2 numbers
Finding the greatest common factor of 2 numbers

How are we supposed to find these values? Trial and error is a painfully slow technique. In fact, it is "exponentially" more difficult than addition.

Fortunately, there's another numbering system for the natural numbers only - prime factorization - in which these operations can be performed very quickly. Multiplication and division can also be performed more rapidly in factorized form.

What's more startling is that addition, subtraction, and comparisons, which are so simple in place-value notation, become utterly impossible with factorized numbers.

We'll look into this mysterious notation in the next post.

Why we learn Fractions

We teach fractions at the elementary school level, and it is probably one of the more complex concepts that we expect kids to learn.

There's good reason for this. Without a working knowledge of fractions, higher math becomes impossible. Algebra, geometry, trigonometry, and calculus can only be learned on a solid foundation that includes the ability to understand and manipulate fractions. Students who have gaps in their knowledge of fractions will have tremendous difficulty later on.

Fractions are also very useful. Most quantities are easiest to express as fractions. We often want to convert these to decimals or to scientific notation in order to make it easier to analyze data, but the quantities still start as fractions. I would consider decimal notation to be a higher-level form that can only be understood by those who understand fractions first.

Why is this relevant to us? It's because the study of fractions is where we get our first look at prime numbers. It's still the main reason we study prime numbers, and without them, prime numbers would be a curiosities only studied in higher institutions of learning. Instead, prime numbers are a part of a fundamental education in mathematics that everyone should have.

In the next few blog posts, in order to build up an extensive archive we can draw from later, we shall explore the link between fractions and prime numbers in detail.

Introduction and Purpose

Some may say that it takes audacity to create a blog whose main purpose is to solve the twin prime conjecture.

This may be especially true since I'm no expert in number theory. This problem is fascinating because it's so easy to understand and yet seemingly impossible to solve. Many great minds have worked on it, and modern mathematics still can't penetrate the mystery. All things considered, I think there may be some collateral benefits to be gained here before the final goal is met:

1) Unfortunately, many advanced texts on this subject are written by and for professional mathematicians and are inaccessible to the average person. I'd like to make this subject more accessible.

2) Many math texts go by a simple definition-theorem-proof formula. A rigorous approach is important, but in order to understand the subject and hopefully advance it, we have to take a step back and think about our setup. Why do we choose to define the way we do? Which proof strategy is most likely to work in a given situation? How are our theorems relevant to our overall goal?

3) Over time, this blog could become a useful resource for educators, researchers, and people with a general interest in number theory. Some blog posts will contain articles on different subjects that are relevant to the twin prime conjecture, but also fine as a stand-alone.

4) I don't think there have been many attempts to solve complex math problems using web 2.0 techniques. Because information is being exchanged more rapidly and through more people, we may be able to make progress where twentieth century mathematicians got stuck.

5) This can also be a forum for discussion on the history and philosophy behind this problem. The more we know, the better.

Most of all, I'm a little surprised that the twin primes conjecture has not yet been proven and I'd like to see it get done. All we need to do is show that there are an infinite number of primes that differ by 2. How hard can that be?

We're at 2300+ years and still waiting...