Posts Tagged ‘prime numbers’

The Fundamental Theorem of Arithmetic

1 Comment

It is not uncommon to hear operations on numbers, even the computations carried out in modern computers, as “mere arithmetic.” But arithmetic is hardly simple or obvious when one gets down to the fundamentals and realizes the structure that must be present in our number system in order for it to work they way we intuitively think it should work. Thus, today we consider the Fundamental Theorem of Arithmetic.

Every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes.

Thus every integer has a canonical representation as a product of powers of primes:

where p1 < p2 < … < pk are primes and the αi are positive integers; 1 is represented by the empty product. As example 12 = 22 × 3, and 666 = 2 × 32 × 37. Fairly familiar stuff for anyone who paid attention during grade school and secondary school math classes. But the theorem itself is not self-evident, it is something that had to be proven true in order for our everyday arithmetic to hold. A good article on why the theorem is not obvious can be found here. It also has implications beyond the natural numbers. If we extend the canonical representation to allow both positive and negative values for ai, we get the set of positive rational numbers (fractions), for which the theorem still holds. It can also be generalized to more exotic constructions, such as Gaussian Integers. Gaussian integers, often denoted ℤ[i] are complex numbers a + bi where i is the square root of -1, and a and b are integers. It can be shown that the fundamental theorem of arithmetic holds for Gaussian integers, and that there is a definite set of “Gaussian primes” just as there are prime numbers. But while plotting the prime numbers and looking for visual patterns is an exercise in frustration, the rotational nature of complex numbers (which we have discussed in a previous article) causes the Gaussian primes to fall into a visually interesting radial pattern:

With all the important and sometimes confounding properties of primes, having ways to visualize them is always intriguing.

Any mathematical construct (specifically, a “domain”) that obeys the fundamental theorem of arithmetic is known as a Euclidean Domain. (Note that this has very little to do with Euclidean spaces or the other uses of the term in geometry.) We can observe many more Euclidean domains, such as generalizing Guassian integers to other roots of 1. If we use the cube roots of 1, for example (yes, 1 has three cube roots), we get the set of Eisenstein Integers: numbers of the form a + bω, where a and b are integers and:

Like Gaussian primes, Eisenstein primes have a distinctive radial pattern when viewed on the complex plane. Whereas Guassian primes divide into quadrants, Eisenstein primes form a hexagonal pattern.

Note that while the generalization works for square roots of -1, cube roots of 1, etc., it doesn’t necessarily work for all roots of 1. Some of those sets will not form Euclidean domains.

We can also look beyond numbers to other mathematical entities that form Euclidean domains. One such example can be found in knot theory, which we discussed in an article a few years ago. Knots can be expressed as unique combinations of prime knots:

From here we can consider the implications for music of the Euclidean domains, the accompanying Euclidean algorithm for computing greatest common divisors in any of these domains. But that will be left as an exercise for another day.

RedditPinterestShare
Tags: , , , , , , , , ,

Fun with the Arithmetic Derivative and Twin Primes

1 Comment

Anyone who has stayed in math classes long enough to reach calculus quickly comes to believe that calculus is more advanced and complex than arithmetic. And while that may be true for the most intuitive aspects of arithmetic that we learn in grade school, the seemingly innocent discipline quickly becomes more mysterious as one advances into it.

Consider the most basic operation in calculus, the derivative. The derivative of the a function is said to describe the instantaneous rate of change of function (how fast it is going up or down in any given direction), or alternatively the slope of a function at any given point. However, there is a related operation on integers is called the arithmetic derivative, defined as follows:

  1. p’ = 1 for any prime number p
  2. (ab)’ = a’b + ab’ for any a,b ∈ ℕ
  3. 1′ = 0
  4. 0′ = 0

While there is an intuitive and even “visual” nature to the calculus derivative, the arithmetic derivative seems more abstract and opaque. Additionally, the former is about continuous functions, while the latter is about discrete entities such as integers or rational numbers. The main thing the two concepts have in common is that they obey the Liebniz Rule governing the products of derivatives, as described on line 2 above.

So can the arithmetic derivative tell us anything useful about integers? It is intimately tied to prime numbers and prime factorization, so it is in that sense an additional tool for examining fundamental properties of numbers as they relate to primes and patterns of primes. The article Deriving the Structure of Numbers quotes Linda Westrick, who has studied the arithmetic derivative and says that it “provides a different context from which to view many topics of number theory, especially those concerning prime numbers. The complex patterns which arise from its simple definition make it interesting and worthy of study.” To see such patterns, one can apply the derivative repeatedly, n’, (n’)’, etc., just as one would in calculus, to chart the variations even among the first few natural numbers.

n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n
0
1
1
4
1
5
1
12
6
7
1
16
1
9
8
32
1
21
n"
0
0
0
4
0
1
0
16
5
1
0
32
0
6
12
80
0
10
n"’
0
0
0
4
0
0
0
32
1
0
0
80
0
5
16
176
0
7

Indeed the interesting patterns include the fact that some numbers quickly go to zero as one repeatedly applies the arithmetic derivative, as on the case of 6′ = 5, 6” = 1, 6”’ = 0. Other numbers, seem to increase without bound. In the above chart, for example, powers of 2 appear to grow quite quickly. Yet others bounce around unpredictably somewhere in between. In many ways, this reminds me a bit of the Collatz Conjecture which have discussed on CatSynth in the past.

Perhaps the most intriguing property of the arithmetic derivative is its relation to twin primes, pairs of prime numbers whose difference is 2, like 11 and 13 or 29 and 31. It is conjectured that there are infinitely many such pairs of twin primes, but no one has ever proven this. However, it turns out that twin primes are related to the second derivative of a number n”. So if there are infinitely many numbers n for which n” = 1, then there are infinitely many twin primes. As described in this paper by Victor Ufnarovsk, one can derive this from the following theorem:

Let p be a prime and a = p+2. Then 2p is a solution for the equation n’ = a

The proof is relatively straightforward:
(2p)’ = 2′p + 2p’ = p + 2

So if 2p’ = p + 2 and p + 2 is also prime, as would be the case for twin primes, then 2p” = (p + 2)’ = 1.

Unfortunately, this does not answer the question of whether there are infinitely many such pairs. So the famous problem remains open.

RedditPinterestShare
Tags: , , ,

11:11 on 11/11/11

3 Comments

At 11:11 on this day 11/11/11, I snapped screenshots of both the iPad and iPhone featuring Luna.

Of course, the symmetry and homogeneity of the date and time is quite attractive, and unique (at least within a given century). The number 111111 is also interesting when you decompose it into primes:

111111 = 11 * 13 * 3 * 37 * 7

I find the prime factorization quite poetic.

We can also factor the date and time together (11:11:11 on 11/11/11):

111111111111 = 11 * 13 * 3 * 37 * 7 * 101 * 9901

Note quite as poetic as the previous example, but still interesting. In particular, 9901 is interesting as the greatest prime factor for any repeating series of 12 numbers. Other related properties can be seen at the site Prime Curios.

RedditPinterestShare
Tags: , , , , , , , , , ,

Calculus for Cats and Prime Number Theorem

4 Comments

<I was looking for a quick way to combine cats and mathematics this morning, and came across the book Calculus for Cats.

This is a book for people about to take calculus, and for survivors of calculus who still wonder what it was all about. It gently explains the basic concepts and vocabulary without making the reader ever do a single problem.

Basically, the book draws (quite literally) an analogy between the fluid motion of cats at play (or in pursuit of “prey”) and the concepts and techniques of calculus, which focuses on continuous functions.

We at CatSynth remember calculus fondly as a mathematical pursuit. But number theory is more my thing. Calculus primary concerns itself with continuous functions of real and complex numbers, while number theory deals with discrete entities, like integers. But in mathematics, all things are interconnected. For example, we demonstrated the connection between the gamma function, pi and factorials, combining continuous and discrete concepts.

Consider the function π(x), the prime-counting function. It's a bit unfortunate they chose the symbol π, but it is what it is. Basically, this function counts the number of primes less than or equal to a particular number. For example π(20) would be all the prime numbers less than 20: 2, 3, 5, 7, 11, 13, 17 and 19. So π(20) = 8.

So to calculate π(1000) would one have to literally count all the prime numbers less than 1000, including figuring out which numbers are prime? And what about π(1000000)? Unfortunately, the answer is yes. But there are good ways to approximate the number of primes, using the results of the Prime Number Theorem. Those interested in the formal theorem are encouraged to follow the link, but we will skip ahead to one of the interesting results. One of basic functions to come out of calculus is the natural logarithm ln(x), whose base is the famous constant e. If you don't know about it, go look it up. Otherwise, the rest of this article will not make much sense. One can use ln(x) to build more complicated functions in calculus, one of which is the offset logarithmic integral, or Li(x):

This is one of those functions, like the gamma function, that cannot be expressed without the use of calculus. Turns out, however, that it is a good approximately for π(x), which is very much a discrete concept and quite distant from the continuous motions involved in calculus. The prime number theorem provides the connection.

This article is included in Carnival of Mathematics #31 at recursivity.

RedditPinterestShare
Tags: , , , , ,