Transcript prime numbers - norsemathology.org

PRIME NUMBERS
History, theories and applications
By Kim Wojtowicz
Definition of a Prime Number
• A Prime number is a number that has exactly
2 Distinct factors: itself and 1.
• Smallest prime number is 2, it is also the only
even prime number.
Is 1 a Prime number?
• There is argument and controversy about 1 being Prime.
• Professor Ian Mallett states: DOES GOD THINK 1 Is Prime
• Does God think that the number 1 is a prime number? A good question,
which can be answered with just four basic responses.
• 1. Yes!
• 2. No! 1 is a separate and special entity called ‘Unity’. It is neither a prime
nor a composite number. The first prime number is 2.
• 3a. It doesn’t matter, it’s just a question of definition.
• 3b. It doesn’t matter, I don’t believe in God.
• 4. What is a prime number?
• In whatever category your reply falls, I’m sure you will benefit from
reading this article so welcome to the site!
• http://www.fivedoves.com/revdrnatch/Does_God_think_1_is_prime.htm
Dr. Mallet’s argument:
Prime numbers are far more important than composite numbers in the
worlds of mathematics, the sciences, cryptography etc. Mathematicians,
mistakenly in my view, often refer to prime numbers as being the
building bricks of all numbers. The act of building is an additive process
rather than a multiplicative one. You can’t build a wall and then multiply
that wall by four to make a house. You just have to keep building, adding
one brick at a time, until the house is completed. The building brick of all
numbers therefore is the number 1. The number 1 is the brick that builds
the number n, where each value of n is equal to the number ‘bricks’
required. The number 10 requires 10 bricks or 10 1’s, 20 requires 20 1’s
etc. Nonetheless, great importance is assigned to the prime number
series. So why the confusion over their order numbers? Why isn’t there
universal agreement as to which is the first prime? Surely this issue is at
least equal to, and probably far more important than, the order number
of the composite numbers
Up until the beginning of the last century the general consensus was that 1 is
prime, with just a few detractors. The French mathematician Henri Lebesgue
was emphatic on this issue. The majority of mathematical textbooks in the 19th
and early 20th centuries gave 1 as prime. Even now, maths textbooks as late as
1995 or later show 1 as being the first prime. However, at the beginning of the
last century mathematicians began to see the number 1 as a special case,
isolating it from the primes and composites by calling it ‘unity’. It supposedly
made things more ‘convenient’, an expression which I loathe because
convenience doesn’t necessarily make a right and even now I still await an
example of this so called ‘convenience’. The main opposition to the 1 is prime
lobby is that it supposedly destroys that monolith of mathematics, the
Fundamental Theorem of Arithmetic which states that every natural number is
either prime or can be uniquely factored as a product of primes in a unique way
- hmm, unique! Well, in the first instance isn’t the number itself unique? Can
something be doubly unique? Of course not! Since the number itself is unique it
would be logical that its prime factorisation is different to that of any other
number. I don’t think it matters a lot whether or not this theorem is destroyed
but there is no need for it to be destroyed if 1 is considered prime. It all boils
down to definition again. By the insertion of just two words the theorem still
stands: the Fundamental Theorem of Arithmetic states that every natural
number is either prime or can be factored as a product of prime proper factors
in a unique way.
Dr. Mallet’s Conclusion
On a final note, how the idea that 1 is not prime destroys that beautiful Trinity
of the first three primes 1, 2 and 3. The only triad of primes which are linked
together, nothing in between, and the only primes whose order numbers are
equal to their values. Uniquely, the product of these three is equal to their
sum, i.e. 6, the 3rd triangle. This is the gematria of the Greek word ABBA
meaning Father or Daddy. The first three primes 1, 2 and 3 represent the Trinity
in terms of the order of the Father, Son and Holy Spirit.
Be not deceived dear reader, 1 is prime and God thinks so too!
Personal Note: from what we have learned, math and religion don’t mix.
History of Primes
Ishango bone: tool handle discovered around
1960 in the African area of Ishango, near Lake
Edward. It has been dated to about 9,000 BC and
was at first thought to have been a tally stick.
At one end of the bone is a piece of quartz for
writing, and the bone has a series of notches
carved in groups on three rows running the length
of the bone. The markings on two of these rows
each add to 60. The first row is consistent with a
number system based on 10, since the notches
are grouped as 20 + 1, 20 - 1, 10 + 1, and 10 - 1,
while the second row contains the prime numbers
between 10 and 20!
The Ishango bone is kept at the Royal Institute for
Natural Sciences of Belgium in Brussels.
Who had knowledge of Primes?
• Shown on Ishango bone
• Hints that Egyptians knew from the Rhind
Papyrus.
• Ancient chinese writings show some
knowledge
• Not much done with it till the Greeks circa
300BC.
Who has researched it? Eratoshenes
• http://www.together.in.th/fi
nd-prime-sequential-sievesalgorithm/
• http://www.youtube.com
/watch?v=0JHEqBLG650&
NR=1&feature=fvwp
• http://www.cafepress.com/+
mathematics_gifts_tshirts_or
ganic_mens_tshirt_,4126933
92
• http://www.youtube.com
/watch?v=3mrVyVBTYNc
&feature=related
• http://www.cafepress.com/+
eratosthenes_prime_guy_mu
g,185245290
Competition for Erosthenes
• Arthur Oliver Lonsdale Atkin (July 31, 1925 –
December 28, 2008), who published under the name
A. O. L. Atkin, was a Professor Emeritus of
mathematics at the University of Illinois at Chicago. As
an undergraduate during World War II, he worked at
Bletchley Park cracking German codes.[1] He received
his Ph.D. in 1952 from the University of Cambridge,
where he was one of John Littlewood's research
students.[2]
• Atkin, along with Noam Elkies, extended Schoof's
algorithm to create the Schoof–Elkies–Atkin algorithm
and, together with Daniel J. Bernstein, developed the
sieve of Atkin.
Sieve of Atkin
•
•
•
•
•
•
•
In the algorithm:
All remainders are modulo-sixty remainders (divide the number by sixty and return the remainder).
All numbers, including x and y, are whole numbers (positive integers).
Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite
marking.
Create a results list, filled with 2, 3, and 5.
Create a sieve list with an entry for each positive whole number; all entries of this list should initially be
marked nonprime.
For each entry number n in the sieve list, with modulo-sixty remainder r :
–
–
–
–
•
•
•
•
•
•
If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x2 + y2 = n.
If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n.
If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 − y2 = n when x > y.
If r is something else, ignore it completely.
Start with the lowest number in the sieve list.
Take the next number in the sieve list still marked prime.
Include the number in the results list.
Square the number and mark all multiples of that square as nonprime.
Repeat steps five through eight.
This results in numbers with an odd number of solutions to the corresponding equation being prime,
and an even number being nonprime.
Study/Theorems of Primes:
Just to name a few
• Fermat: infinitely many primes.
• Gauss:The problem of distinguishing prime
numbers from composite numbers and of
resolving the latter into their prime factors is
known to be one of the most important and
useful in arithmetic.
• Euclid:fundamental Theorem of Arithmetic
• Riemann: distribution of primes
• Goldbach: Every even number >2 can be
expressed as the sum of 2 primes.
Types of Primes
•
•
•
•
Twin Primes: primes differ by 2
Mersinne Primes: descibe Mn = 2 ^ ( n) -1
Fermat Primes: Fn = 2^ (2n) + 1
Prime Quadruplet: A prime constellation of four
successive primes with minimal distance . The term
was coined by Paul Stäckel (1892-1919
Wieferich primes: prime p such that p squared divides
2^ ( p-1) -1
Wall-Sun-Sun Primes: if p squared divides F(p-p/5)
• Wilson Prime: p squared divides ( p-1)!
Prime Calculators
• http://primes.utm.edu/curios/includes/primet
est.php
• http://www.amblesideprimary.com/amblewe
b/primenumber/primecheck.htm
• Many others found on the internet
Largest known Prime
• In 2008 the largest known prime to date was
found.
• http://primes.utm.edu/notes/by_year.html
• Prime of record size:
• http://primes.utm.edu/notes/1257787.html
Uses/applications of Primes
• http://www.odec.ca/projects/2007/fras7j2/uses.
htm Used for cryptography /insects
• http://math.dartmouth.edu/~carlp/PDF/extraterr
estrial.pdf finding extraterrestrials
• What is the best use of primes?
• http://answers.yahoo.com/question/index?qid=2
0090213173906AAgAYxy
Music of the Primes
Olivier Messiaen, a famous composer found a great use
for prime numbers in his music:
Messiaen used both a 17 and 29 sequence in his piece of music
Quartet for the End of Time. Both motifs start at the same time,
however,
since they are both prime numbers, the same sequence of notes playing
together from each sequence wont be the same until they have played
through 17 x 29 times each. He held prime numbers very close to his
heart and believed they gave his music a timelessness quality.
Primes In Nature
Similarly, the cicada, a burrowing insect
owes its survival to prime numbers and their
properties. The cicada lives underground for 17
years, making no sound or showing any signs for
this amount of time. After 17 years, all of the insects
appear in the forest for just six weeks to mate before
dying out.
Uses: Code Breaking
• Prime numbers assist us in internet banking,
shopping and general interaction on the
internet. It encodes the messages.
• Ex: RSA calculator:
http://www.cs.drexel.edu/~jpopyack/IntroCS/
HW/RSAWorksheet.html
Prime Numbers In Code Breaking
To encode a message…
If we want to send the message “HELLO” we simply convert it into a
string of numbers:
0805121216
(A=01, B=02… etc.)
We can then raise that number to a publicly announced power, divide it
by another number which has again been publicly announced and we
will be left with a remainder. This is our encoded message…
Prime Numbers In Code Breaking
To decode this message…
The person who received the coded string of numbers
would raise that number to another power which
would only be known to them. They then divide it
again by the number publicly announced earlier and
the remainder from that would be the string of
numbers that break down to say “HELLO”!
Prime Numbers In Code Breaking
For Example…
Let our message be “E”. “E” is converted to 05, and is then
raised to the 7th power . Our number is now 78,125. We divide
that number by 33 to give 2367 with a remainder of 14.
14 is our encoded message.
Prime Numbers In Code Breaking
Now, to decode…
We raise 14 to the 3rd power to give 2744. We divide
that number by 33 which gives 83 with a remainder of
5…
5 is our decoded message and converts to “E”, the
original message.
Fun time!
• Now if time, a little fun with Relatively
primes?
Prime Number excercise
• You take all people from a group, or all your
class students and put them in a circle.
• Then count the number of students and pick a
number “RELATIVELY PRIME to it” meaning
that both numbers don’t have to be prime,
they just need to share NO Factors
Game continued
• Example: lets say we have 20 students, and you pick
the number 3. You give a Tennis ball to student 1 and
they throw the ball around to every 3rd person. It will
Take 3 rotations, but in these 3 rotations the ball will
come to each student 3 times, touching them all just
once and then returning to where it started.
• You make it tougher by adding a new tennis ball to the
circle everytime the ball passes to the 3rd person start
another ball going. 20 people should be able to handle
9 tennis balls (( # people/2 ) – 1)
On paper.
• You can do the same designs on paper as the
game. Using a ruler, compass and carefully
spacing out the dots connect them and create
spirals and other designs. You will see as the
two numbers get closer the angles shrink and
the picture narrow. For our example to 20 you
could use 20/3 and 20/7 and 20/9 .
On paper
• On paper it gives wonderful designs for 2
number not relatively prime. For example
pick 20/2 you will get 2 decagons that
intertwine. 20/5 will give you 5 intertwining
squares while 20/4 will give 4 intertwining
decagons.
• Formula ( points / n where points and n are
not relatively prime) gives n intertwining
shapes of sides (point/n).
Resources
1) Does god think 1 is prime:
http://www.fivedoves.com/revdrnatch/Does_God_think
_1_is_prime.htm
2) Internet encyclopedia of science:
http://www.daviddarling.info/encyclopedia/P/primenum
ber.html
3) RSA encryption calculator:
http://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAW
orksheet.html
4) Wikipedia:
http://en.wikipedia.org/wiki/Prime_numbers
5) Prime curious:
http://primes.utm.edu/curios/includes/primetest.php