All about primes

All about primes

May 19, 2016.

First post on this blog, so I thought we would start it out with something interesting, like primes.

We include some JSFiddles so you can see all the code available with it!

So, lets start out with what they are.

What are primes?

Most of the time, you might get something like

A prime is any positive integer greater than one whose only postive divisors are 1 and itself

but I prefer to say that a prime is any integer that you can’t make by multiplying two other integers.

For example, 2 is the first prime, 3 is the next. 4 isn’t a prime, though, because 4 = 2 * 2, which means it has other divisors (2), and thus can be made my multiplying two other integers.

I’ve written a little JSFiddle so that you can see if a number is prime. This is a very unoptimized version of primality testing (testing if a number is prime), but you can see how a basic version works.

Full version at https://jsfiddle.net/CadeBrown/x9h5buwa/

This program takes the remainder dividing your input by all numbers less than it (actually, the square root of it, but that is a simple optimization), and if it is zero, that means the number is divisible by some other number, and is therefore not prime.

One common question is

Why isn’t 1 or 0 prime?

And this was a large argument for years. 1 and 0 are not considered prime for a few reasons. The first is the nice property that is called unique factorization, which states that any given integer has exactly one way to factor into primes. For example, 12 = 2 * 2 * 3, and you can’t get 12 from any other primes than 2, 2, and 3. If we said that 1 is a prime, we could have 12 = 2 * 2 * 3 and 12 = 2 * 2 * 3 * 1 . We have agreed that this is a nice property to have. 1 is what is called a unit. As is negative one, which brings us to our next question:

If 2 is a prime, then isn’t -2 ?

And the answer is: Sort of.

This is because -2 is similar to +2, one is multiplied by the unit 1, while the other is multiplied by the unit -1 . We only consider a number prime if it is positive, though.

Are there infinitely many primes?

Yes, there are. Primes get very far apart (however, there are infinitely many primes exactly 246 apart (https://www.quantamagazine.org/20141210-prime-gap-grows-after-decades-long-lull/))

I’ve written a little fiddle to graph how quickly the number of primes grows, and a few approximations to the actual line

Full version at https://jsfiddle.net/CadeBrown/cfg8bgLt/

History of Primes

Primes have been in people’s thoughts ever since hunter-gatherer days (They thought about dividing food up. How do you give out 13 orange to 3 people?).

Primes are something that are so tangible, like rearranging fruits to divvy up, but yet so mysterious, we don’t even know if there are infinitely many primes that differ by 2!

People have studied primes initially for dividing up resources, which is still useful today, but primes are also used in cutting edge technologies, such as cryptography. While I won’t get into cryptography in this post, suffice it to say that bigger primes are more secure to encrypt data and then decrypt it because the hacker in between doesn’t have the computing power to factor out large primes (which is a very computation-heavy task).

Currently, the largest known prime is $ 2^{74,207,281}-1 $ which is more than 22 million digits long!

The largest prime found by hand was $ 2^{127} - 1 $, or $ 170,141,183,460,469,231,731,687,303,715,884,105,727 $ Imagine doing that by hand!

Just think about that for a second. No two integers can be multiplied to get $ 2^{127} - 1 $, but $ 2^{127} $ is just 2 multiplied by itself 126 times!

Another reason I like that number is the fact that $ 2^{127} - 1 = 2^{2^{7} - 1} - 1 = 2^{2^{2^{3} - 1} - 1} - 1 = 2^{2^{2^{2^{2} - 1} - 1} - 1} - 1 $

Subscribe

Subscribe to this blog via RSS.

Categories

Math 4

Software 3

School 1

Pgs 2

Question 1

Music 1

Politics 1

Vietnam 1

Notes 1

Recent Posts

Popular Tags

Math (4) Software (3) School (1) Pgs (2) Question (1) Music (1) Politics (1) Vietnam (1) Notes (1)

About

We strive to create high quality, freedom respecting software and solutions.

Social Links

github

Our HQ

401 Henley St
23890, Tennessee
United States.