Calcolatore Numeri Primi

Q: Che cos'è un numero primo?

Un numero primo è un numero intero positivo strettamente maggiore di 1 che ha esattamente due divisori positivi distinti: 1 e se stesso. Esempi comuni includono 2, 3, 5, 7, 11, 13 e 97.

Q: Perché 0 e 1 non sono considerati numeri primi?

Per definizione matematica fondamentale, un numero primo deve possedere esattamente due divisori positivi distinti. Il numero 1 ha solo un divisore positivo (se stesso), non soddisfacendo la definizione. Il numero 0 ha infiniti divisori poiché 0 diviso per qualsiasi intero non nullo dà 0 con resto 0.

Q: Perché 2 è l'unico numero primo pari?

Ogni intero pari maggiore di 2 è divisibile per 2 oltre che per 1 e per se stesso (ad esempio 4 = 2 × 2, 6 = 2 × 3). Avendo almeno tre divisori, tutti i numeri pari maggiori di 2 sono composti. Il numero 2 è l'unico numero pari con esattamente due divisori.

Q: 7 e 9 sono entrambi numeri primi?

No. 7 è un numero primo perché i suoi unici divisori sono 1 e 7. Tuttavia, 9 è un numero composto perché ha tre divisori positivi: 1, 3 e 9 (3 × 3 = 9).

Q: Come si verifica se un numero grande è primo?

Per i numeri più piccoli, i computer verificano i divisori primi fino al limite della radice quadrata ⌊√n⌋. Per numeri a 64 bit fino a 18 quintilioni, i test deterministici di Miller-Rabin valutano 7 basi matematicamente dimostrate (2, 325, 9375, 28178, 450775, 9780504, 1795265022) per stabilire la primalità con il 100% di certezza formale.

Q: Qual è il numero primo più grande?

Non esiste un numero primo più grande. Verso il 300 a.C., Euclide dimostrò che esistono infiniti numeri primi. Tuttavia, esiste un più grande numero primo attualmente noto scoperto tramite il progetto GIMPS: 2^136.279.841 − 1, composto da 41.024.320 cifre.

Q: Cosa sono i numeri coprimi (primi tra loro)?

Due numeri interi sono coprimi se il loro massimo comune divisore (MCD) è 1. Nessuno dei due numeri deve essere necessariamente primo individualmente. Ad esempio, 8 (2³) e 9 (3²) sono entrambi composti, eppure MCD(8, 9) = 1, il che li rende coprimi.

Q: Quanti numeri primi ci sono tra 1 e 100?

Ci sono esattamente 25 numeri primi tra 1 e 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 e 97. La loro somma è 1.060.

Q: Come funziona la scomposizione in fattori primi su una calcolatrice Casio fx-991ES?

Sui modelli compatibili come la Casio fx-991ES PLUS o fx-115ES PLUS, inserisci il numero intero, premi [=], quindi premi [SHIFT] seguito dal tasto [FACT] (sopra il tasto gradi/minuti). Il display mostrerà immediatamente la sua scomposizione in fattori primi.

Architettura di Calcolo

Come Funziona il Nostro Calcolatore

Costruito per offrire velocità istantanea, rigore matematico e chiarezza didattica.

Un calcolatore di numeri primi è uno strumento matematico di precisione che determina se un dato numero intero è primo o composto. Verifica la divisibilità, accerta se l'intero ha esattamente due divisori positivi, calcola i suoi fattori primi e identifica i primi vicini con assoluta certezza matematica e spiegazioni dettagliate.

Diagramma Interattivo del Flusso di Calcolo

Fai clic su una fase per esaminare il procedimento esatto:

Live Input:

1

Inserisci un Intero

Digita un numero intero positivo o seleziona uno degli esempi preimpostati.

2

Premi Verifica Primo

Il motore matematico esegue divisioni fino alla radice o test Miller-Rabin deterministici a 64 bit.

3

Leggi i Risultati

Consulta la dimostrazione formale, i controlli passo-passo, i fattori e i ranghi della serie.

Cassetta degli Attrezzi Completa

Strumenti per Numeri Primi

Calcolatori specifici creati per indagini e dimostrazioni matematiche avanzate.

Showing 25 of 25 tools

Lists & Ranges

Generatore di Primi

Genera tabelle ed elenchi completi di numeri primi con copia immediata in formato CSV.

Apri Strumento →

Check & Factors

Scomposizione in Fattori Primi

Scomponi qualsiasi numero composto in fattori primi con albero visuale e scala a gradini.

Apri Strumento →

Lists & Ranges

Primo Successivo e Precedente

Trova i numeri primi strettamente adiacenti e calcola l'esatta distanza numerica.

Apri Strumento →

Lists & Ranges

N-esimo Numero Primo

Identifica qualsiasi numero primo in base al suo ordine nella successione, dal 1° (2) al 10.000° (104.729).

Apri Strumento →

Σ

Lists & Ranges

Somma di Primi

Calcola la somma esatta di tutti i numeri primi all'interno di un intervallo con aritmetica BigInt.

Apri Strumento →

Lists & Ranges

Primi Tra Due Numeri

Trova e conta i numeri primi compresi tra due estremi, con densità e coppie di primi gemelli.

Apri Strumento →

Check & Factors

Verifica Coprimalità

How to Check If a Number Is Prime

Simple algorithms and copyable code examples in Python, JavaScript, C++, Java, and Go.

Apri Strumento →

Fondamenti Matematici

Che Cos'è un Numero Primo?

I mattoni fondamentali e indivisibili dell'aritmetica e dei numeri interi.

Diagramma Geometrico: Il Test del Rettangolo

Un numero n è primo se n tessere possono formare solo una singola fila di 1 × n. Se formano un rettangolo pieno con larghezza > 1, il numero è composto.

Numero (n):

Prova esempi:

12 is Composite: 3 rectangular arrangements possible

Displaying a 3 × 4 rectangular array with zero remainder.

Definizione ed Esempi

In matematica, un numero primo è un numero intero positivo maggiore di 1 che ha esattamente due divisori positivi distinti: 1 e se stesso.

I primi dieci numeri primi sono: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Qualsiasi numero intero maggiore di 1 che non è primo viene definito numero composto.

Quick Integer Classifier (Tap 0, 1, 2, or Any Integer)

2 is the ONLY even prime — factors: 2 (exactly 2 divisors).

Indivisible emerald prime polyhedra beside a factored composite block — **The Building Blocks of Arithmetic** Like chemical elements in chemistry, prime numbers cannot break down further—every composite whole splits cleanly into a unique product of primes.

Perché 0 e 1 Non Sono Primi

0 non è né primo né composto: ha infiniti divisori poiché 0 diviso per qualsiasi intero diverso da zero dà resto zero.

1 non è né primo né composto: ha un solo divisore (se stesso). Se 1 fosse primo, il Teorema Fondamentale dell'Aritmetica perderebbe l'unicità della scomposizione.

Classification map of whole numbers: 0 (zero divisors rule), 1 (unit), Primes (2 factors), and Composites (3+ factors).

Numeri Primi vs Numeri Composti

Differenze matematiche essenziali tra le due classi di numeri interi positivi:

Proprietà	Numeri Primi	Numeri Composti
Definizione	Esattamente due divisori positivi distinti: 1 e se stesso	Più di due divisori positivi
Numero di divisori	Rigorosamente 2 divisori	3 o più divisori
Membro più piccolo	2 (l'unico primo pari)	4 (2 × 2)
Fattorizzazione in primi	Il numero stesso (p¹)	Prodotto unico di potenze di primi (p₁ᵃ × p₂ᵇ …)
Interi pari	Solo il 2 è primo; tutti gli altri numeri pari sono composti	Tutti gli interi pari > 2 (4, 6, 8, 10, 12…)
Esempi	2, 3, 5, 7, 11, 13, 97, 101	4, 6, 8, 9, 12, 51, 91, 100

Perché 2 è l'Unico Primo Pari

Un numero pari è divisibile per 2. Il numero 2 ha solo due divisori: 1 e 2, soddisfacendo la definizione. Tuttavia, ogni pari n > 2 è divisibile per 1, 2 e n, avendo almeno 3 divisori.

7 e 9 Sono Numeri Primi?

7 è un numero primo: i suoi unici divisori sono 1 e 7. 9 NON è un numero primo: è divisibile per 3 (3 × 3 = 9). Essere dispari non garantisce che un numero sia primo!

Metodi e Dimostrazioni

Come Verificare se un Numero è Primo

Il limite classico della radice quadrata e gli algoritmi di calcolo.

Simulatore Interattivo: Limite della Radice e Divisioni per Tentativi

Scopri come la soglia ⌊√n⌋ riduce drasticamente le prove necessarie per accertare la primalità.

Intero da testare (n):

Prova casi di test:

Limite della radice quadrata

√97 ≈ 9.85

p ≤ 7 (⌊√97⌋ = 9)

Primi da testare

4

2, 3, 5, 7

Test risparmiati dal limite

92

92 / 96 (95.8%)

Search Horizon Visualization (1 → ⌊√n⌋ → n) Only prime divisors ≤ ⌊√n⌋ are needed

Controlli di divisibilità fino a √n

Multi-stage lattice filter separating composite numbers from emerald prime values — **Eliminating Multiples Early** Small prime filters (2, 3, 5, 7…) sift out composites immediately, shrinking candidate tests up to √N.

Why √N Is the Exact Cutoff Every factor pair (a × b = n) has one member ≤ √n and the mirror cofactor ≥ √n.

Verificare la Divisibilità Fino a √n

Per verificare se un intero n è primo, non serve testare tutti i numeri fino a n. È sufficiente testare i soli numeri primi minori o uguali alla sua radice quadrata: d ≤ ⌊√n⌋.

Perché funziona: I divisori si presentano sempre a coppie complementari: a × b = n. Se entrambi i fattori fossero maggiori di √n, il loro prodotto supererebbe n, il che è impossibile.

Esempio svolto: 97 è primo?

Calcola √97 ≈ 9,848. Testiamo solo i numeri primi ≤ 9.
I numeri primi da testare sono: 2, 3, 5, 7.
97 ÷ 2 = 48 R 1 (Non divisibile, termina con la cifra dispari 7).
97 ÷ 3 = 32 R 1 (Non divisibile, la somma delle cifre 9+7=16 non è divisibile per 3).
97 ÷ 5 = 19 R 2 (Non divisibile, non termina con 0 o 5).
97 ÷ 7 = 13 R 6 (Non divisibile).
Tutti i candidati primi ≤ √97 non sono riusciti a dividere 97 esattamente. Pertanto, 97 è dimostrato primo!

Esempio svolto: Perché 91 è composto?

Calcola √91 ≈ 9,539. Testiamo solo i numeri primi ≤ 9.
I numeri primi da testare sono: 2, 3, 5, 7.
91 ÷ 2 = 45 R 1 (Non divisibile).
91 ÷ 3 = 30 R 1 (Non divisibile, somma delle cifre 9+1=10).
91 ÷ 5 = 18 R 1 (Non divisibile, non termina con 0 o 5).
91 ÷ 7 = 13 R 0 (Divide esattamente!).
Poiché 7 è un divisore, 91 è composto: 91 = 7 × 13.

Scorciatoie mentali di divisibilità

Puoi eliminare rapidamente molti candidati composti usando semplici regole di aritmetica mentale:

Divisibile per 2: L'ultima cifra è pari (0, 2, 4, 6, 8).
Divisibile per 3: La somma di tutte le cifre è un multiplo di 3 (es. per 51: 5+1=6, quindi 51 ÷ 3 = 17).
Divisibile per 5: L'ultima cifra è 0 o 5.
La regola 6k ± 1: Ogni numero primo maggiore di 3 può essere scritto come 6k − 1 o 6k + 1. Sebbene non tutti i numeri di questa forma siano primi, qualsiasi numero non in questa forma è garantito essere composto!

Calcolo Mentale e Scorciatoie

Criteri di Divisibilità e Scorciatoie

Regole mentali per escludere immediatamente numeri composti senza l'uso della calcolatrice.

Diagramma Interattivo: La Ruota Modulo 6 (6k ± 1)

Tutti i numeri primi maggiori di 3 cadono esclusivamente nelle forme 6k + 1 o 6k - 1.

Intero da testare (n):

Prova esempi:

La Regola di Primalità 6k ± 1

97 = 6 × 16 + 1

Remainder dividing by 6: 1 → 6k + 1

Interactive Divisibility Scanner (Test Any Number Against All 10 Rules) Testing 2,730 — divisible by 2, 3, 5, 6, 7, 13 (6 rules match).

Divisore	Criterio di Divisibilità e Scorciatoia	Esempio Pratico
2	L'ultima cifra è pari: 0, 2, 4, 6 o 8.	248 termina con 8 → Divisibile per 2
3	La somma di tutte le singole cifre è divisibile per 3.	453 → 4+5+3 = 12 (divisibile per 3) → Divisibile per 3
4	Il numero formato dalle ultime due cifre è divisibile per 4.	3.116 termina con 16 (16 ÷ 4 = 4) → Divisibile per 4
5	L'ultima cifra è 0 oppure 5.	895 termina con 5 → Divisibile per 5
6	Il numero supera sia il test del 2 (pari) che il test del 3 (somma delle cifre).	732 è pari e 7+3+2 = 12 → Divisibile per 6
7	Raddoppia l'ultima cifra e sottraila dal resto. Il risultato è divisibile per 7.	672 → 67 − (2×2) = 63 (63 ÷ 7 = 9) → Divisibile per 7
8	Il numero formato dalle ultime tre cifre è divisibile per 8.	5.128 termina con 128 (128 ÷ 8 = 16) → Divisibile per 8
9	La somma di tutte le singole cifre è divisibile per 9.	2.871 → 2+8+7+1 = 18 (18 ÷ 9 = 2) → Divisibile per 9
11	La somma alternata delle cifre (aggiungi-sottrai-aggiungi...) è 0 o un multiplo di 11.	913 → 9 − 1 + 3 = 11 → Divisibile per 11
13	Aggiungi 4 volte l'ultima cifra al prefisso rimanente. La somma è divisibile per 13.	299 → 29 + (9×4) = 65 (65 ÷ 13 = 5) → Divisibile per 13

La Regola di Primalità 6k ± 1

Tutti i numeri primi maggiori di 3 cadono esclusivamente nelle forme 6k + 1 o 6k - 1.

6k − 1 | 6k + 1

Perché questo è garantito: Qualsiasi intero può essere suddiviso in una di sei forme: 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5 (che è 6(k+1)−1).

6k, 6k+2, 6k+4 sono sempre pari (divisibili per 2).
6k+3 è sempre divisibile per 3.

Avviso critico: Questa è una condizione necessaria, non sufficiente. Sebbene ogni primo > 3 abbia questa forma, alcuni numeri di questa forma sono composti (es. 25 = 6(4)+1 e 35 = 6(6)−1). Verifica sempre i candidati usando la divisione per tentativi limitata.

Perché Non Esiste una Formula Semplice per i Primi

Nel 1772, Leonhard Euler scoprì lo straordinario polinomio quadratico f(n) = n² + n + 41 che produce solo numeri primi per ogni intero n = 0, 1, 2, ..., 39 (40 primi consecutivi: 41, 43, 47, 53, 61, ..., 1601).

f(n) = n² + n + 41

Tuttavia, per n = 40, il polinomio produce 40² + 40 + 41 = 1.681 = 41², dimostrando che nessun polinomio algebrico non costante può mai generare esclusivamente numeri primi all'infinito.

Click any n (0–45) to verify f(n): f(0) = 41 (Prime)

Griglia Visuale di Riferimento

Tabella dei Numeri Primi da 1 a 100

Griglia interattiva 10×10. Utilizza il simulatore del Crivello di Eratostene per osservare l'eliminazione dei numeri composti.

Numeri Primi (1–100) Σ = 1,060

Primo (25 numeri: 2, 3, 5, 7, 11, … 97)

Composto (74 numeri: multipli dei primi testati)

Nessuno dei due (1) (Elemento neutro: esattamente 1 divisore)

Applica l'antico algoritmo: cancella i multipli di 2, 3, 5 e 7 per far emergere tutti i 25 numeri primi.

Catalogo Esteso

Numeri Primi da 1 a 1.000

Ci sono esattamente 168 numeri primi compresi tra 1 e 1.000.

Diagramma Interattivo: Distribuzione per Centinaia

Fai clic su qualsiasi barra per filtrare i 168 numeri primi.

Visualizzazione di 168 primi dimostrati (da 1 a 1000) (Σ = 76,127)

Visualizza tutti i 168 Numeri Primi fino a 1.000 ▾

Clicca su qualsiasi numero primo qui sotto per caricarlo nella calcolatrice.

Traguardi della Successione

Traguardi Fondamentali tra i Numeri Primi

Questi numeri primi rappresentano tappe fondamentali nella teoria dei numeri e nell'informatica.

Posizione / Ordine (n):

Traguardi notevoli:

Ricerca N-esimo Primo e Curva di Crescita Asintotica p(100) = 541 · 100 × ln(100) ≈ 461

Slide Rank (1–10,000):

Exact p(n) n · ln(n)

Valore dell'n-esimo Primo

541

p(100)

Primi Adiacenti

p₉₉: 523 · p₁₀₁: 547

p(n−1) · p(n+1)

Posizione nella sequenza dei primi

#100

Sequenza OEIS A000040

Traguardi chiave nella sequenza dei numeri primi

Questi numeri primi di riferimento segnano confini importanti in matematica, test computazionali e teoria dei numeri:

#1 → 2

p₁ = 2

Il primo più piccolo, il primo numero primo positivo e l'unico numero primo pari esistente. Tutti i primi successivi sono interi dispari.

#25 → 97

p₂₅ = 97

Il più grande numero primo a due cifre. Esattamente 25 numeri primi risiedono tra 1 e 100, formando il 25% di tutti gli interi in base 10 fino a due cifre.

#100 → 541

p₁₀₀ = 541

Il traguardo del 100° numero primo. Segna il completamento dei primi cento numeri primi, con una densità complessiva del 18,5% in questo intervallo.

#1,000 → 7,919

p₁₀₀₀ = 7,919

Il millesimo numero primo. Dimostra che i primi diventano progressivamente più rari al crescere dei numeri: servono 7.919 interi per trovare 1.000 primi (densità del 12,6%).

#5,000 → 48,611

p₅₀₀₀ = 48,611

Il cinquemillesimo numero primo. Si trova appena sotto la soglia di 50.000, mostrando una densità localizzata di circa il 10,3%.

#10,000 → 104,729

p₁₀₀₀₀ = 104,729

Il riferimento del 10.000° numero primo. La nostra ricerca istantanea in tabella copre tutti i primi fino a questo limite senza alcun ritardo del server.

Teoria Analitica dei Numeri

Funzione Contaprimi π(x) e Densità

Scopri come diminuisce la frequenza dei numeri primi e approfondisci il Teorema dei Numeri Primi di Gauss.

Inserisci il limite superiore (x):

Limiti predefiniti:

Misuratore Interattivo di Densità e Progresso Densità dei primi: 16.80% (~1/6)

0% 25% (x=100) 50% 100%

Conteggio esatto π(x)

168

Primi rigorosamente ≤ x (≤ 1,000)

Densità dei primi

16.80%

Percentuale di interi primi

Stima PNT di Gauss

144.76

Errore Relativo (%): −13.8%

Conteggio dei Primi per Potenze di 10

All'aumentare dei numeri, i primi diventano più rari, eppure ne esistono infiniti. Nota come l'approssimazione del Teorema dei Numeri Primi x / ln(x) converga più da vicino in percentuale relativa al crescere di x:

Limite Superiore (x)	π(x) Esatto	Densità (%)	PNT Gauss: x / ln(x)	Errore Relativo (%)
10	4	40.00%	4.34	+8.5%
100	25	25.00%	21.71	−13.1%
1,000	168	16.80%	144.76	−13.8%
10,000	1,229	12.29%	1,085.74	−11.7%
100,000	9,592	9.59%	8,685.89	−9.4%
1,000,000	78,498	7.85%	72,382.41	−7.8%
10,000,000	664,579	6.65%	620,420.69	−6.6%
100,000,000	5,761,455	5.76%	5,428,681.02	−5.8%

Che Cosa Significa la Funzione π(x)?

Nella teoria dei numeri, π(x) non si riferisce alla costante geometrica π ≈ 3,14159. Piuttosto, i matematici del XVIII secolo guidati da Carl Friedrich Gauss adottarono la lettera greca π (da plēthos, che significa "moltitudine") per indicare la Funzione enumerativa dei primi: il numero esatto di primi minori o uguali a x.

A differenza delle funzioni algebriche, π(x) è una funzione a gradino che aumenta di 1 ogni volta che x supera un numero primo.

Il Teorema dei Numeri Primi (PNT)

Dimostrato indipendentemente nel 1896 da Jacques Hadamard e Charles Jean de la Vallée Poussin, il Teorema dei Numeri Primi afferma che quando x tende all'infinito, la distribuzione dei primi segue:

π(x) ~ x / ln(x)

Questo teorema rivela che la probabilità che un intero scelto casualmente vicino a x sia primo è approssimativamente 1 / ln(x).

Exact π(x) vs Gauss’s Li(x) vs x/ln(x) As upper bound x grows toward 10⁸, prime density smoothly thins like 1/ln(x) while Gauss’s logarithmic integral Li(x) hugs the true count far more closely than x/ln(x).

Analisi di Intervallo

Trova Numeri Primi in un Intervallo

Trova, conta e calcola la somma esatta in BigInt dei numeri primi compresi tra due estremi.

Numero Iniziale:

Numero Finale:

Predefiniti:

Trova Numeri Primi in un Intervallo Densità dei primi: 25.0%

Density Histogram (10 bins) Prime Position Twin Prime Pair (Δ = 2)

Conteggio Primi

25

π(end) − π(start−1)

Somma Cumulativa

1,060

Somma BigInt esatta

Estremi dell'Intervallo

2 … 97

Estremi inclusi

Primi Adiacenti

Trova il Primo Successivo e Precedente

Individua i numeri primi immediatamente contigui, calcola la distanza esatta e trova il massimo primo ≤ n.

Inserisci qualsiasi numero intero positivo (n):

Prova esempi:

Diagramma Interattivo: Pista dei Salti tra Primi 89 (Δ = 1)

n: 90

Primo precedente (p < n)

89

Δ = −1

n

90

Composto dimostrato

Primo successivo (p > n)

97

Δ = +7

Primo più vicino 89 (Δ = 1)

max(p ≤ n) 89

Apri Strumento →

Vicini Stretti vs Limiti Inclusivi

Quando si cercano numeri primi adiacenti, la precisione matematica richiede di distinguere tra primi rigorosamente adiacenti e limiti inclusivi:

Primo rigorosamente precedente (p < n): Il più grande numero primo rigorosamente minore di n. Per n = 97, il primo precedente è 89.
Primo rigorosamente successivo (p > n): Il più piccolo numero primo rigorosamente maggiore di n. Per n = 97, il primo successivo è 101.
Più grande primo ≤ n: Se n stesso è primo (come 97), il più grande primo ≤ 97 è 97. Se n è composto (come 90), è 89.

Postulato di Bertrand e Distanze Equidistanti

Quanto può essere distante il primo successivo? Nel 1850, Pafnuty Chebyshev dimostrò il Postulato di Bertrand: per qualsiasi intero n > 3, esiste sempre almeno un numero primo p tale che:

n < p < 2n − 2

Pareggi equidistanti: Per alcuni numeri, il primo precedente e quello successivo si trovano esattamente alla stessa distanza. Ad esempio, per n = 6, il precedente è 5 (dist 1) e il successivo è 7 (dist 1). Entrambi sono i primi più vicini!

Scomposizione e Passaggi

Scomposizione in Fattori Primi con Passaggi

Come ogni numero composto si scompone in modo unico in potenze di numeri primi.

Diagramma interattivo dell'albero dei fattori e scala di divisione

Inserisci qualsiasi intero per generare sia il suo albero dei fattori visivo in SVG sia la scala di divisione passo dopo passo.

Numero (n):

Prova esempi:

Forma Esponenziale Canonica

360 = 2³ × 3² × 5

Calcolatore Completo di Scomposizione →

Teoria dei Numeri e MCD

Verifica Numeri Coprimi (Primi tra Loro)

Determina se due numeri non condividono divisori comuni oltre all'1 tramite l'algoritmo euclideo.

Primo Intero (a):

Secondo Intero (b):

Prova coppie:

✓ (8, 9) — SONO COPRIMI (Relativamente primi)

gcd(8, 9) = 1

Valore MCD 1

Diagramma Interattivo: Tassellazione Geometrica Euclidea Piastrella comune più grande: 1 × 1

Euclide scoprì che trovare mcd(a, b) è identico a trovare la piastrella quadrata più grande che può pavimentare perfettamente un rettangolo a × b senza spazi vuoti o sovrapposizioni:

Passaggi di divisione dell'algoritmo di Euclide

9 = 8 × 1 + 1

8 = 1 × 8 + 0

Due numeri composti possono essere coprimi?

Sì, assolutamente! Questo è uno dei concetti più comunemente fraintesi nella teoria elementare dei numeri. Due numeri sono coprimi (o relativamente primi) se il loro massimo comune divisore è 1, indipendentemente dal fatto che i numeri stessi siano primi.

gcd(a, b) = 1

Considera 8 = 2³ (composto) e 9 = 3² (composto). Nessuno dei due numeri è primo! Eppure, poiché le loro fattorizzazioni in primi non condividono alcun fattore primo comune, mcd(8, 9) = 1, rendendoli completamente coprimi.

Perché la coprimalità è importante in crittografia

Funzione toziente di Eulero φ(n): Conta quanti interi fino a n sono coprimi con n. Per i numeri primi, φ(p) = p − 1.
Generazione chiavi RSA: L'esponente pubblico e deve essere rigorosamente coprimo con φ(n) = (p − 1)(q − 1) affinché esista il suo inverso moltiplicativo modulare d.
Distribuzione hash: La scelta di dimensioni coprime per i bucket hash previene il clustering nelle tabelle hash ad alte prestazioni.

Trabocchetti Comuni

Numeri che Sembrano Primi (Ma Non lo Sono)

Numeri composti ingannevoli che traggono spesso in inganno studenti e programmatori.

Ispettore Interattivo: Analisi dei Falsi Primi

Decostruire il 91: Il falso primo più famoso

91 = 7 × 13

√91 ≈ 9.54 (p ≤ 7)

Il Punto Cieco Cognitivo

91 termina con 1, quindi supera il controllo dei pari (2). La somma delle cifre è 9+1=10, quindi supera il 3. Non termina con 5. Poiché né il 7 né il 13 si trovano nelle tipiche tabelline elementari, gli esseri umani presumono inconsciamente che 91 debba essere primo!

51 Composto

3 × 17

5 + 1 = 6 (÷ 3 → 51 = 3 × 17)