By the Power of Primes
Unraveling the world of Prime Numbers
I was looking into my son’s Book on Prime Numbers and realised it is me who needs the learning.. Never came across these beautiful snippets on Primes during my learning years.
Perhaps appreciation comes with maturity and life never ceases to throw opportunities.
Sieve of Eratosthenes
How do we generate Prime numbers? Eratosthenes proposed a very easy solution where we filter out all the composite numbers. What remains is prime numbers.
Basically list numbers till 100 and start eliminating multiples of 2, 3, 4… till 10.. Once we eliminate the composite numbers, the prime numbers remain.. Do watch this animation
The First Few Primes
2 -3- -5- 7 -11 -13 -17- 19 -23 -29- 31 -37- 41- 43 -47- 53- 59- 61 -67 -71–73- 79 -83- 89 -97
I was awed by this picture from Jain 108..
Primality Check
Well, How do we check for Prime Numbers?
Obviously we check for divisibility with prime numbers.. But till where? Till it’s square root.. Think about it.. 64 = 1*16, 2*32, 4*16, 8*8 and it repeats the other way after 8.. 16*4, 32*2, 16*1
Is 163 a Prime number? 13² = 169.. We check till 13 ie 2,3,5,7,11.. It has no factor, hence a prime number..
How about 161? It is divisible by 7 and hence not a prime..
Divisibility by Prime Numbers
I came across this very interesting divisibility video. Traditionally we have been learning different techniques for detecting divisibility by different numbers.. 3, 9,11, 4, 8 series to name a few. It gets complicated with 7, 13, 17.. This Vedic Math method called as osculation gives the Golden Master Lock for all prime numbers. How cool can that be..
https://www.youtube.com/watch?v=8kerLHgabMo
https://www.youtube.com/watch?v=hJhZcyoL1hE&feature=youtu.be
A Prime Reboot
My older son had this question a few years back.. Is p²-1 divisible by 24 given p > 3?.. At first it seemed my head needed a prime reboot.. I am an Engineering Grad and I stare at this elementary level question.. Then I realised .. It is just about breaking it up.. Give it a try..
(p + 1)(p -1).. Given that Primes numbers are even > 2, one of these had to be multiple of 2 and the other multiple of 4. There has to be a multiple of 3 in every 3 numbers and p itself cannot be that number as it is prime.. 2 * 4* 3 = 24..
Common Applications
It seemed to me initially that we do not use prime numbers in our regular world and perhaps it is for the mathematicians till it stuck that LCM, GCD is all about prime factorisation.. Any composite number can be prime factorised.. LCM or Least Common Multiple is all about picking up prime exponents to accomodate both numbers..
LCM(18, 12) => LCM(2*3², 2² *3) is 2²*3²= 36
Think of prime number 2 as hampster, 3 as cat and perhaps 5 as dog and 7 as horse.. We need large enough holes for each so that the biggest power of each set can be accommodated in LCM.. That’s how I told my younger son.
In GCD, we pick up those animals present in both and their smallest power..
GCD(18,12) = 2* 3 = 6..
Special Numbers
Mathematicians were thrilled and tried to come out with different expressions for possible prime numbers.
If we observe these prime numbers => 3, 7, 31, 127.. these fall into the form 2^n -1.. Such numbers are called Mersenne Prime Number.. The biggest number was noted in 2017 and it happens to be the 50th of this series.. (2^ 77232917)–1
A Perfect Number equals to the sum of its factors. How Interesting.. 6 = 1 + 2 + 3; 28 = 1 + 2 + 4 + 7 + 14
If a number p is prime and also 2p + 1 is prime, it is a Sophie German prime.. 2, 3, 5, 11, 23, 29, 41, 53, 83, 89 are some of them. Extremely large numbers are used in cryptography.
Lucas Primes are Prime Numbers arising from Lucas series.. It is kind of a Fibonacci series with the starting seed as 2 and 1… 2 , 1, 3, 4, 7, 11, 18, 29, 47, 76 ….
Jain 108
Prime Time Riddle
A popular hotel that had infinite rooms vertically stacked ie each floor hosting only one room. It was fully occupied. One day there were infinite coaches with infinite customers in each bus waiting to get the rooms. How would the clever Manager allocate the rooms? Mind you, no two customers can be allocated the same room.
Humm.. We need to partition the rooms cleverly according to the coach number b and the seat number s.. And these numbers should not be over lapping..
Our prime numbers come to our rescue again.. We have two approaches..
Method 1) Prime Powers
Idea is to allocate a prime number to every coach. Existing occupants will be assigned 2 and other coaches 3,5,7 .. Every guest will be assigned room according to the prime number and seat number in the coach.. Eg existing customers will be moved to Room number 2^n and first coach customers to Room number 3^n and so on.. Of course there will be vacant rooms but that should not matter for this hotel.
Method 2) Prime Factorisation
We get a little smarter here.. We use only 2 prime bases 2 & 3.. And the variables coach number c and seat number n as powers to 2 and 3.. Room Number = 2^c * 3^n
This gives us room for using remaining prime numbers as other variables if needed like infinite wings in a floor, infinite rooms in a floor etc :)
Do watch this TED Video for some Prime Fun..
References
https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel
