Embed Size (px)
Citation preview
Matematiques no aplicades a la vida quotidiana
Francesc Rossello
UOM, 2013
Nombres primers
2 de 63
Definicio
Los numeros primos son aquellos cuyos padres son hermanos
(Zipi y Zape)
3 de 63
Definicio
Donats dos nombres naturals n,m, direm que n es divisible per m(o que n es un multiple de m, o que m divideix n, o que m es undivisor de n) quan el quocient n/m es un nombre natural exacte.
Exemples:
• 6 divideix 120, perque 120/6 = 20
• 6 no divideix 130, perque 130/6 = 21,666 . . .
• 1 divideix tots els numeros naturals: n/1 = n
4 de 63
Definicio
Un nombre natural es primer quan es > 2 i nomes es divisible per1 i per ell mateix
Un nombre natural es compost quan es > 2 i no es primer
Exemples:
• 2, 3, 5, 7 son primers
• 4, 6, 8, 9,10 no son primers (son composts)
• 1 no es primer
5 de 63
Els atoms de les matematiques
Teorema (fonamental de l’aritmetica)
Tot nombre natural major que 1 es pot escriure de manera unica(llevat de l’ordre) com a producte de nombres primers.
Un nombre primer es el producte d’ell tot sol
Exemples:
• 12 = 2× 2× 3
• 5 = 5
6 de 63
Els atoms de les matematiques
Demostracio d’Euclides (s. III a.C.)
Sigui n > 2 un nombre natural.
Si es primer, ja esta: n = n.
Si no es primer, sigui p1 el seu divisor mes petit diferent de 1.
p1 sera primer (si no, un divisor 6= 1 de p1 seria un divisor encarames petit de n).
Dividim n entre p1: n/p1 = q1, de manera que n = p1 × q1.
Si q1 no es primer, tornam a comencar.
7 de 63
Factoritzacions
Per exemple
120 = 2× 60 = 2× 2× 30 = 2× 2× 2× 15= 2× 2× 2× 3× 5
Obtenim120 = 2× 2× 2× 3× 5 = 23 × 3× 5
En diem una factoritzacio d’aquest nombre compost en nombresprimers
8 de 63
Com decidim si un nombre es primer?
Anam provant divisors primers. . .
Si n es compost, p es el seu factor primer mes petit, i m = n/p,aleshores p 6 m.
Per tant, basta provar divisors primers fins que el quocient donames petit que el divisor.
Exemples:
• Es 187 primer?
• Es 2013 primer?
9 de 63
Qui va descobrir els nombres primers?
L’os Ishango (∼ 9.000 a.C.—6.500 a.C.) conte alguns nombresprimers
10 de 63
Qui va descobrir els nombres primers?
Els xinesos cap al 1000 a.C. deien arrels de les matematiques alsnombres amb els que no es pot construir un rectangle de mesd’una filera (no es producte de dos nombres > 1)
15 no es una arrel de les matematiques
• • • • •• • • • •• • • • •
5 sı que ho es:• • • • •
11 de 63
Qui va descobrir els nombres primers?
12 de 63
Qui va descobrir els nombres primers?
Els jugadors del Reial Madrid?
Dorsals de la temporada 2003/2004:
• 3: Roberto Carlos
• 5: Zidane
• 7: Raul
• 11: Ronaldo
• 23: Beckham
13 de 63
Qui va descobrir els nombres primers?
En Beckham no ho crec. . .
14 de 63
Qui va descobrir els nombres primers?
Les cigales nordamericanes Magicicada tredecim i Magicicadaseptendecim tenen cicles vitals sincronitzats de 13 i 17 anys
15 de 63
Quants nombres primers hi ha?
Teorema (Euclides, s. III a.c.)
Hi ha infinits nombres primers.
Si nomes n’hi ha un nombre finit p1, . . . , pn, aleshores
p1 × p2 × · · · × pn + 1
no es divisible per cap d’aquests: per tant, o es primer, o tequalque divisor primer nou!
16 de 63
Nombres primerials
Sigui p un nombre primer. Diguem #p al producte dels nombresprimers 6 p
#2 = 2#3 = 3× 2 = 6#5 = 5× 3× 2 = 30#7 = 7× 5× 3× 2 = 210#11 = 11× 7× 5× 3× 2 = 2310
La demostracio d’Euclides es basa en el fet que cada #p + 1 esprimer o te qualque divisor primer mes gran que p.
17 de 63
Nombres primerials
Els nombres primerials son els de la forma #p + 1.
#2 + 1 = 3 primer#3 + 1 = 7 primer#5 + 1 = 31 primer#7 + 1 = 211 primer#11 + 1 = 2311 primer
Son tots els nombres primerials primers? No
#13 + 1 = 13× 11× 7× 5× 3× 2 + 1 = 30031 = 59× 509
18 de 63
Nombres primerials
Els nombres primerials son els de la forma #p + 1.
#2 + 1 = 3 primer#3 + 1 = 7 primer#5 + 1 = 31 primer#7 + 1 = 211 primer#11 + 1 = 2311 primer
Hi ha infinits nombres primers p tals que #p + 1 sigui primer?No se sap
Dels 78.498 nombres primers p < 1.000.000, nomes n’hi ha 19tals que #p + 1 sigui primer
19 de 63
Quin es el nombre primer mes gran conegut?
Es257.885.161 − 1 (17.425.170 xifres)
Trobat el 25/1/2013
20 de 63
Com trobar els nombres primers? El sedas
d’Eratostenes
(1) Escrivim tots els nombres 2, 3, . . . ,N .
21 de 63
El sedas d’Eratostenes
(2) Marcam el 2 i esborram tots els multiples de 2
22 de 63
El sedas d’Eratostenes
(3) Prenem el primer nombre que no estigui marcat (niesborrat), el marcam i esborram tots els seus multiples
23 de 63
El sedas d’Eratostenes
(4) Repetim el punt anterior mentre quedin nombres que noestiguin marcats
24 de 63
El sedas d’Eratostenes
(4) Repetim el punt anterior mentre quedin nombres que noestiguin marcats
25 de 63
El sedas d’Eratostenes
(5) Quan aturem (podem aturar quan el primer nombre nomarcat sigui >
√N), els que quedin seran primers.
26 de 63
Com trobar els nombres primers? El sedas de
Matiyasevitch
Dibuixam la parabola y = x2, i per a cada n,m > 2, unim elspunts de la parabola (−n, n2) i (m,m2) amb una recta. Lainterseccio d’aquesta recta amb l’eix x = 0 es el punt (0,m × n).
27 de 63
El sedas de Matiyasevitch
28 de 63
El sedas de Matiyasevitch
29 de 63
El sedas de Matiyasevitch
30 de 63
El sedas de Matiyasevitch
31 de 63
El sedas de Matiyasevitch
32 de 63
Com es troben primers grans? Primers de
Mersenne
El pare Mersenne (1644) escrigue en una carta que els nombres
2p − 1, amb p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257
son primers, i que si p 6 257 es un altre nombre primer,aleshores 2p − 1 es compost.
Mersenne no s’equivoca de gaire: 267 − 1 i 2257 − 1 no sonprimers, i en canvi sı que ho son 261 − 1, 289 − 1 i 2107 − 1 (5errors de 55 primers)
33 de 63
Primers de Mersenne
Diem nombres de Mersenne als nombres de la forma
2p − 1 amb p primer
Els 15 nombres primers mes grans que se coneixen son d’aquesttipus
34 de 63
Primers de Mersenne
Hi ha maneres “rapides” de comprovar si un nombre de Mersennees primer.
Definiu la successio de Lucas-Lehmer (Ln)n de la manera seguent
L1 = 4, Ln = L2n−1 − 2 si n > 2
DonaL1 = 4L2 = 42 − 2 = 14L3 = 142 − 2 = 194L4 = 1942 − 2 = 37.634L5 = 37.6342 − 2 = 1.416.317.954...
35 de 63
Primers de Mersenne
Teorema
Si n > 3, aleshores 2n − 1 es primer si, i nomes si, divideix Ln−1
• 23 − 1 = 7 divideix L2 = 14 ⇒ 3 es primer
• 24 − 1 = 15 no divideix L3 = 194 ⇒ 4 no es primer
• 25 − 1 = 31 divideix 37.634 (= 31× 1214) ⇒ 5 es primer
36 de 63
Primers de Mersenne vs nombres perfectes
Els pitagorics definiren els nombres perfectes com aquells que sonla suma dels seus divisors estrictes:
6 = 1 + 2 + 328 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 2488128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508
+1016 + 2032 + 406410 6= 1 + 2 + 512 6= 1 + 2 + 3 + 4 + 6
37 de 63
Primers de Mersenne vs nombres perfectes
Factoritzem els nombres perfectes:
6 = 2× 3 = 21 × (22 − 1)28 = 4× 7 = 22 × (23 − 1)
496 = 16× 31 = 24 × (25 − 1)8128 = 64× 127 = 26 × (27 − 1)
38 de 63
Primers de Mersenne vs nombres perfectes
Teorema
• (Euclides, s. III a.C.) Si p es primer i 2p − 1 es primer,2p−1 × (2p − 1) es perfecte
• (Euler, s. XVIII) Tot nombre perfecte parell es de la forma2p−1 × (2p − 1), amb p primer i 2p − 1 primer (de Mersenne)
Nombres perfectes parells ≡ primers de Mersenne
Hi ha nombres perfectes senars? No se sap, no n’hi ha 6 101500 i“seria miraculos”
39 de 63
Primers de Mersenne vs nombres perfectes
Teorema
• (Euclides, s. III a.C.) Si p es primer i 2p − 1 es primer,2p−1 × (2p − 1) es perfecte
• (Euler, s. XVIII) Tot nombre perfecte parell es de la forma2p−1 × (2p − 1), amb p primer i 2p − 1 primer (de Mersenne)
Nombres perfectes parells ≡ primers de MersenneHi ha infinits nombres perfectes parells (infinits nombres primersde Mersenne)? No se sap, es conjectura que sı
40 de 63
Cercant primers de Mersenne
El Great Internet Mersenne Prime Search (GIMPS) es un projectecol.laboratiu on voluntaris de tot el mon deixen que el seuordinador, a estones perdudes, corri en paral.lel un programa quecomprova si nombres de Mersenne son primers o no.
Posat en marxa l’any 1996, hi ha 783.003 ordinadors apuntats (adata 16/5/2013)
Us hi podeu apuntar a http://www.mersenne.org/
41 de 63
Com estan distribuıts els nombres primers?
Nombres (ordenats per fileres) de l’1 al 76.800, amb els primersmarcats42 de 63
L’espiral d’Ulam
Escriviu els nombres naturals en espiral
43 de 63
L’espiral d’Ulam
Deixau-hi nomes els primers
44 de 63
L’espiral d’Ulam
I tendeixen a agrupar-s’hi en diagonals
S. Ulam (1963)45 de 63
L’espiral d’Ulam
I tendeixen a agrupar-s’hi en diagonals
46 de 63
L’espiral d’Ulam
Les diagonals / corresponen a famılies de nombres de la forma4n2 + 2bn + c , n = 0, 1, 2, . . ..
La diagonal 4n2 − 2n + 41
47 de 63
L’espiral d’Ulam
Conjectura (Hardy, Littlewood, 1923)
Si 4, b, c no tenen divisors en comu, el nombre P(N) de nombresn 6 N tals que 4n2 + 2bn + c es primer satisfa que
P(N) ∼ A · N
ln(N)
amb A una formula especıfica en b, c
48 de 63
Els nombres primers en la vida quotidiana?
Poden servir per comunicar-nos amb extraterrestres
Els nombres primers no son primers perque nosaltres hohagim decidit, o perque les nostres ments estiguindissenyades d’una manera en lloc d’una altra, sinosimplement perque sı, perque la realitat matematica es aixı
(G. H. Hardy, Apologia d’un matematic
49 de 63
Els nombres primers en la vida quotidiana?
Poden servir per comunicar-nos amb extraterrestres
El que estam rebent sembla ser una sequencia llarga denombres primers [. . . ]. No es probable que cap procesastrofısic generi nomes nombres primers. Per tant, ihaurıem de ser cautelosos aquı, jo diria que, sota qualsevolcriteri que poguem plantejar, aixo sembla un missatge real”.
(Carl Sagan, Contact)
Els extraterresres emeten la sequencia dels primers 261 nombresprimers en base 2.
50 de 63
Els nombres primers en la vida quotidiana?
Serveixen per comunicar-nos amb extraterrestres
El missatge enviat des d’Arecibo te 1679 = 73× 23 bits.
Missatge enviat des d’Arecibo (1974)51 de 63
Els nombres primers en la vida quotidiana?
Serveixen per comunicar-nos amb extraterrestres
El missatge enviat des d’Arecibo te 1679 = 73× 23 bits.Organitzat en 73 fileres i 23 columnes te sentit:
Missatge enviat des d’Arecibo (1974), girat i colorejatExplicacio a http://ca.wikipedia.org/wiki/Missatge_d%27Arecibo
52 de 63
Els nombres primers en la vida quotidiana?
Serveixen per comunicar-nos amb extraterrestres
El missatge enviat des d’Arecibo te 1679 = 73× 23 bits.Organitzat en 23 fileres i 73 columnes no te sentit:
La idea es que els extraterrestres s’adonin que coneixem ladescomposicio en nombres primers53 de 63
Els nombres primers en la vida quotidiana?
Cada cop que entrau en una pagina segura, emprau nombresprimers!
Continuara la setmana que ve!
54 de 63
