• Traduzione

Proprietà numeri primi cominciò a studiare matematica Grecia antica. I matematici della scuola pitagorica (500-300 a.C.) erano interessati principalmente alle proprietà mistiche e numerologiche dei numeri primi. Sono stati i primi a inventare idee sui numeri perfetti e amichevoli.

Un numero perfetto ha la somma dei propri divisori uguale a se stesso. Ad esempio, i divisori propri del numero 6 sono 1, 2 e 3. 1 + 2 + 3 = 6. I divisori del numero 28 sono 1, 2, 4, 7 e 14. Inoltre, 1 + 2 + 4 + 7 + 14 = 28.

I numeri sono chiamati amichevoli se la somma dei divisori propri di un numero è uguale a un altro e viceversa, ad esempio 220 e 284. Possiamo dire che un numero perfetto è amico di se stesso.

Al tempo degli Elementi di Euclide nel 300 a.C. Molti fatti importanti sui numeri primi sono già stati dimostrati. Nel Libro IX degli Elementi Euclide dimostrò che i numeri primi sono infiniti. Questo, tra l'altro, è uno dei primi esempi di utilizzo della prova per contraddizione. Dimostra anche il teorema fondamentale dell'aritmetica: ogni intero può essere rappresentato in modo univoco come prodotto di numeri primi.

Mostrò anche che se il numero 2n-1 è primo, allora il numero 2n-1 * (2n-1) sarà perfetto. Un altro matematico, Eulero, riuscì a dimostrare nel 1747 che tutti i numeri perfetti pari possono essere scritti in questa forma. Ad oggi non è noto se esistano numeri perfetti dispari.

Nell'anno 200 a.C. Il greco Eratostene inventò un algoritmo per trovare i numeri primi chiamato Setaccio di Eratostene.

E poi ci fu una grande svolta nella storia dello studio dei numeri primi, associata al Medioevo.

Le seguenti scoperte furono fatte già all'inizio del XVII secolo dal matematico Fermat. Dimostrò la congettura di Albert Girard secondo cui qualsiasi numero primo della forma 4n+1 può essere scritto unicamente come somma di due quadrati e formulò anche il teorema secondo cui qualsiasi numero primo può essere scritto come somma di quattro quadrati.

Si è sviluppato nuovo metodo fattorizzazione grandi numeri, e lo dimostrò sul numero 2027651281 = 44021 × 46061. Dimostrò anche il Piccolo Teorema di Fermat: se p è un numero primo, allora per ogni intero a sarà vero che a p = a modulo p.

Questa affermazione dimostra la metà di quella che era conosciuta come la “congettura cinese” e risale a 2000 anni fa: un intero n è primo se e solo se 2 n -2 è divisibile per n. La seconda parte dell'ipotesi si è rivelata falsa: ad esempio 2.341 - 2 è divisibile per 341, sebbene il numero 341 sia composto: 341 = 31 × 11.

Il Piccolo Teorema di Fermat servì come base per molti altri risultati nella teoria dei numeri e metodi per verificare se i numeri sono primi, molti dei quali sono ancora utilizzati oggi.

Fermat corrispondeva molto con i suoi contemporanei, soprattutto con un monaco di nome Maren Mersenne. In una delle sue lettere ipotizzò che i numeri della forma 2 n +1 saranno sempre primi se n è una potenza di due. Lo testò per n = 1, 2, 4, 8 e 16 ed era sicuro che nel caso in cui n non fosse una potenza di due, il numero non fosse necessariamente primo. Questi numeri sono chiamati numeri di Fermat, e solo 100 anni dopo Eulero dimostrò che il numero successivo, 2 32 + 1 = 4294967297, è divisibile per 641, e quindi non è primo.

Anche i numeri della forma 2 n - 1 sono stati oggetto di ricerca, poiché è facile dimostrare che se n è composto, allora anche il numero stesso è composto. Questi numeri sono chiamati numeri di Mersenne perché li studiò approfonditamente.

Ma non tutti i numeri della forma 2 n - 1, dove n è primo, sono primi. Ad esempio, 2 11 - 1 = 2047 = 23 * 89. Questo fu scoperto per la prima volta nel 1536.

Per molti anni numeri di questo tipo hanno fornito ai matematici i più grandi numeri primi conosciuti. Che M 19 fu dimostrato da Cataldi nel 1588, e per 200 anni fu il più grande numero primo conosciuto, finché Eulero dimostrò che anche M 31 era primo. Questo record durò altri cento anni, poi Lucas dimostrò che M 127 è primo (e questo è già un numero di 39 cifre), e successivamente la ricerca continuò con l'avvento dei computer.

Nel 1952 fu dimostrata l'eccellenza dei numeri M 521, M 607, M 1279, M 2203 e M 2281.

Nel 2005 erano stati trovati 42 primi di Mersenne. Il più grande di essi, M 25964951, è composto da 7816230 cifre.

Il lavoro di Eulero ha avuto un enorme impatto sulla teoria dei numeri, compresi i numeri primi. Estese il Piccolo Teorema di Fermat e introdusse la funzione φ. Fattorizzò il 5° numero di Fermat 2 32 +1, trovò 60 coppie di numeri amichevoli e formulò (ma non riuscì a dimostrarla) la legge di reciprocità quadratica.

Fu il primo a introdurre metodi di analisi matematica e a sviluppare la teoria analitica dei numeri. Dimostrò che non solo la serie armonica ∑ (1/n), ma anche una serie della forma

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Anche il risultato ottenuto dalla somma dei reciproci dei numeri primi diverge. La somma degli n termini della serie armonica cresce approssimativamente come log(n), e la seconda serie diverge più lentamente come log[ log(n) ]. Ciò significa che, ad esempio, l'importo reciproci a tutti i numeri primi trovati finora ne verranno forniti solo 4, anche se la serie diverge ancora.

A prima vista, sembra che i numeri primi siano distribuiti in modo abbastanza casuale tra gli interi. Ad esempio, tra i 100 numeri immediatamente prima di 10000000 ci sono 9 numeri primi, e tra i 100 numeri immediatamente dopo questo valore ce ne sono solo 2. Ma su segmenti grandi i numeri primi sono distribuiti in modo abbastanza uniforme. Legendre e Gauss hanno affrontato i problemi della loro distribuzione. Gauss una volta disse a un amico che in ogni 15 minuti liberi conta sempre il numero di primi nei successivi 1000 numeri. Alla fine della sua vita aveva contato tutti i numeri primi fino a 3 milioni. Legendre e Gauss calcolarono ugualmente che per grandi n la densità primaria è 1/log(n). Legendre ha stimato il numero dei numeri primi nell'intervallo da 1 a n as

π(n) = n/(log(n) - 1,08366)

E Gauss è come un integrale logaritmico

π(n) = ∫ 1/log(t) dt

Con un intervallo di integrazione da 2 a n.

L'affermazione sulla densità primaria 1/log(n) è nota come Teorema della distribuzione primaria. Tentarono di dimostrarlo per tutto il XIX secolo e i progressi furono ottenuti da Chebyshev e Riemann. Lo collegarono all'ipotesi di Riemann, un'ipotesi ancora non dimostrata sulla distribuzione degli zeri della funzione zeta di Riemann. La densità dei numeri primi fu dimostrata contemporaneamente da Hadamard e Vallée-Poussin nel 1896.

Ci sono ancora molte domande irrisolte nella teoria dei numeri primi, alcune delle quali risalgono a centinaia di anni fa:

• L’ipotesi dei primi gemelli riguarda un numero infinito di coppie di numeri primi che differiscono tra loro di 2
• Congettura di Goldbach: qualsiasi numero pari, a partire da 4, può essere rappresentato come la somma di due numeri primi
• Esiste un numero infinito di numeri primi della forma n 2 + 1?
• È sempre possibile trovare un numero primo compreso tra n 2 e (n + 1) 2? (il fatto che tra n e 2n esista sempre un numero primo è stato dimostrato da Chebyshev)
• Il numero dei primi di Fermat è infinito? Esistono numeri primi di Fermat dopo il 4?
• esiste? progressione aritmetica di numeri primi consecutivi per una data lunghezza? ad esempio per la lunghezza 4: 251, 257, 263, 269. La lunghezza massima trovata è 26.
• Esiste un numero infinito di serie di tre numeri primi consecutivi in ​​una progressione aritmetica?
• n 2 - n + 41 è un numero primo per 0 ≤ n ≤ 40. Esiste un numero infinito di tali numeri primi? La stessa domanda per la formula n 2 - 79 n + 1601. Questi numeri sono primi per 0 ≤ n ≤ 79.
• Esiste un numero infinito di numeri primi della forma n# + 1? (n# è il risultato della moltiplicazione di tutti i numeri primi minori di n)
• Esiste un numero infinito di numeri primi della forma n# -1 ?
• Esiste un numero infinito di numeri primi della forma n? +1?
• Esiste un numero infinito di numeri primi della forma n? - 1?
• se p è primo, 2 p -1 non contiene sempre quadrati primi tra i suoi fattori?
• la sequenza di Fibonacci contiene un numero infinito di numeri primi?

I numeri primi gemelli più grandi sono 2003663613 × 2 195000 ± 1. Sono costituiti da 58711 cifre e sono stati scoperti nel 2007.

Il numero primo fattoriale più grande (del tipo n! ± 1) è 147855! - 1. È composto da 142891 cifre ed è stato trovato nel 2002.

Il più grande numero primo primoriale (un numero della forma n# ± 1) è 1098133# + 1.

Tag: aggiungi tag

I numeri sono diversi: naturali, razionali, razionali, interi e frazionari, positivi e negativi, complessi e primi, pari e dispari, reali, ecc. Da questo articolo puoi scoprire cosa sono i numeri primi.

Quali numeri sono chiamati “semplici” in inglese?

Molto spesso, gli scolari non sanno a prima vista come rispondere a una delle domande più semplici di matematica, su cosa sia un numero primo. Spesso confondono i numeri primi con i numeri naturali (cioè i numeri che le persone usano quando contano gli oggetti, mentre in alcune fonti iniziano con zero e in altre con uno). Ma questi sono due concetti completamente diversi. I numeri primi sono i numeri naturali, cioè i numeri interi e positivi maggiori di uno e che hanno solo 2 divisori naturali. Inoltre, uno di questi divisori è il numero indicato e il secondo è uno. Ad esempio, tre è un numero primo perché non può essere diviso senza resto per nessun numero diverso da se stesso e uno.

Numeri compositi

L’opposto dei numeri primi sono i numeri composti. Sono anch'essi naturali, anche maggiori di uno, ma non hanno due, ma un numero maggiore di divisori. Quindi, ad esempio, i numeri 4, 6, 8, 9, ecc. sono numeri naturali, compositi, ma non primi. Come puoi vedere, questi sono per lo più numeri pari, ma non tutti. Ma “due” è un numero pari e il “primo numero” di una serie di numeri primi.

Sotto sequenza

Per costruire una serie di numeri primi, è necessario selezionare tra tutti i numeri naturali, tenendo conto della loro definizione, ovvero è necessario agire per contraddizione. È necessario esaminare ciascuno dei numeri naturali positivi per vedere se ha più di due divisori. Proviamo a costruire una serie (sequenza) composta da numeri primi. L'elenco inizia con due, seguito da tre, poiché è divisibile solo per se stesso e per uno. Consideriamo il numero quattro. Ha divisori diversi da quattro e uno? Sì, quel numero è 2. Quindi quattro non è un numero primo. Anche il cinque è primo (non è divisibile per nessun altro numero, eccetto 1 e 5), ma il sei è divisibile. E in generale, se segui tutti i numeri pari, noterai che, ad eccezione del “due”, nessuno di essi è primo. Da ciò concludiamo che i numeri pari, eccetto due, non sono primi. Un'altra scoperta: anche tutti i numeri divisibili per tre, eccetto il tre stesso, pari o dispari, non sono primi (6, 9, 12, 15, 18, 21, 24, 27, ecc.). Lo stesso vale per i numeri divisibili per cinque e sette. Anche tutta la loro moltitudine non è semplice. Riassumiamo. Quindi, i numeri semplici a una cifra includono tutti i numeri dispari tranne uno e nove, e anche i “due” sono numeri pari. Le decine stesse (10, 20,... 40, ecc.) non sono semplici. I numeri primi a due, tre cifre, ecc. possono essere determinati in base ai principi di cui sopra: se non hanno divisori diversi da se stessi e uno.

Teorie sulle proprietà dei numeri primi

Esiste una scienza che studia le proprietà dei numeri interi, compresi i numeri primi. Questa è una branca della matematica chiamata superiore. Oltre alle proprietà degli interi, si occupa anche dei numeri algebrici e trascendenti, nonché di funzioni di varia origine legate all'aritmetica di questi numeri. In questi studi, oltre a quelli elementari e metodi algebrici, vengono utilizzati anche analitici e geometrici. Nello specifico, la “Teoria dei Numeri” si occupa dello studio dei numeri primi.

I numeri primi sono i “mattoni” dei numeri naturali

In aritmetica esiste un teorema chiamato teorema fondamentale. Secondo lei, qualsiasi numero naturale, tranne uno, può essere rappresentato come un prodotto, i cui fattori sono numeri primi, e l'ordine dei fattori è unico, ciò significa che il metodo di rappresentazione è unico. Si chiama fattorizzazione di un numero naturale in fattori primi. C'è un altro nome per questo processo: fattorizzazione dei numeri. Sulla base di ciò, i numeri primi possono essere chiamati “materiale da costruzione”, “blocchi” per costruire i numeri naturali.

Cerca i numeri primi. Test di semplicità

Molti scienziati di epoche diverse hanno cercato di trovare alcuni principi (sistemi) per trovare un elenco di numeri primi. La scienza conosce sistemi chiamati crivello Atkin, crivello Sundartham e crivello Eratostene. Tuttavia, non producono risultati significativi e per trovare i numeri primi viene utilizzato un semplice test. I matematici hanno anche creato algoritmi. Di solito sono chiamati test di primalità. Ad esempio, esiste un test sviluppato da Rabin e Miller. È usato dai crittografi. Esiste anche il test Kayal-Agrawal-Sasquena. Tuttavia, nonostante la sufficiente precisione, è molto difficile da calcolare, il che ne riduce l’importanza pratica.

L’insieme dei numeri primi ha un limite?

L'antico scienziato greco Euclide scrisse nel suo libro “Elementi” che l'insieme dei numeri primi è infinito. Ha detto questo: “Immaginiamo per un momento che i numeri primi abbiano un limite. Quindi moltiplichiamoli tra loro e aggiungiamone uno al prodotto. Il numero risultante da questi azioni semplici, non può essere diviso per nessuno dei numeri primi, perché il resto sarà sempre uno. Ciò significa che esiste qualche altro numero che non è ancora incluso nell'elenco dei numeri primi. Pertanto, la nostra ipotesi non è vera e questo insieme non può avere limiti. Oltre alla dimostrazione di Euclide, esiste una formula più moderna data dal matematico svizzero del XVIII secolo Leonhard Euler. Secondo esso la somma reciproca della somma dei primi n numeri cresce illimitatamente all'aumentare del numero n. Ed ecco la formula del teorema riguardante la distribuzione dei numeri primi: (n) cresce come n/ln (n).

Qual è il numero primo più grande?

Lo stesso Leonard Euler riuscì a trovare il più grande numero primo del suo tempo. Questo è 2 31 - 1 = 2147483647. Tuttavia, nel 2013, è stato calcolato un altro più accurato nell'elenco dei numeri primi: 2 57885161 - 1. Si chiama numero di Mersenne. Ne contiene circa 17 milioni cifre decimali. Come puoi vedere, il numero trovato da uno scienziato del diciottesimo secolo è molte volte inferiore a questo. Dovrebbe essere così, perché Eulero effettuava questo calcolo manualmente, mentre il nostro contemporaneo probabilmente si avvaleva dell'aiuto di un computer. Inoltre, questo numero è stato ottenuto presso la Facoltà di Matematica di uno dei dipartimenti americani. I numeri che prendono il nome da questo scienziato superano il test di primalità di Luc-Lemaire. La scienza, però, non vuole fermarsi qui. La Electronic Frontier Foundation, fondata nel 1990 negli Stati Uniti d'America (EFF), ha offerto una ricompensa in denaro per aver trovato grandi numeri primi. E se fino al 2013 il premio veniva assegnato a quegli scienziati che riuscivano a trovarli tra 1 e 10 milioni di numeri decimali, oggi questa cifra è arrivata da 100 milioni a 1 miliardo. I premi vanno da 150 a 250mila dollari americani.

Nomi di numeri primi speciali

Sono detti speciali quei numeri che sono stati trovati grazie ad algoritmi creati da alcuni scienziati e che hanno superato il test di semplicità. Ecco qui alcuni di loro:

1. Merssen.

4. Cullen.

6. Mills et al.

La semplicità di questi numeri, che prendono il nome dagli scienziati sopra menzionati, viene stabilita utilizzando i seguenti test:

1.Luc-Lemaire.

2. Pepina.

3. Riesel.

4. Billhart-Lemaire-Selfridge e altri.

La scienza moderna non si ferma qui e probabilmente nel prossimo futuro il mondo conoscerà i nomi di coloro che hanno potuto ricevere il premio di 250.000 dollari trovando il numero primo più grande.

Definizione 1. numero primo− è un numero naturale maggiore di uno divisibile solo per se stesso e di 1.

In altre parole, un numero è primo se ha solo due divisori naturali distinti.

Definizione 2. Viene chiamato qualsiasi numero naturale che abbia altri divisori oltre a se stesso e uno un numero composto.

In altre parole, i numeri naturali che non sono numeri primi sono detti numeri composti. Dalla Definizione 1 segue che un numero composto ha più di due fattori naturali. Il numero 1 non è né primo né composto perché ha un solo divisore 1 e inoltre molti teoremi sui numeri primi non valgono per l'unità.

Dalle definizioni 1 e 2 segue che ogni intero positivo maggiore di 1 è un numero primo o un numero composto.

Di seguito è riportato un programma per visualizzare i numeri primi fino a 5000. Compila le celle, fai clic sul pulsante "Crea" e attendi qualche secondo.

Tabella dei numeri primi

Dichiarazione 1. Se P- numero primo e UN qualsiasi numero intero, allora neanche UN diviso per P, O P E UN numeri coprimi.

Veramente. Se P Un numero primo è divisibile solo per se stesso e per 1 se UN non divisibile per P, quindi il più grande divisore comune UN E Pè uguale a 1. Quindi P E UN numeri coprimi.

Dichiarazione 2. Se il prodotto di più numeri di numeri UN 1 , UN 2 , UN 3, ... è divisibile per un numero primo P, quindi secondo almeno uno dei numeri UN 1 , UN 2 , UN 3, ...divisibile per P.

Veramente. Se nessuno dei numeri fosse divisibile per P, poi i numeri UN 1 , UN 2 , UN 3, ... sarebbero numeri coprimi rispetto a P. Ma dal Corollario 3 () ne consegue che il loro prodotto UN 1 , UN 2 , UN 3, ... è anche relativamente primo rispetto a P, il che contraddice lo stato della dichiarazione. Pertanto almeno uno dei numeri è divisibile per P.

Teorema 1. Qualsiasi numero composto è sempre rappresentabile e, inoltre, l'unico modo come prodotto di un numero finito di numeri primi.

Prova. Permettere K numero composto e lasciamo UN 1 è uno dei suoi divisori diverso da 1 e da se stesso. Se UN 1 è composto, quindi ha in aggiunta a 1 e UN 1 e un altro divisore UN 2. Se UN 2 è un numero composto, quindi ha, oltre a 1 e UN 2 e un altro divisore UN 3. Ragionando in questo modo e tenendo conto che dei numeri UN 1 , UN 2 , UN 3 , ... diminuiscono e questa serie contiene un numero finito di termini, raggiungeremo un numero primo P 1 . Poi K può essere rappresentato nella forma

Supponiamo che ci siano due scomposizioni di un numero K:

Perché k=p 1 P 2 P 3 ...divisibile per un numero primo Q 1, allora almeno uno dei fattori, ad esempio P 1 è divisibile per Q 1 . Ma P 1 è un numero primo ed è divisibile solo per 1 e per se stesso. Quindi P 1 =Q 1 (perché Q 1 ≠1)

Allora da (2) possiamo escludere P 1 e Q 1:

Siamo quindi convinti che ogni numero primo che appare come fattore nella prima espansione una o più volte appare anche nella seconda espansione almeno altrettante volte, e viceversa, ogni numero primo che appare come fattore nella seconda espansione appare una o più volte anche nella prima espansione almeno lo stesso numero di volte. Pertanto, qualsiasi numero primo appare come fattore in entrambe le espansioni lo stesso numero di volte e, quindi, queste due espansioni sono le stesse.

Espansione di un numero composto K può essere scritto nella seguente forma

(3)

Dove P 1 , P 2, ... vari numeri primi, α, β, γ ... interi positivi.

Viene chiamata l'espansione (3). espansione canonica numeri.

I numeri primi si trovano in modo non uniforme nella serie dei numeri naturali. In alcune parti della fila ce ne sono di più, in altre meno. Più ci muoviamo lungo la serie dei numeri, meno comuni sono i numeri primi. La domanda sorge spontanea: esiste un numero primo più grande? L'antico matematico greco Euclide dimostrò che esistono infiniti numeri primi. Presentiamo questa dimostrazione di seguito.

Teorema 2. Il numero dei numeri primi è infinito.

Prova. Supponiamo che esista un numero finito di numeri primi e sia il numero primo più grande P. Consideriamo tutti i numeri maggiori P. Per ipotesi dell'affermazione, questi numeri devono essere composti e devono essere divisibili per almeno uno dei numeri primi. Scegliamo un numero che è il prodotto di tutti questi numeri primi più 1:

Numero z Di più P Perché 2p già di più P. P non è divisibile per nessuno di questi numeri primi, perché quando diviso per ciascuno di essi dà un resto di 1. Quindi arriviamo a una contraddizione. Quindi i numeri primi sono infiniti.

Questo teorema è un caso speciale di un teorema più generale:

Teorema 3. Sia data una progressione aritmetica

Quindi qualsiasi numero primo incluso in N, dovrebbe essere incluso in M, quindi dentro N altri fattori primi non inclusi M e, inoltre, questi fattori primi in N sono inclusi non più volte di in M.

È vero anche il contrario. Se ogni fattore primo di un numero N incluso almeno altrettante volte nel numero M, Quello M diviso per N.

Dichiarazione 3. Permettere UN 1 ,UN 2 ,UN 3,... vari numeri primi inclusi M COSÌ

Dove io=0,1,...α , J=0,1,...,β , k=0,1,..., γ . notare che αi accetta α +1 valori, β j accetta β +1 valori, γ k accetta γ +1 valori, ... .

In questo articolo esploreremo numeri primi e composti. Per prima cosa daremo le definizioni dei numeri primi e composti e forniremo anche degli esempi. Successivamente dimostreremo che esistono infiniti numeri primi. Successivamente, scriveremo una tabella di numeri primi e considereremo i metodi per compilare una tabella di numeri primi, prestando particolare attenzione al metodo chiamato crivello di Eratostene. In conclusione, evidenzieremo i punti principali di cui tenere conto per dimostrare che un dato numero è primo o composto.

Navigazione della pagina.

Numeri primi e compositi: Definizioni ed esempi

I concetti di numeri primi e numeri composti si riferiscono a numeri maggiori di uno. Tali numeri interi, a seconda del numero dei loro divisori positivi, sono divisi in numeri primi e composti. Quindi per capire definizioni di numeri primi e composti, devi avere una buona conoscenza di cosa sono i divisori e i multipli.

Definizione.

numeri primi sono numeri interi, unità grandi, che hanno solo due divisori positivi, vale a dire se stessi e 1.

Definizione.

Numeri compositi sono numeri interi, grandi, che hanno almeno tre divisori positivi.

Separatamente, notiamo che il numero 1 non si applica né ai numeri primi né ai numeri composti. L'unità ha un solo divisore positivo, che è il numero 1 stesso. Ciò distingue il numero 1 da tutti gli altri numeri interi positivi che hanno almeno due divisori positivi.

Considerando che gli interi positivi sono , e che uno ha un solo divisore positivo, possiamo dare altre formulazioni delle definizioni esposte di numeri primi e composti.

Definizione.

numeri primi sono numeri naturali che hanno solo due divisori positivi.

Definizione.

Numeri compositi sono numeri naturali che hanno più di due divisori positivi.

Si noti che ogni intero positivo maggiore di uno è un numero primo o un numero composto. In altre parole, non esiste un singolo intero che non sia né primo né composto. Ciò deriva dalla proprietà di divisibilità, la quale afferma che i numeri 1 e a sono sempre divisori di qualsiasi intero a.

Sulla base delle informazioni contenute nel paragrafo precedente, possiamo dare la seguente definizione di numeri composti.

Definizione.

I numeri naturali che non sono primi vengono chiamati composito.

Diamo esempi di numeri primi e composti.

Esempi di numeri compositi includono 6, 63, 121 e 6.697. Anche questa affermazione necessita di chiarimenti. Il numero 6, oltre ai divisori positivi 1 e 6, ha anche i divisori 2 e 3, poiché 6 = 2 3, quindi 6 è veramente un numero composto. I fattori positivi di 63 sono i numeri 1, 3, 7, 9, 21 e 63. Il numero 121 è uguale al prodotto 11·11, quindi i suoi divisori positivi sono 1, 11 e 121. E il numero 6.697 è composto, poiché i suoi divisori positivi, oltre a 1 e 6.697, sono anche i numeri 37 e 181.

In conclusione di questo punto, vorrei anche attirare l’attenzione sul fatto che i numeri primi e i numeri coprimi sono tutt’altro che la stessa cosa.

Tabella dei numeri primi

I numeri primi, per comodità del loro ulteriore utilizzo, sono registrati in una tabella chiamata tabella dei numeri primi. Sotto è tabella dei numeri primi fino a 1.000.

Sorge una domanda logica: “Perché abbiamo riempito la tabella dei numeri primi solo fino a 1.000, non è possibile creare una tabella di tutti i numeri primi esistenti”?

Rispondiamo prima alla prima parte di questa domanda. Per la maggior parte dei problemi che richiedono l'uso di numeri primi, saranno sufficienti i numeri primi entro il migliaio. In altri casi, molto probabilmente, dovrai ricorrere ad alcune soluzioni particolari. Anche se possiamo certamente creare una tabella di numeri primi fino ad un intero positivo finito arbitrariamente grande, sia esso 10.000 o 1.000.000.000, nel prossimo paragrafo parleremo dei metodi per creare tabelle di numeri primi, in particolare vedremo un metodo chiamato.

Consideriamo ora la possibilità (o meglio, l'impossibilità) di compilare una tabella di tutti i numeri primi esistenti. Non possiamo fare una tabella di tutti i numeri primi perché i numeri primi sono infiniti. L'ultima affermazione è un teorema che dimostreremo dopo il seguente teorema ausiliario.

Teorema.

Il più piccolo divisore positivo diverso da 1 di un numero naturale maggiore di uno è un numero primo.

Prova.

Permettere a è un numero naturale maggiore di uno e b è il più piccolo divisore positivo di a diverso da uno. Dimostriamo che b è un numero primo per assurdo.

Supponiamo che b sia un numero composto. Poi c'è un divisore del numero b (denotiamolo b 1), che è diverso sia da 1 che da b. Se teniamo conto anche che il valore assoluto del divisore non supera il valore assoluto del dividendo (lo sappiamo dalle proprietà della divisibilità), allora la condizione 1 deve essere soddisfatta

Poiché il numero a è divisibile per b secondo la condizione, e abbiamo detto che b è divisibile per b 1, il concetto di divisibilità ci permette di parlare dell'esistenza di interi q e q 1 tali che a=b q e b=b 1 q 1 , da dove a= b 1 ·(q 1 ·q) . Ne consegue che il prodotto di due interi è un intero, allora l'uguaglianza a=b 1 ·(q 1 ·q) indica che b 1 è un divisore del numero a. Tenendo conto delle disuguaglianze di cui sopra 1

Ora possiamo dimostrare che i numeri primi sono infiniti.

Teorema.

Esistono infiniti numeri primi.

Prova.

Supponiamo che non sia così. Cioè, supponiamo che ci siano solo n numeri primi, e che questi numeri primi siano p 1, p 2, ..., p n. Mostriamo che possiamo sempre trovare un numero primo diverso da quelli indicati.

Consideriamo il numero p uguale a p 1 ·p 2 ·…·p n +1. È chiaro che questo numero è diverso da ciascuno dei numeri primi p 1, p 2, ..., p n. Se il numero p è primo il teorema è dimostrato. Se questo numero è composto, allora in virtù del teorema precedente esiste un divisore primo di questo numero (lo denotiamo p n+1). Mostriamo che questo divisore non coincide con nessuno dei numeri p 1, p 2, ..., p n.

Se così non fosse allora, secondo le proprietà di divisibilità, il prodotto p 1 ·p 2 ·…·p n sarebbe diviso per p n+1. Ma il numero p è divisibile anche per p n+1, pari alla somma p 1 ·p 2 ·…·p n +1. Ne consegue che p n+1 deve dividere il secondo termine di questa somma, che è uguale a uno, ma questo è impossibile.

Pertanto è stato dimostrato che è sempre possibile trovare un nuovo numero primo che non sia compreso tra nessun numero primo predeterminato. Pertanto i numeri primi sono infiniti.

Quindi, poiché esiste un numero infinito di numeri primi, quando compili tabelle di numeri primi, ti limiti sempre dall'alto a un numero, solitamente 100, 1.000, 10.000, ecc.

Setaccio di Eratostene

Ora discuteremo come creare tabelle di numeri primi. Supponiamo di dover creare una tabella dei numeri primi fino a 100.

Il metodo più ovvio per risolvere questo problema è controllare in sequenza gli interi positivi, iniziando da 2 e terminando con 100, per la presenza di un divisore positivo maggiore di 1 e minore del numero da testare (dalle proprietà di divisibilità che conosciamo che il valore assoluto del divisore non superi il valore assoluto del dividendo, diverso da zero). Se tale divisore non viene trovato, il numero da testare è primo e viene inserito nella tabella dei numeri primi. Se viene trovato un tale divisore, il numero da testare è composto; NON viene inserito nella tabella dei numeri primi. Successivamente si passa al numero successivo, sul quale viene controllata in modo simile la presenza di un divisore.

Descriviamo i primi passi.

Iniziamo dal numero 2. Il numero 2 non ha divisori positivi diversi da 1 e 2. Pertanto è semplice, quindi lo inseriamo nella tabella dei numeri primi. Qui va detto che 2 è il numero primo più piccolo. Passiamo al numero 3. Il suo possibile divisore positivo diverso da 1 e 3 è il numero 2. Ma 3 non è divisibile per 2, quindi 3 è un numero primo e deve essere incluso anche lui nella tabella dei numeri primi. Passiamo al numero 4. I suoi divisori positivi diversi da 1 e 4 possono essere i numeri 2 e 3, controlliamoli. Il numero 4 è divisibile per 2, quindi 4 è un numero composto e non necessita di essere incluso nella tabella dei numeri primi. Tieni presente che 4 è il numero composto più piccolo. Passiamo al numero 5. Controlliamo se almeno uno dei numeri 2, 3, 4 è il suo divisore. Poiché 5 non è divisibile per 2, 3 o 4, allora è primo e deve essere scritto nella tabella dei numeri primi. Poi c'è il passaggio ai numeri 6, 7 e così via fino a 100.

Questo approccio alla compilazione di una tabella di numeri primi è tutt’altro che ideale. In un modo o nell'altro, ha il diritto di esistere. Nota che con questo metodo di costruzione di una tabella di numeri interi, puoi utilizzare i criteri di divisibilità, che accelereranno leggermente il processo di ricerca dei divisori.

Esiste un modo più conveniente per creare una tabella di numeri primi, chiamato. La parola "setaccio" presente nel nome non è casuale, poiché le azioni di questo metodo aiutano, per così dire, a "setacciare" numeri interi e unità grandi attraverso il setaccio di Eratostene per separare quelli semplici da quelli compositi.

Mostriamo il crivello di Eratostene in azione durante la compilazione di una tabella dei numeri primi fino a 50.

Per prima cosa, scrivi i numeri 2, 3, 4, ..., 50 in ordine.

Il primo numero scritto, 2, è primo. Ora, dal numero 2, ci spostiamo in sequenza verso destra di due numeri e cancelliamo questi numeri fino a raggiungere la fine della tabella dei numeri in fase di compilazione. In questo modo verranno cancellati tutti i numeri multipli di due.

Il primo numero dopo il 2 che non è barrato è 3. Questo numero è primo. Ora, dal numero 3, ci spostiamo in sequenza a destra di tre numeri (tenendo conto dei numeri già cancellati) e li cancelliamo. Questo cancellerà tutti i numeri che sono multipli di tre.

Il primo numero dopo il 3 che non viene cancellato è 5. Questo numero è primo. Ora dal numero 5 ci spostiamo costantemente a destra di 5 numeri (prendiamo in considerazione anche i numeri cancellati in precedenza) e li cancelliamo. Questo cancellerà tutti i numeri che sono multipli di cinque.

Successivamente, cancelliamo i numeri che sono multipli di 7, poi multipli di 11 e così via. Il processo termina quando non ci sono più numeri da cancellare. Di seguito la tabella completa dei numeri primi fino a 50, ottenuta utilizzando il crivello di Eratostene. Tutti i numeri non barrati sono primi e tutti i numeri barrati sono composti.

Formuliamo e dimostriamo anche un teorema che accelererà il processo di compilazione di una tabella di numeri primi utilizzando il crivello di Eratostene.

Teorema.

Il più piccolo divisore positivo di un numero composto a diverso da uno non supera , dove proviene da a .

Prova.

Indichiamo con la lettera b il più piccolo divisore di un numero composto a diverso da uno (il numero b è primo, come segue dal teorema dimostrato all'inizio del paragrafo precedente). Allora esiste un intero q tale che a=b·q (qui q è un intero positivo, che segue dalle regole della moltiplicazione degli interi), e (per b>q la condizione che b sia il minimo divisore di a è violata , poiché q è anche un divisore del numero a per l'uguaglianza a=q·b ). Moltiplicando entrambi i membri della disuguaglianza per un positivo e un numero intero maggiore di uno (questo è consentito), otteniamo , da cui e .

Cosa ci dà il teorema dimostrato riguardo al crivello di Eratostene?

In primo luogo, cancellando i numeri compositi che sono multipli di un numero primo b dovrebbe iniziare con un numero uguale a (questo deriva dalla disuguaglianza). Ad esempio, i numeri multipli di due dovrebbero iniziare con il numero 4, i multipli di tre con il numero 9, i multipli di cinque con il numero 25 e così via.

In secondo luogo, compilare una tabella dei numeri primi fino al numero n utilizzando il crivello di Eratostene può essere considerato completo quando tutti i numeri composti che sono multipli di numeri primi non superiori a . Nel nostro esempio n=50 (poiché stiamo facendo una tabella di numeri primi fino a 50) e, quindi, il crivello di Eratostene dovrebbe eliminare tutti i numeri composti che sono multipli dei numeri primi 2, 3, 5 e 7 che non non superare la radice quadrata aritmetica di 50. Cioè non abbiamo più bisogno di cercare e cancellare i numeri che sono multipli dei numeri primi 11, 13, 17, 19, 23 e così via fino a 47, poiché saranno già cancellati come multipli dei numeri primi più piccoli 2 , 3, 5 e 7 .

Questo numero è primo o composto?

Alcuni compiti richiedono di scoprire se un dato numero è primo o composto. In generale, questo compito è tutt'altro che semplice, soprattutto per i numeri la cui scrittura è composta da un numero significativo di caratteri. Nella maggior parte dei casi, devi cercare un modo specifico per risolverlo. Cercheremo comunque di dare una direzione al filone di pensiero per casi semplici.

Naturalmente puoi provare a utilizzare i test di divisibilità per dimostrare che un dato numero è composto. Se, ad esempio, qualche test di divisibilità mostra che un dato numero è divisibile per un intero positivo maggiore di uno, allora il numero originale è composto.

Esempio.

Dimostra che 898.989.898.989.898.989 è un numero composto.

Soluzione.

La somma delle cifre di questo numero è 9·8+9·9=9·17. Poiché il numero pari a 9·17 è divisibile per 9, allora per divisibilità per 9 possiamo dire che anche il numero originale è divisibile per 9. Pertanto è composito.

Uno svantaggio significativo di questo approccio è che i criteri di divisibilità non consentono di dimostrare l’primità di un numero. Pertanto, quando si prova un numero per vedere se è primo o composto, è necessario procedere diversamente.

L'approccio più logico è provare tutti i possibili divisori di un dato numero. Se nessuno dei possibili divisori è un vero divisore di un dato numero, allora questo numero sarà primo, altrimenti sarà composto. Dai teoremi dimostrati nel paragrafo precedente consegue che i divisori di un dato numero a vanno ricercati tra i numeri primi non superiori a . Pertanto, un dato numero a può essere diviso in sequenza per i numeri primi (che sono convenientemente presi dalla tabella dei numeri primi), cercando di trovare il divisore del numero a. Se viene trovato un divisore, il numero a è composto. Se tra i numeri primi non superiori a , non esiste alcun divisore del numero a, allora il numero a è primo.

Esempio.

Numero 11 723 semplice o composto?

Soluzione.

Scopriamo fino a quale numero primo possono essere i divisori del numero 11.723. Per fare questo, valutiamo.

È abbastanza ovvio , poiché 200 2 =40.000 e 11.723<40 000 (при необходимости смотрите статью confronto di numeri). Pertanto, i possibili fattori primi di 11.723 sono inferiori a 200. Già questo rende il nostro compito molto più semplice. Se non lo sapessimo, dovremmo esaminare tutti i numeri primi non fino a 200, ma fino al numero 11.723.

Se lo desideri, puoi valutare in modo più accurato. Poiché 108 2 =11.664 e 109 2 =11.881, allora 108 2<11 723<109 2 , следовательно, . Pertanto, qualsiasi numero primo inferiore a 109 è potenzialmente un fattore primo del numero dato 11.723.

Ora divideremo in sequenza il numero 11.723 nei numeri primi 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Se il numero 11.723 viene diviso per uno dei numeri primi scritti, sarà composto. Se non è divisibile per nessuno dei numeri primi scritti, allora il numero originale è primo.

Non descriveremo l'intero processo di divisione monotono e monotono. Diciamo subito che 11.723