Primtalsräknare

Q: Vad är ett primtal?

Ett primtal är ett positivt heltal strikt större än 1 som har exakt två olika positiva delare: 1 och sig självt. Vanliga exempel är 2, 3, 5, 7, 11, 13 och 97.

Q: Varför räknas inte 0 och 1 som primtal?

Enligt den matematiska definitionen måste ett primtal ha exakt två olika positiva delare. Talet 1 har endast en positiv delare (sig självt) och uppfyller inte kravet. Talet 0 har oändligt många delare eftersom 0 delat med vilket nollskilt heltal som helst blir 0 med rest 0.

Q: Varför är 2 det enda jämna primtalet?

Varje jämnt heltal större än 2 är delbart med 2 utöver 1 och sig självt (t.ex. 4 = 2 × 2, 6 = 2 × 3). Eftersom de har minst tre delare är alla jämna tal större än 2 sammansatta. 2 är det enda jämna talet med exakt två delare.

Q: Är 7 och 9 båda primtal?

Nej. 7 är ett primtal eftersom dess enda delare är 1 och 7. Men 9 är ett sammansatt tal eftersom det har tre delare: 1, 3 och 9 (3 × 3 = 9).

Q: Hur kontrollerar man om ett stort tal är ett primtal?

För mindre tal testar datorer primtalsdelare upp till kvadratrotsgränsen ⌊√n⌋. För 64-bitars heltal upp till 18 kvintiljoner utvärderar deterministiska Miller-Rabin-tester 7 matematiskt bevisade baser (2, 325, 9375, 28178, 450775, 9780504, 1795265022) med 100 % matematisk säkerhet.

Q: Vilket är det största primtalet?

Det finns inget största primtal. Omkring år 300 f.Kr. bevisade Euklides att det finns oändligt många primtal. Det finns dock ett största för närvarande känt primtal upptäckt via GIMPS: 2^136 279 841 − 1, som innehåller 41 024 320 siffror.

Q: Vad är relativt prima (koprima) tal?

Två heltal är relativt prima om deras största gemensamma delare (SGD) är 1. Varken det ena eller det andra talet behöver vara ett primtal i sig. Till exempel är 8 (2³) och 9 (3²) båda sammansatta, men sgd(8, 9) = 1, vilket gör dem relativt prima.

Q: Hur många primtal finns det mellan 1 och 100?

Det finns exakt 25 primtal mellan 1 och 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 och 97. Deras summa är 1 060.

Q: Hur fungerar primtalsfaktorisering på en Casio fx-991ES räknare?

På kompatibla modeller som Casio fx-991ES PLUS eller fx-115ES PLUS anger du heltalet, trycker på [=], trycker sedan på [SHIFT] följt av [FACT]-tangenten. Skärmen visar omedelbart talets primtalsfaktorisering.

Beräkningsarkitektur

Hur Vår Primtalsräknare Fungerar

Byggd från grunden för maximal hastighet, matematisk visshet och pedagogisk tydlighet.

En primtalsräknare är ett matematiskt precisionsverktyg som avgör om ett givet heltal är ett primtal eller ett sammansatt tal. Den testar delbarhet, verifierar att talet har exakt två positiva delare, beräknar dess primfaktorer och identifierar närliggande primtal med full matematisk visshet och steg-för-steg-förklaringar.

Interaktivt Flödesschema för Beräkningen

Klicka på ett steg för att granska beräkningen i detalj:

Live Input:

1

Mata in ett Heltal

Skriv in ett heltal i inmatningsfältet eller klicka på något av våra färdiga exempel.

2

Klicka Kontrollera

Matematikmotorn utför provdivision upp till kvadratroten eller deterministiska 64-bitars tester.

3

Läs av Resultatet

Se det bevisade primtalsutlåtandet, delningsstegen, primfaktorerna och intilliggande primtal.

Komplett Verktygslåda

Primtalsverktyg

Specialiserade räknare utformade för specifika matematiska undersökningar.

Showing 25 of 25 tools

Lists & Ranges

Primtalsgenerator

Skapa kompletta listor och tabeller över primtal med smidig kopiering till CSV.

Öppna Verktyg →

Check & Factors

Primtalsfaktorisering

Faktorisera sammansatta tal i primtalsfaktorer med interaktivt faktorträd och divisionsstege.

Öppna Verktyg →

Lists & Ranges

Nästa och Föregående Primtal

Hitta de närmast belägna primtalen ovan och under ett givet tal med exakt avstånd.

Öppna Verktyg →

Lists & Ranges

N:te Primtalet

Bestäm valfritt primtal efter dess ordningsnummer i talföljden, från 1:a (2) till 10 000:e (104 729).

Öppna Verktyg →

Σ

Lists & Ranges

Primtalssumma

Beräkna den exakta summan av alla primtal i ett intervall med BigInt-aritmetik.

Öppna Verktyg →

Lists & Ranges

Primtal Mellan Två Tal

Räkna och lista primtal mellan två tal med täthetsanalys och tvillingprimtal.

Öppna Verktyg →

Check & Factors

Kontroll av Relativt Primiska Tal

How to Check If a Number Is Prime

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

Öppna Verktyg →

Matematiska Grunder

Vad Är ett Primtal?

De fundamentala och odelbara byggstenarna för alla heltal och aritmetiken.

Geometrisk Modell: Rektangel-Primtalstestet

Ett tal n är ett primtal om n brickor enbart kan bilda en enda rad av storleken 1 × n. Kan de bilda en rektangel med bredd > 1 är talet sammansatt.

Tal (n):

Prova Exempel:

12 is Composite: 3 rectangular arrangements possible

Displaying a 3 × 4 rectangular array with zero remainder.

Definition och Exempel

I matematiken är ett primtal ett positivt heltal strikt större än 1 som har exakt två positiva delare: 1 och talet självt.

De tio första primtalen är: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Varje heltal större än 1 som inte är ett primtal kallas för ett sammansatt tal, eftersom det kan bildas genom multiplikation av mindre primtal.

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.

Varför 0 och 1 Inte Är Primtal

0 är varken primtal eller sammansatt: det har oändligt många delare eftersom 0 delat med vilket nollskilt tal som helst ger 0.

1 är varken primtal eller sammansatt: det har bara en positiv delare (sig självt). Om 1 vore ett primtal skulle aritmetikens fundamentalsats förlora sin entydiga primtalsfaktorisering.

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

Primtal vs. Sammansatta Tal

Viktiga matematiska skillnader mellan de två klasserna av positiva heltal:

Egenskap	Primtal	Sammansatta Tal
Definition	Exakt två distinkta positiva delare: 1 och talet självt	Fler än två positiva delare
Antal delare	Strikt 2 delare	3 eller fler delare
Minsta medlem	2 (det enda jämna primtalet)	4 (2 × 2)
Primtalsfaktorisering	Talet självt (p¹)	Unik produkt av primtalspotenser (p₁ᵃ × p₂ᵇ …)
Jämna heltal	Endast 2 är primtal; alla andra jämna tal är sammansatta	Alla jämna heltal > 2 (4, 6, 8, 10, 12…)
Exempel	2, 3, 5, 7, 11, 13, 97, 101	4, 6, 8, 9, 12, 51, 91, 100

Varför 2 Är det Enda Jämna Primtalet

Ett jämnt tal är delbart med 2. Talet 2 har bara två delare: 1 och 2, vilket uppfyller definitionen. Varje jämnt tal n > 2 är delbart med 1, 2 och n, och har därmed minst tre delare.

Är 7 och 9 Primtal?

7 är ett primtal: dess enda delare är 1 och 7. 9 är INTE ett primtal: 9 är sammansatt eftersom det är delbart med 3 (3 × 3 = 9). Att vara udda innebär inte automatiskt att ett tal är ett primtal!

Metoder och Bevis

Hur Man Kontrollerar om ett Tal Är ett Primtal

Den klassiska kvadratrotsgränsen och stegvisa algoritmer.

Interaktiv Simulator: Kvadratrotsgräns och Provdivision

Se hur gränsen ⌊√n⌋ kraftigt minskar antalet delningstester som krävs för att bevisa primalitet.

Testtal (n):

Prova testfall:

Kvadratrotsgräns

√97 ≈ 9.85

p ≤ 7 (⌊√97⌋ = 9)

Primtal att testa

4

2, 3, 5, 7

Tester sparade genom gräns

92

92 / 96 (95.8%)

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

Delbarhetskontroller upp till √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.

Testa Delbarhet Upp till √n

För att kontrollera om ett heltal n är ett primtal behöver du inte testa alla tal upp till n. Det räcker matematiskt att enbart testa primtal upp till kvadratroten: d ≤ ⌊√n⌋.

Varför det fungerar: Delare uppträder alltid i par (a × b = n). Om båda faktorerna vore större än √n skulle deras produkt överstiga n, vilket är omöjligt.

Löst exempel: Är 97 ett primtal?

Beräkna √97 ≈ 9,848. Vi testar endast primtal ≤ 9.
Primtalen att testa är: 2, 3, 5, 7.
97 ÷ 2 = 48 R 1 (Ej delbart, slutar på udda siffran 7).
97 ÷ 3 = 32 R 1 (Ej delbart, siffersumman 9+7=16 är ej delbar med 3).
97 ÷ 5 = 19 R 2 (Ej delbart, slutar inte på 0 eller 5).
97 ÷ 7 = 13 R 6 (Ej delbart).
Alla primtalskandidater ≤ √97 misslyckades med att dela 97 jämnt. Därför är 97 bevisat ett primtal!

Löst exempel: Varför är 91 sammansatt?

Beräkna √91 ≈ 9,539. Vi testar endast primtal ≤ 9.
Primtalen att testa är: 2, 3, 5, 7.
91 ÷ 2 = 45 R 1 (Ej delbart).
91 ÷ 3 = 30 R 1 (Ej delbart, siffersumma 9+1=10).
91 ÷ 5 = 18 R 1 (Ej delbart, slutar inte på 0 eller 5).
91 ÷ 7 = 13 R 0 (Jämnt delbart!).
Eftersom 7 är en delare är 91 sammansatt: 91 = 7 × 13.

Mentala genvägar för delbarhet

Du kan snabbt utesluta många sammansatta kandidater med enkla huvudräkningsregler:

Delbart med 2: Sista siffran är jämn (0, 2, 4, 6, 8).
Delbart med 3: Summan av alla siffror är en multipel av 3 (t.ex. för 51: 5+1=6, så 51 ÷ 3 = 17).
Delbart med 5: Sista siffran är 0 eller 5.
Regeln 6k ± 1: Varje primtal större än 3 kan skrivas som 6k − 1 eller 6k + 1. Även om inte alla tal på denna form är primtal, är varje tal som inte har denna form garanterat sammansatt!

Huvudräkning och Genvägar

Delbarhetsregler och Primalitetsgenvägar

Grundläggande minnestrick för att snabbt sortera bort sammansatta tal utan miniräknare.

Interaktivt Diagram: Modulo-6-Hjulet (6k ± 1)

Alla primtal större än 3 hamnar uteslutande i formen 6k + 1 eller 6k - 1.

Testa heltal (n):

Prova exempel:

Primtalsregeln 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).

Delare	Delbarhetsregel & Tankesätt	Praktiskt Exempel
2	Sista siffran är jämn: 0, 2, 4, 6 eller 8.	248 slutar på 8 → Delbart med 2
3	Summan av alla enskilda siffror är delbar med 3.	453 → 4+5+3 = 12 (delbart med 3) → Delbart med 3
4	Talet som bildas av de två sista siffrorna är delbart med 4.	3 116 slutar på 16 (16 ÷ 4 = 4) → Delbart med 4
5	Sista siffran är antingen 0 eller 5.	895 slutar på 5 → Delbart med 5
6	Talet klarar både testet för 2 (jämnt) och testet för 3 (siffersumma).	732 är jämnt och 7+3+2 = 12 → Delbart med 6
7	Dubblera sista siffran och subtrahera den från resten. Resultatet är delbart med 7.	672 → 67 − (2×2) = 63 (63 ÷ 7 = 9) → Delbart med 7
8	Talet som bildas av de tre sista siffrorna är delbart med 8.	5 128 slutar på 128 (128 ÷ 8 = 16) → Delbart med 8
9	Summan av alla enskilda siffror är delbar med 9.	2 871 → 2+8+7+1 = 18 (18 ÷ 9 = 2) → Delbart med 9
11	Den alternerande siffersumman (addera-subtrahera-addera...) är 0 eller en multipel av 11.	913 → 9 − 1 + 3 = 11 → Delbart med 11
13	Addera 4 gånger sista siffran till den återstående delen. Summan är delbar med 13.	299 → 29 + (9×4) = 65 (65 ÷ 13 = 5) → Delbart med 13

Primtalsregeln 6k ± 1

Alla primtal större än 3 hamnar uteslutande i formen 6k + 1 eller 6k - 1.

6k − 1 | 6k + 1

Varför detta är garanterat: Varje heltal kan delas in i en av sex former: 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5 (vilket är 6(k+1)−1).

6k, 6k+2, 6k+4 är alltid jämna (delbara med 2).
6k+3 är alltid delbart med 3.

Viktig varning: Detta är ett nödvändigt villkor, inte ett tillräckligt. Även om varje primtal > 3 har denna form, är vissa tal på denna form sammansatta (t.ex. 25 = 6(4)+1 och 35 = 6(6)−1). Verifiera alltid kandidater med begränsad provdivision.

Varför Det Inte Finns Någon Enkel Primtalsformel

År 1772 upptäckte Leonhard Euler det anmärkningsvärda kvadratiska polynomet f(n) = n² + n + 41 som endast ger primtal för varje heltal n = 0, 1, 2, ..., 39 (40 på varandra följande primtal: 41, 43, 47, 53, 61, ..., 1601).

f(n) = n² + n + 41

Men vid n = 40 ger polynomet 40² + 40 + 41 = 1 681 = 41², vilket bevisar att inget icke-konstant algebraiskt polynom någonsin kan generera uteslutande primtal i oändlighet.

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

Visuell Rutnätsöversikt

1 till 100 Primtalstabell

Interaktiv 10×10-tabell. Använd Eratosthenes såll-simulator för att följa hur sammansatta tal utesluts steg för steg.

Primtal (1–100) Σ = 1,060

Primtal (25 tal: 2, 3, 5, 7, 11, … 97)

Sammansatt (74 tal: multiplar av testade primtal)

Ingetdera (1) (Enhetselement: exakt 1 delare)

Följ den antika metoden: stryk multiplar av 2, 3, 5 och 7 för att få fram alla 25 primtal.

Utökad Katalog

Primtal från 1 till 1 000

Det finns exakt 168 primtal mellan 1 och 1 000.

Interaktivt Diagram: Fördelning per Hundratal

Klicka på en stapel för att filtrera de 168 primtalen.

Visar 168 bevisade primtal (1 till 1000) (Σ = 76,127)

Visa alla 168 Primtal upp till 1 000 ▾

Klicka på valfritt primtal nedan för att ladda det i kalkylatorn.

Följdens Milstolpar

Viktiga Milstolpar Bland Primtalen

Dessa referensprimtal markerar centrala gränser inom talteorin och beräkningsvetenskapen.

Ordningsnummer (n):

Noterbara milstolpar:

N:te Primtalsfinnare & Asymptotisk Tillväxtkurva p(100) = 541 · 100 × ln(100) ≈ 461

Slide Rank (1–10,000):

Exact p(n) n · ln(n)

Värde för N:te primtalet

541

p(100)

Intilliggande Primtal

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

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

Primtalsföljdens rang

#100

OEIS-följd A000040

Viktiga milstolpar i primtalsföljden

Dessa referensprimtal markerar viktiga gränser inom matematik, beräkningstester och talteori:

#1 → 2

p₁ = 2

Det minsta primtalet, det första positiva primtalet och det enda jämna primtalet som existerar. Alla efterföljande primtal är udda heltal.

#25 → 97

p₂₅ = 97

Det största tvåsiffriga primtalet. Exakt 25 primtal finns mellan 1 och 100, vilket utgör 25 % av alla heltal i bas 10 upp till 100.

#100 → 541

p₁₀₀ = 541

Milstolpen det 100:e primtalet. Markerar fullbordandet av de första hundra primtalen, med en total primtalstäthet på 18,5 % över detta intervall.

#1,000 → 7,919

p₁₀₀₀ = 7,919

Det tusende primtalet. Bevisar att primtal blir allt glesare när talen växer: det krävs 7 919 heltal för att hitta 1 000 primtal (12,6 % täthet).

#5,000 → 48,611

p₅₀₀₀ = 48,611

Det femtusende primtalet. Ligger precis under gränsen 50 000 och uppvisar en lokal täthet på cirka 10,3 %.

#10,000 → 104,729

p₁₀₀₀₀ = 104,729

Riktmärket det 10 000:e primtalet. Vår omedelbara tabellslagning täcker alla primtal upp till denna gräns utan serverfördröjning.

Analytisk Talteori

Primtalsfunktionen π(x) och Täthet

Upptäck hur primtalens frekvens avtar och fördjupa dig i Gauss primtalssats.

Ange övre gräns (x):

Förvalda gränser:

Interaktiv Täthetsmätare & Förloppsindikator Primtalstäthet: 16.80% (~1/6)

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

Exakt π(x)-antal

168

Primtal strikt ≤ x (≤ 1,000)

Primtalstäthet

16.80%

Procentandel heltal som är primtal

Gauss PNT-uppskattning

144.76

Relativt Fel (%): −13.8%

Antal Primtal per Tiotals-potenser

När talen ökar blir primtalen glesare, men ändå finns det oändligt många. Lägg märke till hur primtalssatsens approximation x / ln(x) konvergerar närmare i relativ procentandel när x växer:

Övre Gräns (x)	Exakt π(x)	Täthet (%)	Gauss PNT: x / ln(x)	Relativt Fel (%)
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%

Vad Betyder Funktionen π(x)?

Inom talteorin syftar π(x) inte på den geometriska konstanten π ≈ 3,14159. Istället antog 1700-talsmatematiker ledda av Carl Friedrich Gauss den grekiska bokstaven π (från plēthos, som betyder "mängd") för att beteckna primtalsräkningsfunktionen: det exakta antalet primtal som är mindre än eller lika med x.

Till skillnad från algebraiska funktioner är π(x) en trappstegsfunktion som ökar med 1 varje gång x passerar ett primtal.

Primtalssatsen (PNT)

Primtalssatsen, som bevisades oberoende av varandra år 1896 av Jacques Hadamard och Charles Jean de la Vallée Poussin, säger att när x går mot oändligheten följer fördelningen av primtal:

π(x) ~ x / ln(x)

Denna sats avslöjar att sannolikheten för att ett slumpmässigt valt heltal nära x är ett primtal är ungefär 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).

Intervallanalys

Hitta Primtal i ett Intervall

Hitta, räkna och beräkna den exakta BigInt-summan av primtalen mellan två valfria tal.

Starttal:

Sluttal:

Förval:

Hitta Primtal i ett Intervall Primtalstäthet: 25.0%

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

Antal Primtal

25

π(end) − π(start−1)

Kumulativ Summa

1,060

Exakt BigInt-summa

Intervallgränser

2 … 97

Inklusiva gränser

Intilliggande Primtal

Hitta Nästa och Föregående Primtal

Identifiera de direkt angränsande primtalen, beräkna avståndet och hitta det största primtalet ≤ n.

Ange valfritt positivt heltal (n):

Prova exempel:

Interaktivt Diagram: Avståndsspår Mellan Primtal 89 (Δ = 1)

n: 90

Föregående primtal (p < n)

89

Δ = −1

n

90

Bevisat sammansatt

Nästa primtal (p > n)

97

Δ = +7

Närmaste primtal 89 (Δ = 1)

max(p ≤ n) 89

Öppna Verktyg →

Strikta Grannar vs Inkluderande Gränser

När man hittar intilliggande primtal kräver matematisk precision att man skiljer mellan strikt intilliggande primtal och inklusiva gränser:

Strikt föregående primtal (p < n): Det största primtalet som är strikt mindre än n. För n = 97 är föregående primtal 89.
Strikt nästa primtal (p > n): Det minsta primtalet som är strikt större än n. För n = 97 är nästa primtal 101.
Största primtal ≤ n: Om n i sig är ett primtal (som 97), är det största primtalet ≤ 97 lika med 97. Om n är sammansatt (som 90), är det 89.

Bertrands Postulat & Lika Avstånd

Hur långt borta kan nästa primtal vara? År 1850 bevisade Pafnutij Tjebysjov Bertrands postulat: för varje heltal n > 3 finns det alltid minst ett primtal p sådant att:

n < p < 2n − 2

Lika avstånd (oavgjort): För vissa tal ligger föregående och nästa primtal på exakt samma avstånd. Till exempel, för n = 6 är föregående 5 (avstånd 1) och nästa är 7 (avstånd 1). Båda är närmaste primtal!

Faktorisering och Steg

Primtalsfaktorisering med Lösning

Hur varje sammansatt tal kan delas upp unikt i potenser av primtal.

Interaktivt faktorträd & divisionsstege

Ange valfritt heltal för att generera både dess visuella SVG-faktorträd och en divisionsstege steg för steg.

Tal (n):

Prova exempel:

Kanonisk Exponentialform

360 = 2³ × 3² × 5

Komplett Faktoriseringsräknare →

Talteori & SGD

Kontroll av Relativt Primiska Tal (Coprime)

Kontrollera om två tal saknar gemensamma delare förutom 1 med Euklides algoritm.

Första Heltalet (a):

Andra Heltalet (b):

Prova par:

✓ (8, 9) — ÄR RELATIVT PRIMA (Koprima)

gcd(8, 9) = 1

SGD-värde 1

Interaktivt Diagram: Geometrisk Euklidisk Tessellation Största gemensamma platta: 1 × 1

Euklides upptäckte att det att hitta sgd(a, b) är identiskt med att hitta den största kvadratiska plattan som sömlöst kan täcka en a × b-rektangel utan några mellanrum eller överlappningar:

Divisionssteg med Euklides algoritm

9 = 8 × 1 + 1

8 = 1 × 8 + 0

Kan två sammansatta tal vara relativt prima?

Ja, absolut! Detta är ett av de mest missförstådda begreppen inom elementär talteori. Två tal är relativt prima (koprima) om deras största gemensamma delare är 1, oavsett om talen själva är primtal eller inte.

gcd(a, b) = 1

Betrakta 8 = 2³ (sammansatt) och 9 = 3² (sammansatt). Inget av talen är ett primtal! Men eftersom deras primtalsfaktoriseringar inte delar några gemensamma primtal är sgd(8, 9) = 1, vilket gör dem helt relativt prima.

Varför relativ primhet är viktig inom kryptografi

Eulers fi-funktion φ(n): Räknar hur många heltal upp till n som är relativt prima till n. För primtal gäller φ(p) = p − 1.
RSA-nyckelgenerering: Den publika exponenten e måste vara strikt relativt prima till φ(n) = (p − 1)(q − 1) för att dess modulära multiplikativa invers d ska existera.
Hash-fördelning: Att välja relativt prima storlekar för hashtabeller förhindrar klustring i högpresterande hashtabeller.

Vanliga Fällor

Tal som Ser ut som Primtal (Men Inte Är Det)

Kluriga sammansatta tal som ofta lurar elever och programmerare.

Interaktiv Granskare: Analys av Falska Primtal

Dekonstruktion av 91: Det mest berömda falska primtalet

91 = 7 × 13

√91 ≈ 9.54 (p ≤ 7)

Den Kognitiva Blinda Fläcken

91 slutar på 1, så det klarar jämnt-kontrollen (2). Siffersumman är 9+1=10, så det klarar 3. Slutar inte på 5. Eftersom varken 7 eller 13 finns med i vanliga enkla multiplikationstabeller antar människor undermedvetet att 91 måste vara ett primtal!

51 Sammansatt

3 × 17

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