Numeri primi

[Stex19]

Vorrei raccogliere tutti i possibili modi con cui si possono definire i numeri primi, ossia le condizioni che, se realizzate, implicano che un numero sia primo.
al momento me ne sono venute in mente 3:
($ p>1 $)

1) se $ (p;(p-1)!)=1 $, allora p è primo

2) se $ \varphi(p)=p-1 $ dove $ \varphi(x) $ è la funzione di eulero, allora p è primo

3) se $ p|(p-1)!+1 $ allora p è primo (teorema di wilson)

se ne sapete altri postateli, poi semmai li aggiungo al primo post....

[pic88]

Vorrei raccogliere tutti i possibili modi con cui si possono definire i numeri primi, ossia le condizioni che, se realizzate, implicano che un numero sia primo.

Lol ma dovrebbero anche essere necessarie, sennò non è una definizione equivalente. Anche essere uguali a 5 è una condizione che, se realizzata, implica che un numero sia primo....


EDIT: mettiamo anche la "vera" definizione, ma mi pare se ne sia già parlato. Un numero p intero >1 è primo sse p|ab implica p|a V p|b

[Stex19]

Vorrei raccogliere tutti i possibili modi con cui si possono definire i numeri primi, ossia le condizioni che, se realizzate, implicano che un numero sia primo.

Lol ma dovrebbero anche essere necessarie, sennò non è una definizione equivalente. Anche essere uguali a 5 è una condizione che, se realizzata, implica che un numero sia primo....


EDIT: mettiamo anche la "vera" definizione, ma mi pare se ne sia già parlato. Un numero p intero >1 è primo sse p|ab implica p|a V p|b

beh si.... è ovvio....
non sono anche necessarie quelle che ho scritto?

[salva90]

la prima non è sufficiente... prendi p=1
(1, 0!)=1, ma 1 non è primo

[Stex19]

la prima non è sufficiente... prendi p=1
(1, 0!)=1, ma 1 non è primo

è vero...
in fondo quella me l'ero inventata io ieri mentre cenavo...
è che davo per scontato che 1 non è primo....

[SkZ]

comunque mi pare che quasi tutte le definizioni di numero primo abbiano $ $p>1$ $ tra le ipotesi, ergo metticelo pure tu all'inizio del tuo post

[linux]

capita a fagiolo questo topic !

allora....

da un post vecchiotto ho trovato questo link http://en.wikipedia.org/wiki/Fermat_primality_test

e devo dire che mi ha lasciato perplesso alquanto....

" Concept

Fermat's little theorem states that if p is prime and


$ \displaystyle 1 \le a < p $

then


$ \displaystyle a^{p-1} \equiv 1 \pmod{p} $

se ancora so leggere a può essere uguale ad $ \displaystyle 1 $ visto che a deve essere maggiore/uguale ad uno e minore di p

se ancora so fare bene i conti.....

$ \displaystyle 1^n = 1 $

quindi presumo che

$ \displaystyle 1 \equiv 1 \pmod{p} $

quindi tutti i numeri sono primi !!!!!!!

sto dando di matto o wiki è impazzita ???

se sono uscito pazzo qualche anima pia mi spiega la situazione ???

[salva90]

SE p è primo quella roba fa 1
mica deve valere il viceversa

[linux]

proviamo....

Concept

Fermat's little theorem states that if p is prime and


$ \displaystyle 1 \le a < p $
,then

$ a^{p-1} \equiv 1 \pmod{p} $

quindi.....

voglio vedere se 8 è numero primo



come dice wiki , prendo a maggiore/uguale ad $ \displaystyle 1 $ e come contemplato sopra $ \displaystyle 1 $ è minore del numero che voglio testare $ \displaystyle 8 $

THEN ( per dirla con wiki )

$ \displaystyle a^{8-1} \equiv 1 \pmod{8} $

ERGO ( per dirla con Cicerone )

$ \displaystyle a^{7} \equiv 1 \pmod{8} $

sostituendo la a

$ \displaystyle 1^{7} \equiv 1 \pmod{8} $

$ \displaystyle 1^{7} \equiv 1 \pmod{8} $

$ \displaystyle 1 \equiv 1 \pmod{8} $

quindi qui risulta che $ \displaystyle 8 $
è un numero primo !!!!

( a meno che il sole non mi abbia fuso l'unico neurone funzionante...mooooooolto probabile)

chiedo anticipatamente scusa delle cavolate , se ne sto dicendo

[pic88]

LOL ma lo insegnano ancora nelle scuole che "A implica B" non significa "(non A) implica (non B)"? Che poi il viceversa sarebbe "se quella roba vale per ogni a intero in [1, p[, allora p è primo".... prova a dimostrare o confutare quest'ultima

[Stex19]

il piccolo teorema di fermat dice che se $ p $ è primo, allora si verifica la congruneza, ma non che la conguenza si verifica solo con numeri primi....
in poche parole, con i primi è sempre vera la congruenza per qualsiasi $ a $, con i non primi a volte si a volte no.
è il teorema di wilson che è vero anche al contrario....

p.s. la condizione su $ a $ in fermat piccolo non era solo che deve essere coprima a $ p $?

p.p.s

comunque mi pare che quasi tutte le definizioni di numero primo abbiano $ $p>1$ $ tra le ipotesi, ergo metticelo pure tu all'inizio del tuo post

è vero... anche con il teorema di wilson risulterebbe che 1 è primo se non si pone p>1....

[pa]

comunque il fatto del piccolo teorema di fermat e' usato spessissimo per trovare numeri primi grandi, anzi, l'algoritmo piu' usato per trovare (probabili) numeri primi grandi e' proprio basato su di esso:
http://en.wikipedia.org/wiki/Miller-Rab ... ality_test
esiste un algoritmo con complessita' polinomiale ma e' in $ O(n^{12}) $!!!

[SkZ]

una definizione che non necessita di $ $p>1$ $ mi pare sia
Sia $ $D_n=\{x\in\mathbb{N}^*:\frac{n}{x}\in\mathbb{N}\}$ $, $ $p$ $ e' primo se e solo se $ $card(D_p)=2$ $

in tal caso $ $card(D_1)=1$ $, ma la cosa carina e' che $ $card(D_0)=\aleph_0$ $

definizione poco utile pero'

[Fedecart]

Girando un po in internet, stavo cercando un elenco dei numeri primi da uno a 10000, quando ho trovato per caso questo. Ditemi, se vi va, che ne pensate. Io personalmente non mi trovo d'accordo su un punto e mi perdo in un altro, ma di certo non sono in grado di dare un giudizio!

http://www.geocities.com/tetractius83/C ... eprimi.htm

[SkZ]

a proposito di siti, buon sito (in inglese) e'
http://primes.utm.edu/