Category Archives: Primes

Congruent mod 4 primes

One of the last sections in our primes lab had to do with an interesting distribution of primes that are congruent to 1 and 3 mod 4. This means that our prime number, n, is congruent to either 1 (mod 4) or 3 (mod 4). We can divide these up into two sets of primes numbers:

$\pi_1(n)$= #{primes p| p $\leq$ n and p = 1 + 4k, for some positive integer k}

$\pi_3(n)$= #{primes p| p $\leq$ n and p = 3 + 4k, for some positive integer k}

So the question is, how many primes actually fit into these two sets?

 

n

$\pi(n)$

$\pi_1(n)$

$\pi_3(n)$

$\pi_1(n)$/$\pi(n)$

$\pi_3(n)$/$\pi(n)$

10

5

1

1

.2

.2

25

9

3

4

.33

.44

50

15

6

7

.4

.47

100

26

11

12

.42

.46

1000

168

80

86

.48

.51

10000

1229

609

618

.5

.5

100000

9592

4783

4807

.5

.5

As we can see, as our n approaches infinity, the two sets comprise together roughly 100% of the primes. There are some primes missing, as evidenced with n is small. 2 is a good example of one that doesn’t work with this relationship. But, as we can see, when n gets really large, the relationship holds really well.

Through this, we can make an extension of our very first proof, where we found that there are an infinite number of primes.

Let’s prove: If $\pi(n) \geq \pi_1(n) + \pi_3(n)$, then as n approaches infinity, $\pi_1$ and $\pi_3$ are infinite sets.

We already know that $\pi(n)$ is an infinite set, so our question is whether $\pi_1(n)$ and/or $\pi_3(n)$ are also infinite. As n approached infinity, $pi_1(n) \approx 0.5\pi(n)$, and $pi_3(n) \approx 0.5\pi(n)$. So, we can plug in our values: $\pi(n) \geq 0.5\pi(n) + 0.5\pi(n)$, and since $\pi(n)$ is an infinite sets, it is the sum of two infinite sets. So, as n approaches infinity, $\pi_1$ and $\pi_3$ also approach infinity, so they are also infinite sets. This is what we wanted to prove in the first place, so we are done.

The Sieve of Eratosthenes

Because there was a question in our first post about what a sieve is, it would be good to give a quick example of what a sieve is supposed to do, and what it looks like.

For the sake of an example, we are going to sieve all of the primes from 2-30, in other words we are going to separate the primes from the non-prime numbers in the set.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Let’s strikethrough all of the multiples of 2 greater than 2.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Now, let’s strikethrough all of the multiples of 3 greater than 3.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Now, you may be saying to me, but why didn’t you make 6, 12, 18…green too? Well, they’ve already been highlighted once in blue, so there’s no real reason to do more work than I have to.

 

So, let’s continue with 5.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

I’m going to continue going up using the non-crossed out numbers as a guide, and highlighting the multiples of those non-highlighted numbers.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Because I only chose to go up to 30, we are actually done. The non-crossed out numbers are our prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

 

So, here are some closing thoughts about the sieve “method” of finding primes:

Pro: Easy algorithm, an easy way to loop through a set of numbers to find the primes, easy to program by hand

Con: Can take a long time with larger numbers, eats memory in larger number sets.

 

And just for a thing to brighten your day, here is a poem that I found about the sieve on Wikipedia. I take no credit because it’s not mine, but I thought it was a fun way to think about the sieve method. More information can be found at the wikipedia page on the topic, including a very cool animation of the sieve from 2-120.

 

Sift the Two’s, and Sift the Three’s,

The Sieve of Eratosthenes.

When the multiples sublime,

The numbers that remain are prime.

 

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Previous Post: Prime-Generating Functions

Prime-Generating Functions

In the eighteenth century the supercomputers we have today which people can use to find prime numbers did not exist. Mathematicians have always sought to create order in a very chaotic world. Many people looked for a way to produce prime numbers. Is there a polynomial that when inputted with the set of all non-negative integers, would always produce distinct prime numbers?

In 1772 Euler discovered a polynomial whch produces primes from integers. This polynomial is x^2+x+41. After running this polynomial through Sage, we find that it does indeed produce distinct prime numbers but only for all integer values of x between 0 and 39. After that, the formula begins to degrade and not always produce prime numbers.

{41,43,47,53,61,71,83,97,113,131,151,173,197,223,251,281,313,347,383,421,461,503,547,593,641,691,743,797,853,911,971,1033,1097,1163,1231,1301,1373,1447,1523,1601}

If we then look at a second polynomial, x^2-79x+1601, and find its outputs with Sage, we find that it produces primes for all integer values between 0 and 79. Though, this polynomial simply outputs all primes that Euler’s original formula produced, twice each.

These quadratic polynomials both do pretty well. They both produce uninterrupted strings of primes of lengths 40 and 80, respectively. To show that there are polynomials that do a very poor job of this, we can look at x^2 + x + 2. The largest string of primes this produces for non negative integers is… 1, as it produces a 2 at x = 0, and nonprime numbers otherwise.

The fact is that there does not exist a polynomial with integer coefficients that always produces prime numbers. Their behavior is very difficult to predict. So although primes cannot be described with a polynomial, maybe there are other things we can learn about them by observing their distributions, another time.

Primes Lab
Primes Lab Introduction
Expanded Motivations and Definitions
The Sieve of Eratosthenes

Prime Numbers – Expanded Modivations and Definitions

The explanation of primes, and their importance to number theory by definition must be both explainable, and justifiable with words as mathematics is an extension of language. That extension is by way of the principle that mathematics consists of ideas that are not only consistent, they are also communicable. Our proof that shows that an transfinite number of primes exists, does so by method of substitution. The principle that an entire idea can be expressible in a single symbol. It is quite possible to reverse substitute all of the mathematical symbols for the language that defines each symbol. Though the proof would become exceedingly long.

Basis for all numbers, and by consequence the basis of Number Theory, stems from the principle that all numbers are products of primes. This is the definition of Prime Factorization. What prime factorization does for us is put the composites in terms of primes. Further, the Sieve method eliminates composite numbers by consequence of their not meeting the definition of prime. That definition being any number that has exactly two factors, one, and itself. By this definition all negative numbers are not prime because they contain the additional factor of negative one. A composite number would be any number that contains more than two factors. Such as four, for example, in that Four has the factors of one, two, and four.

For primes this is obvious by the given definition, but less so for composites. Each composite number essentially is an unfactored product of primes. Knowing this further helps us when we reach beyond the primes we know into the realm of higher primes. This is quintessential when we are working with things like the Euclid algorithm or the Sieve algorithm. At this point eliminating numbers that are not prime is the only real method we know to find primes, which returns us the the “basis for all numbers” hinted at earlier.

Previous: Prime Numbers: Lab 1
Next: Prime Numbers: The Sieve of Eratosthenes

Prime Number Lab: Post 1

Prime numbers are important to study because they are largely the basis for what we consider to be modern number theory. Understanding prime numbers and their distribution can help us solve problems in fields such as cryptology. Prime numbers have also been looked at since mathematics as we understand it came into being. So, by studying prime numbers, we are studying a vast history of research and theorems that mathematicians have discovered over the years.

We relate this motivation to process with an introduction into the process of finding primes, and move onto proving why we can find these primes by proving that the list of primes is infinite.
Our first observation begins with the Sieve method, which is the most basic method to find primes, but also the most computationally expensive as the numbers we work with get larger.
Euclid’s proof shows that the Sieve method can be used infinitely to find any number of primes we desire.

Euclid’s Proof of Infinite Primes:
Theorem: There are an infinite number of primes.

For the sake of argument, let’s let there be a finite number of primes, so n primes exist.

Let’s let M be an integer greater than 1. Like all integers greater than 1, it is either prime, or composite. Let’s let M be composite, so M is the product of primes. So, let M be the product of all the primes in our list. This means that M=p1*p2*p3*…*pn. What do we know about M+1? Well, it’s an integer greater than 1, so it’s either prime or composite. Let’s let M be prime. Then, either M+1 is a prime not on our list. Uh oh :(.

Now, let’s let M+1 be composite. This means that p|(M+1), where p is a prime from our list. But, that same p would also divide M. This is a contradiction because consecutive numbers are co-prime. This means that they cannot share a divisor greater than 1. So there must be a prime not on our list which divides M+1. So, there is at least one more prime that is not included in our list, so our list cannot be complete. Thus, the set of all primes is an infinite set, and there are an infinite number of primes.

To Next Post: Expanded Motivations and Definitions