Factorisatie van getallen in priemfactoren, methoden en voorbeelden van ontleding

Send

Er is een soort taak waarbij het tegenovergestelde wordt aangegeven door een getal dat al in een gebroken indeling wordt gepresenteerd. In dit geval wordt een stuk papier genomen en worden alle componenten van het nummer in volgorde van rechts naar links geschreven, van kleiner naar groter. Een voorbeeld:

Het aantal is verdeeld in 4 eenheden, 8 tientallen, 7 honderden en 4 duizend. Om het te verzamelen, moet u, van rechts naar links, van eenheden tot duizenden het nummer schrijven:
4784.

tienduizendenduizenden in 2018
Verdeel het getal 1234 in termen

Wat betekent een getal ontleden in priemfactoren?

Eerst zullen we uitzoeken wat de belangrijkste factoren zijn.

Het is duidelijk dat, aangezien het woord 'factoren' in deze zin voorkomt, er een product van sommige getallen plaatsvindt en het kwalificerende woord 'priem' betekent dat elke factor een priemgetal is. In een product met de vorm 2-7 · 7 · 23 zijn er bijvoorbeeld vier hoofdfactoren: 2, 7, 7 en 23.

Maar wat betekent het om een getal te ontbinden in priemfactoren?

Dit betekent dat dit nummer moet worden weergegeven als een product van priemfactoren en dat de waarde van dit product gelijk moet zijn aan het oorspronkelijke nummer. Beschouw als voorbeeld het product van drie priemgetallen 2, 3 en 5; het is 30, dus de ontleding van 30 in priemfactoren heeft de vorm 2 · 3 · 5. Gewoonlijk wordt de ontbinding van een getal in priemfactoren geschreven in de vorm van gelijkheid, in ons voorbeeld zal het zo zijn: 30 = 2 · 3 · 5. We benadrukken afzonderlijk dat eenvoudige factoren in de ontbinding kunnen worden herhaald. Dit wordt duidelijk geïllustreerd door het volgende voorbeeld: 144 = 2 · 2 · 2 · 2 · 3 · 3. Maar een weergave van de vorm 45 = 3 - 15 is geen factorisatie, omdat het getal 15 samengesteld is.

De volgende vraag rijst: "Welke getallen kunnen in het algemeen worden ontbonden"?

Op zoek naar een antwoord daarop geven we de volgende redenering. Priemgetallen behoren per definitie tot positieve gehele getallen groter dan één. Gezien dit feit en de regels voor het vermenigvuldigen van gehele getallen, kan worden gesteld dat het product van verschillende priemfactoren een positief geheel getal is dat groter is dan één. Daarom vindt factorisatie alleen plaats voor positieve gehele getallen die groter zijn dan 1.

Maar zijn alle gehele getallen die groter zijn dan één afgebroken in priemfactoren?

Het is duidelijk dat het niet mogelijk is om rekening te houden met prime gehele getallen. Dit wordt verklaard door het feit dat priemgetallen slechts twee positieve delers hebben - een en zichzelf, daarom kunnen ze niet worden weergegeven als het product van twee of meer priemgetallen. Als het gehele getal z zou kunnen worden weergegeven als het product van de priemgetallen a en b, dan zou het concept van deelbaarheid leiden tot de conclusie dat z deelbaar is door a en b, wat onmogelijk is vanwege de eenvoud van het getal z. Er wordt echter aangenomen dat elk priemgetal zelf een ontleding is.

Hoe zit het met samengestelde getallen? Worden samengestelde getallen ontleed in priemfactoren en zijn alle samengestelde getallen onderworpen aan een dergelijke ontleding? Een bevestigend antwoord op een aantal van deze vragen wordt gegeven door de basistheorie van rekenen. De basistheorie van rekenkunde stelt dat elk geheel getal a dat groter is dan 1 kan worden ontbonden in het product van priemfactoren p₁, p₂, ..., p_n , de ontleding heeft de vorm a = p₁· p₂· ... · p_n , en deze ontleding is uniek, als u geen rekening houdt met de opeenvolging van factoren

Canonieke prime-factorisatie

Bij de uitbreiding van het aantal kunnen priemfactoren worden herhaald. Herhalende priemfactoren kunnen compacter worden geschreven met behulp van de kracht van een getal. Stel dat bij de uitbreiding van a een priemfactor p₁ voldoet aan s₁ keer, priemfactor p₂ - s₂ tijden, enzovoort, p_n - s_n tijd. Dan kan de priemfactorisatie van a worden geschreven als a = p₁ s₁ · p₂ s₂ · ... · p_n s_n . Deze vorm van opname is de zogenaamde canonieke priemfactorisatie.

Laten we een voorbeeld geven van de canonieke factorisatie van een getal. Laat ons de ontbinding weten 609 840 = 2 · 2 · 2 · 2 · 3 · 3 · 5 · 7 · 11 · 11, de canonieke schrijfvorm heeft de vorm 609 840 = 2 4 · 3 2 · 5 · 7 · 11 2.

Met de canonieke factorisatie van het getal kunt u alle delers van het getal en het aantal delers van het getal vinden.

Prime factorisatie-algoritme

Om met succes de taak van het ontleden van een getal in priemfactoren te verwerken, moet je een zeer goede kennis hebben van de informatie in het priemgetal en samengestelde getallen.

De essentie van het proces van ontleding van een positief geheel getal groter dan eenheid blijkt uit het bewijs van de hoofdstelling van de rekenkunde. De betekenis is om achtereenvolgens de kleinste priemdelers te vinden p₁, p₂, ..., p_n nummers a, a₁een₂, ..., een_n-1 , waarmee we de reeks gelijkheden a = p kunnen verkrijgen₁· een₁ waar een₁= a: p₁ , a = p₁· een₁= p₁· p₂· een₂ waar een₂= a₁: p₂ , ..., a = p₁· p₂· ... · p_n· een_n waar een_n= a_n-1: p_n . Wanneer doet een_n= 1, dan is de gelijkheid a = p₁· p₂· ... · p_n geeft ons de gewenste factorisatie van een. Hierbij moet worden opgemerkt dat p₁≤p₂≤p₃≤ ... ≤p_n .

Het blijft om te gaan met het vinden van de kleinste priemdelers bij elke stap, en we zullen een algoritme hebben om het aantal in priemfactoren op te splitsen. Het vinden van prime-delers zal ons helpen met een tabel met priemgetallen. We laten zien hoe het te gebruiken om de kleinste priemdeler van z te verkrijgen.

We nemen achtereenvolgens priemgetallen uit de tabel met priemgetallen (2, 3, 5, 7, 11 enzovoort) en delen door hen het gegeven getal z. Het eerste priemgetal waarin z volledig is verdeeld, is de kleinste priemdeler. Als z priem is, dan is z de minste priemdeler. Hier moet eraan worden herinnerd dat als z geen priemgetal is, de kleinste priemdeler een getal niet overschrijdt, waar is de rekenkundige vierkantswortel van z. Dus als er geen enkele deler van z is tussen de priemgetallen die niet overschrijden, kunnen we concluderen dat z een priemgetal is (zie voor meer informatie hierover de theorie onder het kopje dit getal is priemgetal of samengestelde).

Als voorbeeld laten we zien hoe we de kleinste priemdeler van 87 kunnen vinden. Neem het nummer 2. Deel 87 door 2, we krijgen 87: 2 = 43 (rest 1) (zie indien nodig het artikel over de regel en voorbeelden van het delen van gehele getallen met de rest). Dat wil zeggen, wanneer 87 door 2 wordt gedeeld, is de rest 1, dus 2 is geen deler van 87. We nemen het volgende priemgetal uit de tabel met priemgetallen, dit is het nummer 3. Deel 87 door 3, we krijgen 87: 3 = 29. Aldus is 87 volledig deelbaar door 3; daarom is 3 de kleinste priemdeler van 87.

Merk op dat we in het algemeen voor priemfactoren van a een tabel met priemgetallen nodig hebben tot een aantal niet minder dan. We moeten bij elke stap naar deze tabel gaan, dus we moeten deze bij de hand hebben. Om bijvoorbeeld te ontbinden in priemfactoren van 95 hebben we slechts een tabel met priemgetallen tot 10 nodig (omdat 10 meer is dan). En voor de uitbreiding van het nummer 846.653 is een tabel met priemgetallen tot 1.000 nodig (aangezien er 1.000 meer zijn dan).

Nu hebben we genoeg informatie om op te nemen primair factorisatie-algoritme. Het ontledingsalgoritme van het getal a is als volgt:

Door achtereenvolgens de getallen uit de priemtabel te sorteren, vinden we de kleinste priemdeler p₁ getallen a, waarna we een berekenen₁= a: p₁ . Als een₁= 1, dan is het getal a priem, en het is zelf de uitbreiding ervan in priemfactoren. Als een₁ is gelijk aan 1, dan hebben we a = p₁· een₁ en ga door naar de volgende stap.
De kleinste priemdeler vinden p₂ cijfers een₁ , hiervoor sorteren we de getallen uit de priemtabel, beginnend met p₁ , waarna we een berekenen₂= a₁: p₂ . Als een₂= 1, dan is de gewenste factorisatie van a a = p₁· p₂ . Als een₂ is gelijk aan 1, dan hebben we a = p₁· p₂· een₂ en ga door naar de volgende stap.
Herhaling van getallen uit een priemtabel beginnend met p₂ , zoek de kleinste priemdeler p₃ cijfers een₂ , waarna we een berekenen₃= a₂: p₃ . Als een₃= 1, dan is de gewenste factorisatie van a a = p₁· p₂· p₃ . Als een₃ is gelijk aan 1, dan hebben we a = p₁· p₂· p₃· een₃ en ga door naar de volgende stap.
…
De kleinste priemdeler vinden p_n cijfers een_n-1 sorteren door priemgetallen beginnend met p_n-1 evenals een_n= a_n-1: p_n en een_n het blijkt 1 te zijn. Deze stap is de laatste stap van het algoritme, hier verkrijgen we de gewenste factorisatie van het getal a: a = p₁· p₂· ... · p_n .

Alle resultaten verkregen bij elke stap van het algoritme voor het ontleden van het getal in priemfactoren worden voor de duidelijkheid gepresenteerd in de vorm van de volgende tabel, waarin de nummers a, a opeenvolgend worden geschreven in de kolom links van de verticale balk₁een₂, ..., een_n , en rechts van de lijn zijn de overeenkomstige minst prime delers p₁, p₂, ..., p_n .

Het blijft alleen om een paar voorbeelden te overwegen van de toepassing van het verkregen algoritme voor de ontleding van getallen in priemfactoren.

Prime Factor Voorbeelden

Nu zullen we in detail analyseren voorbeelden van primaire factoren. In de uitbreiding zullen we het algoritme van de vorige paragraaf toepassen. Laten we beginnen met eenvoudige gevallen, en we zullen ze geleidelijk ingewikkelder maken om alle mogelijke nuances tegen te komen die zich voordoen wanneer de getallen worden ontbonden in priemfactoren.

Hoe factoren te factureren?

Elk samengesteld nummer kan worden weergegeven als het product van de priemdelers:

De rechterkant van de verkregen gelijkheden worden genoemd primaire factorisatie nummers 15 en 28.

Een bepaald samengesteld getal ontleden in priemfactoren is dit getal vertegenwoordigen als het product van zijn priemdelers.

De ontbinding van dit aantal in priemfactoren is als volgt:

Eerst moet u het kleinste priemgetal uit de priemtabel selecteren waarmee dit samengestelde getal zonder rest deelbaar is en de deling uitvoeren.
Vervolgens moet u opnieuw het kleinste priemgetal oppakken waarmee het reeds ontvangen quotiënt zonder rest wordt verdeeld.
De tweede actie wordt herhaald totdat een eenheid wordt verkregen in het quotiënt.

We ontleden bijvoorbeeld het getal 940 in priemfactoren. We vinden het kleinste priemgetal gedeeld door 940. Dit getal is 2:

Nu selecteren we het kleinste priemgetal, dat wordt gedeeld door 470. Dit nummer is weer 2:

Het kleinste priemgetal dat 235 verdeelt is 5:

Het getal 47 is priem, wat betekent dat het kleinste priemgetal waarmee 47 wordt gedeeld, het getal zelf is:

We krijgen dus het getal 940, opgesplitst in priemfactoren:

940 = 2 · 470 = 2 · 2 · 235 = 2 · 2 · 5 · 47

Als we bij het ontleden van een getal in priemfactoren verschillende identieke factoren krijgen, kunnen ze voor de beknoptheid als een macht worden geschreven:

940 = 2 2 · 5 · 47

Prime factorisatie is het handigst als volgt geschreven: schrijf eerst dit samengestelde getal op en teken een verticale balk rechts ervan:

Rechts van de regel schrijven we de kleinste eenvoudige deler waarin dit samengestelde getal is verdeeld:

We voeren de divisie uit en het quotiënt dat voortvloeit uit de divisie wordt geschreven onder het dividend:

We behandelen het quotiënt op dezelfde manier als met het gegeven samengestelde getal, d.w.z. we selecteren het kleinste priemgetal waarmee het deelbaar is zonder rest en voeren de deling uit. En dus herhalen we totdat een eenheid is verkregen in het quotiënt:

Houd er rekening mee dat het soms moeilijk is om een getal te ontbinden in priemfactoren, omdat we bij het ontbinden een groot aantal kunnen tegenkomen, dat moeilijk direct te bepalen is of het eenvoudig of samengesteld is. En als het samengesteld is, is het niet altijd gemakkelijk om de kleinste eenvoudige deler te vinden.

Laten we bijvoorbeeld proberen 5106 om te zetten in priemfactoren:

Na het bereiken van de privé 851, is het moeilijk om onmiddellijk de kleinste deler te bepalen. We wenden ons tot de tabel met priemgetallen. Als er een nummer in zit dat ons in moeilijkheden brengt, wordt het alleen door zichzelf en door één gedeeld. Het getal 851 staat niet in de priemtabel, wat betekent dat het een composiet is. Het blijft alleen om het in priemgetallen te verdelen volgens de methode van sequentieel zoeken: 3, 7, 11, 13 ,. en zo verder tot we een geschikte prime deler vinden. Met behulp van de opsommingsmethode zien we dat 851 wordt gedeeld door het getal 23:

We krijgen dus het getal 5106, ontbonden in priemfactoren:

5106 = 2 · 3 · 23 · 37