09 November 2007

On the infinitude of primes

From Microsiervos: two videos: "Cómo Arquímedes calculó el volumen de una esfera" (5:52) and "Sobre la suma de los recíprocos de los números primos" 11:46 (That is, "how Archimedes calculated the volume of a sphere" and "On the sum of the reciprocals of prime numbers")

There's a bit of an apparent error. Translating the slide that's on the screen at 3:00 in the second video:
Proof
If P [the set of primes] is finite, P := {p_1, p_2, ..., p_n} in increasing order.
Let us form the number p_1 p_2 ... p_n + 1.
This number is greater than p_n, therefore it is not prime.
It is not divisible by p_1, nor by p_2, ..., nor by p_n, therefore it is prime.
Contradiction.

(There's nothing in what the speaker says that contradicts this; it's just easier for me to translate from the written text than the speaker.)

Indeed, the original post at Microsiervos points this out:
La demostración de Euclides de que hay infinitos primos que se presenta es incompleta: el 30031 sería un contraejemplo (se construye como 2 × 3 × 5 × 7 × 11 × 13 + 1 pero aun no siendo divisible entre 2, 3, 5, 7, 11, 13 no es primo: 59 × 509). Así que faltaría añadir «… o bien [el número creado] está compuesto por la multiplicación de otros números primos mayores que los de la lista original».

That is,
Euclid's demonstration that there are infinitely many primes, as presented here, is incomplete; 30031 would be a counterexample (it can be constructed as 2 × 3 × 5 × 7 × 11 × 13 + 1, which despite not being divisible by 2, 3, 5, 7, 11, and 13 is not prime: 59 × 509. One must add: "or else [the created number] is composite and made of oter prime numbers larger than those from the original list.


I'd claim that this isn't really an error; we've assumed there are no other primes, so the number p1...pn+1 can't be divisible by some other primes. It's hard to keep things straight because we all know there are infinitely many primes.

This also includes the classic demonstration that the sum 1 + 1/2 + 1/3 + 1/4 + ... is infinite, which leads to Euler's analytic proof of the infinitude of primes (roughly, the number of primes "is ζ(1)") before eventually getting to the proof that the sum of the reciprocals of primes diverges. (Wikipedia says that means that the primes are a large set, which seems like a good name, but I don't know if people actually use this term.) Also see this English Wikipedia article for a lot of the content of the second video.

Oh, and ζ in (Castilian) Spanish apparently sounds the same as θ in (American) English. How do Castilians pronounce θ?

4 comments:

Adri said...

'Teta'

Which incidentally is the same word as boob in the same language. Funny twists of life.

Zeta is pronounced effectively 'Theta' because of the strongly local way of pronouncing z'eds as th.

^DiAmOnD^ said...

First of all, sorry for my English :S.

Spanish (Spain) people usually pronounce this two greek letters like this:

ζ: zeta (like theta)
θ: teta or tita

Wikipedia (Spanish) says:

"Hasta su diccionario de 1992 la Real Academia Española denominaba theta a la θ y zeta a la ζ. Hoy registra los nombres de zeta (θ) y dseda (ζ)."

That is:

"Before 1992: theta=θ; zeta=ζ.
After 1992: zeta=θ; dseda=ζ."

Ups, my pronunciation is theta=θ and zeta=ζ. I'm wrong!! :(.

alvy said...

Hi Isabel,

You are right. I misunderstood the proof presented on the video with the «old-fashion» Euclides proof that seems to be somehow slightly diferent (I didn't watch closely the video and thought there was only one version of the proof).

I found this page where anybody can check both versions of the same demonstration

Euclid's Proof of the Infinitude of Primes (c. 300 BC)

Thanks for your post and your comment!

Anonymous said...

[... ] is other relavant source on this topic[...]