# Another Look at Prime Numbers

Primes are numeric celebrities: they're used in movies, security codes, puzzles, and are even the subject of forlorn looks from university professors.

This is a companion discussion topic for the original entry at http://betterexplained.com/articles/another-look-at-prime-numbers/

Just to correct one point: you say “you could even argue that pi (3.14159…) is not irrational in base “pi””. I think this is wrong: the criteria for irrationality is not the infinity of decimal figures when writing in base 10 (or any other), it is the fact that pi is not a “ratio”, i.e. not the result of a division of 2 integer numbers. Hope this helps.

Hi Kalid,

It was a good read. It would be interesting if you could explain the mechanism of cryptograhy intuitively using prime numbers !

Thank you,
Arun

Hi Michel, that’s a great point – you’re right, the formal definition of irrationality isn’t about the decimal sequence, it’s about whether it can be expressed as the ratio of two numbers p/q, as you say. I suppose you could argue (poorly ) that pi is not irrational in base pi.

Thanks Arun, I plan on addressing this in an upcoming article also. I don’t yet have a good intuitive understanding of the math involved (just a mechanical one, which I don’t like) but I would love to write about this topic.

Kalid, yes I know I’m right, as a former maths teacher

Then, I’m sorry but I don’t understand (and I’m a bit surprised, as the rest of you post is fully correct) why you repeat in your comment: “I suppose you could argue (poorly ) that pi is not irrational in base pi.”.

Numbers exist out of their representation. Surely, pi would be represented as “1” in base pi, but the number of decimals (finite/infinite) is not a criteria for rationality: 1/2 and 1/3 are both rational, and the second has infinite decimals in base 10, but finite in e.g. base 3.

Hope this helps.

Oh, I do agree, I was just making a joke in the comment that you “could” argue the point, but it would be a poor (i.e. invalid) argument to make.

Appreciate the feedback!

No, primes are ‘easy’ to discover; one can tell whether a number with d digits is prime in time polynomial in d. That isn’t practical yet, but other methods are so close to polynomial that it doesn’t matter.

Here’s how you can tell whether an inteher is prime or not. One fact about primes p (other than 2) is that

(Fermat’s little theorem) 2^{p-1} = 1 (mod p). That is, p divides 2^{p-1}-1. 7 divides 63, for example. Similarly, if p is a prime other than 3, p divides 3^{p-1} - 1.

The arithmetic of taking powers doesn’t have to be complicated; you can work ‘modulo p’ in these cases. So, if you want to check n for being prime, then look at 2^{n-1}-1. If n doesn’t divide that, n isn’t ptime. If n does divide it, try 3^{n-1}-1. If n divides that, you have more evidence for n being prime.

Now, some numbers n (called Carmichael numbers) are composite, but n divides a^{n-1}-1 for any a (relatively prime to n). So, that test won’t select only the primes. But variants do a better job.

In the end, you don’t use the Sieve of Eratosthenes to find primes. It’s too slow.

Hi Eric, thanks for the clarification! A better restatement may be that large numbers are still hard to factor into primes (which is more relevant to the security problem than simply determining whether a number is prime or not).

do u hv any tric to simplify theory as well as practical subjects?

A sure shot way to identify whether a given number is prime or not :-

The given number must confirm to the expression (6k+1) OR (6k-1) where k is any integer > 0

e.g.

1)7, is a prime number as it confirms to (6k+1) as ((6)(1) + 1)=7

2)47 is a prime number as it confirms to (6k-1) as ((6)(8) - 1)=47

Any number can in the above way be tested to see if its prime or not!

Just to correct you a little …

the formula holds true only for prime numbers greater than 3

just a tweak to a fabulous empirical formula

@Archana: I’m planning on writing about how I approach subjects. At a high level, it’s important to always ask “Why?” and “What problem is this trying to solve?” when learning a new subject. Don’t take things at face value – see what they are trying to accomplish.

@Vivek, Saurabh: Great tip! I didn’t believe it at first but this explanation helped: http://everything2.com/index.pl?node_id=1176369

Basically, every number can be written as (6k, 6k + 1, 6k+2, 6k+3, 6k+4, or 6k+5). 6k is clearly not prime. Items 6k+2 to 6k+4 can be written as 2(3k + 1), 3(2k+1), and 2(3k + 2) and therefore aren’t prime as they’re divisible by 2 or 3.

Only 6k+1 and 6k+5 [i.e. 6k-1 for a larger k] remain as possibilities for prime numbers. Be careful though, just because the two numbers are possibilities doesn’t mean either will prime. For k=141, you get 847 (7121) and 845 (5169), so neither answer is prime (try it out ).

Great insight, thanks!

Kalid: are you aware of James McCanney’s book, “Calculate Primes”, for the generation of prime numbers . . . if not, I think you would be interested; book costs about \$25 at www.jmccanneyscience.com

(great work at “betterexplained”!)

[…] His Another Look at Prime Numbers takes the otherwise for math freaks only topic of these oddly behaving numbers and looks at them from a very different perspective Chemistry. Odd and amusing and likely to stay with you for while. […]

Hi Ned, thanks for the info. I haven’t seen that book, I may add it to the reading list

Recently (2002) scientists discovered a deterministic polynomial time (basically it means that the solution is not brute-forced which takes exponential time) equation to determine if a number is a prime or composite: http://primes.utm.edu/prove/prove4_3.html

Primes are really interesting and I’ve been looking into them recently. But I haven’t reached anything conclusive about them.

Hi Dasiciks, that’s pretty cool – I’ll have to take a look. I guess the next step is factoring the number once it’s been determined to be composite. Thanks for the info.

James McCanney is a quack. Don’t bother reading his books, Kalid. See Bad Astronomy. He thinks comets are NOT made of ice, for example (and they are).

There’s also the Miller-Rabin prime test: http://snippets.dzone.com/posts/show/4636

Nice post!

Thanks gordon, interesting link! I like seeing little numerical methods like that ;).