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 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.
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).
@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.
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 ).
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
[…] 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. […]
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.