Články

1.4: Prime Factorization - Mathematics


Vo výroku 3,4 = 12 sa číslo 12 nazýva výrobok, pričom sa volajú 3 a 4 faktorov.

Príklad 1

Nájdite všetky faktory s celkovým počtom 18.

Riešenie

Musíme nájsť všetky dvojice celých čísel, ktorých súčin sa rovná 18. Nasledujúce páry nám prídu na myseľ.

1,18 = 18 a 2,9 = 18 a 3,6 = 18.

Preto sú faktory 18 (v poradí) 1, 2, 3, 6, 9 a 18.

Cvičenie

Nájdite všetkých faktorov s celkovým počtom 21.

Odpoveď

1, 3, 7 a 21

Deliteľnosť

V príklade 1 sme videli 3,6 = 18, čím sme vytvorili 3 a 6 faktorov 18. Pretože delenie je inverzné k násobeniu, to znamená, že delenie číslom zruší násobenie tohto čísla, toto okamžite poskytne

18 ÷ 6 = 3 a 18 ÷ 3 = 6.

To znamená, že 18 je deliteľné 3 a 18 je deliteľné 6. Keď hovoríme, že 18 je deliteľné 3, máme na mysli, že keď je 18 delené 3, zostáva nula.

Deliteľné

Poďme a a b byť celé čísla. Potom a je deliteľné b len a len vtedy, ak je zvyšok nulový, keď a je delené b. V tomto prípade hovoríme, že „b je deliteľom spoločnosti a.”

Príklad 2

Nájdite všetky delitele celého čísla 18.

Riešenie

V príklade 1 sme videli, že 3,6 = 18. Preto je 18 deliteľné 3 aj 6 (18 ÷ 3 = 6 a 18 ÷ 6 = 3). Keď je teda 18 vydelené 3 alebo 6, zvyšok je nula. Preto sú 3 a 6 deliteľmi 18. Ak si všimneme ďalšie produkty v príklade 1, kompletný zoznam deliteľov 18 je 1, 2, 3, 6, 9 a 18.

Cvičenie

Nájdite všetky delitele celého čísla 21.

Odpoveď

1, 3, 7 a 21.

Príklad 1 a príklad 2 ukazujú, že pri práci s celými číslami sú to slová faktor a deliteľ sú zameniteľné.

Faktory a delitelia

Ak c = a · bpotom a a b sa volajú faktorov z c. Oboje a a b sú tiež tzv delitelia z c.

Testy deliteľnosti

Existuje niekoľko veľmi užitočných testov deliteľnosti.

Deliteľné 2. Ak celé číslo končí číslicami 0, 2, 4, 6 alebo 8, potom sa číslo nazýva párne číslo a je deliteľné 2. Príklady párnych čísel sú 238 a 1 246 (238 ÷ 2 = 119 a 1, 246 ÷ 2 = 623). Číslo, ktoré nie je párne, sa nazýva nepárne číslo. Príklady nepárnych čísel sú 113 a 2 339.

Deliteľné 3. Ak je súčet číslic celého čísla deliteľný 3, potom je samotné číslo deliteľné 3. Príkladom je 141. Súčet číslic je 1 + 4 + 1 = 6, čo je deliteľné 3. Preto , 141 je tiež deliteľné 3 (141 ÷ 3 = 47).

Deliteľné 4. Ak je číslo predstavované poslednými dvoma číslicami celého čísla deliteľné 4, potom je samotné číslo deliteľné 4. Príkladom je 11 524. Posledné dve číslice predstavujú 24, ktoré je deliteľné 4 (24 ÷ 4 = 6). Preto je 11 524 deliteľných 4 (11, 524 ÷ 4 = 2 881).

Deliteľné 5. Ak celé číslo končí nulou alebo 5, potom je číslo deliteľné 5. Príklady sú 715 a 120 (715 ÷ 5 = 143 a 120 ÷ 5 = 24).

Deliteľné 6. Ak je celé číslo deliteľné 2 a 3, potom je deliteľné 6. Príkladom je 738. Po prvé, 738 je párne a deliteľné 2. Po druhé, 7 + 3 + 8 = 18, čo je deliteľné 3. Preto je 738 deliteľné číslom 3. Pretože 738 je deliteľné 2 aj 3, je deliteľné 6 (738 ÷ 6 = 123).

Deliteľné 8. Ak je číslo predstavované poslednými tromi číslicami celého čísla deliteľné 8, potom je samotné číslo deliteľné 8. Napríklad 73 024. Posledné tri číslice predstavujú číslo 24, ktoré je deliteľné 8 (24 ÷ 8 = 3). Teda 73 024 je tiež deliteľné 8 (73, 024 ÷ 8 = 9, 128).

Deliteľné 9. Ak je súčet číslic celého čísla deliteľný 9, potom je samotné číslo deliteľné 9. Príkladom je 117. Súčet číslic je 1 + 1 + 7 = 9, čo je deliteľné 9. Preto , 117 je deliteľné 9 (117 ÷ 9 = 13).

Základné čísla

Začíname definíciou prvočísla.

Prvočíslo

Celé číslo (iné ako 1) je prvočíslo, ak jeho jedinými faktormi (deliteľmi) sú 1 a seba. Ekvivalentne je číslo prvočíslo práve vtedy, ak má presne dva faktory (delitele).

Príklad 3

Ktoré z celých čísel 12, 13, 21 a 37 sú prvočísla?

Riešenie

  • Faktory (delitele) 12 sú 1, 2, 3, 4, 6 a 12. Preto 12 nie je prvočíslo.
  • Faktory (delitele) 13 sú 1 a 13. Pretože jeho jedinými deliteľmi sú 1 a sám, 13 je prvočíslo.
  • Faktory (delitele) 21 sú 1, 3, 7 a 21. Preto 21 nie je prvočíslo.
  • Faktory (delitele) 37 sú 1 a 37. Pretože jeho jedinými deliteľmi sú 1 a sám, 37 je prvočíslo.

Cvičenie

Ktoré z celých čísel 15, 23, 51 a 59 sú prvočísla?

Odpoveď

23 a 59

Príklad 4

Uveďte všetky prvočísla menšie ako 20.

Riešenie

Prvočísla menšie ako 20 sú 2, 3, 5, 7, 11, 13, 17 a 19.

Vyskúšajte to!

Vymenujte všetky prvočísla menšie ako 100.

Zložené čísla

Ak celé číslo nie je prvočíslo, potom sa nazýva a zložené číslo.

Príklad 5

Je celé číslo 1 179 prvočíslo alebo zložené?

Riešenie

Všimnite si, že 1 + 1 + 7 + 9 = 18, ktoré je deliteľné 3 aj 9. Preto sú 3 a 9 deliteľmi 1 179. Preto je 1 179 zložené číslo.

Cvičenie

Je celé číslo 2 571 primárne alebo zložené?

Odpoveď

Zložený

Faktorové stromy

Teraz sa naučíme, ako vyjadriť zložené číslo ako jedinečný súčin prvočísel. Najpopulárnejším zariadením na dosiahnutie tohto cieľa je faktorový strom.

Príklad 6

Express 24 ako produkt hlavných faktorov.

Riešenie

Pomocou faktorového stromu rozdelíme 24 na produkt prvočísiel.

Na každej úrovni stromu rozdeľte súčasné číslo na súčin dvoch faktorov. Proces je dokončený, keď všetky „krúžkované listy“ v spodnej časti stromu sú prvočísla. Zoradenie faktorov v „okrúhlých listoch“ podľa poradia,

24 = 2 · 2 · 2 · 3.

Konečná odpoveď nezávisí od výberu produktu na každej úrovni stromu. Tu je ďalší prístup.

Konečná odpoveď sa nachádza zahrnutím všetkých faktorov z „zakrúžkovaných listov“ na koniec každej vetvy stromu, ktorá vedie k rovnakému výsledku, konkrétne 24 = 2 · 2 · 2 · 3.

Alternatívny prístup

Niektorí uprednostňujú opakované delenie dvoma, kým výsledok už nie je deliteľný dvoma. Potom skúste opakované delenie ďalším prvočíslom, kým výsledok už nebude deliteľný týmto prvočíslom. Proces sa ukončí, keď sa posledný výsledný kvocient rovná číslu 1.

Prvý stĺpec odhaľuje hlavnú faktorizáciu; tj. 24 = 2,2 · 2,3.

Cvičenie

Express 36 ako produkt hlavných faktorov.

Odpoveď

2 · 2 · 3 · 3.

Skutočnosť, že alternatívny prístup v príklade 6 priniesol rovnaký výsledok, je významná.

Unikátna veta o faktorizácii

Môže byť každé celé číslo jedinečne započítaný ako produkt prvočísiel.

Tento výsledok zaručuje, že ak sú prvočíselné faktory zoradené od najmenších po najväčšie, každý získa rovnaký výsledok, keď rozdelí číslo na súčin prvočíselných faktorov.

Exponenti

Začíname definíciou exponenciálneho výrazu.

Exponenti

Výraz am je definované, že znamená

(a ^ {m} = podprsenka {a cdot a cdot ldots cdot a} _ {m text {časy}} )

Číslo a sa nazýva základ exponenciálneho výrazu a číslo m sa nazýva exponent. Exponent m káže nám opakovať základňu a ako faktor m krát.

Príklad 7

Vyhodnoťte 25, 23a 52.

Riešenie

  • V prípade 25, máme

25 = 2 · 2 · 2 · 2 · 2

= 32.

  • V prípade 33, máme

33 = 3 · 3 · 3

= 27.

  • V prípade 52, máme

52 = 5 · 5

= 25.

Cvičenie

Vyhodnoťte: 35.

Odpoveď

243.

Príklad 8

Vyjadrite riešenie príkladu 6 v kompaktnej podobe pomocou exponentov.

Riešenie

V príklade 6 sme určili prvočíselnú faktorizáciu 24.

24 = 2 · 2 · 2 · 3

Pretože 2 · 2 · 2 = 23, môžeme to napísať kompaktnejšie.

24 = 23 · 3

Cvičenie

Prime factor 54.

Odpoveď

2 · 3 · 3 · 3

Príklad 9

Vyhodnoťte výraz 23 · 32 · 52.

Riešenie

Najskôr zdvihnite každý faktor na daný exponent a potom vykonajte násobenie v poradí (zľava doprava).

23 · 32 · 52 = 8 · 9 · 25

= 72 · 25

= 1800

Cvičenie

Vyhodnoťte: 33 · 52.

Odpoveď

675

Aplikácia

Štvorec je obdĺžnik so štyrmi rovnakými stranami.

Plocha štvorca

Poďme s predstavuje dĺžku každej strany štvorca.

Pretože štvorec je tiež obdĺžnik, môžeme plochu štvorca nájsť vynásobením jeho dĺžky a šírky. V tomto prípade sa však dĺžka aj šírka rovnajú s, takže A = (s)(s) = s2. Preto vzorec pre plochu štvorca je

A = s2.

Príklad 10

Okraj štvorca je 13 centimetrov. Nájdite plochu štvorca.

Riešenie

Náhradník s = 13 cm do vzorca plochy.

A = s2

= (13 cm)2

= (13 cm) (13 cm)

= 169 cm2

Preto je plocha štvorca 169 cm2; 169 centimetrov štvorcových.

Cvičenie

Okraj námestia je 15 metrov. Nájdite plochu štvorca.

Odpoveď

225 metrov štvorcových

Cvičenia

V Cvičeniach 1-12 nájdite všetky delitele daného čísla.

1. 30

2. 19

3. 83

4. 51

5. 91

6. 49

7. 75

8. 67

9. 64

10. 87

11. 14

12. 89


Ktoré z nasledujúcich čísel nie je v Cvičeniach 13–20 vydeliteľné dvoma?

13. 117, 120, 342, 230

14. 310, 157, 462, 160

15. 30, 22, 16, 13

16. 382, 570, 193, 196

17. 105, 206, 108, 306

18. 60, 26, 23, 42

19. 84, 34, 31, 58

20. 66, 122, 180, 63


Ktoré z nasledujúcich čísel nie je v Cvičeniach 21–28 deliteľné 3?

21. 561, 364, 846, 564

22. 711, 850, 633, 717

23. 186, 804, 315, 550

24. 783, 909, 504, 895

25. 789, 820, 414, 663

26. 325, 501, 945, 381

27. 600, 150, 330, 493

28. 396, 181, 351, 606


Ktoré z nasledujúcich čísel nie je v Cvičeniach 29–36 deliteľné 4?

29. 3797, 7648, 9944, 4048

30. 1012, 9928, 7177, 1592

31. 9336, 9701, 4184, 2460

32. 2716, 1685, 2260, 9788

33. 9816, 7517, 8332, 7408

34. 1788, 8157, 7368, 4900

35. 1916, 1244, 7312, 7033

36. 7740, 5844, 2545, 9368


Ktoré z nasledujúcich čísel nie je v Cvičeniach 37–44 deliteľné 5?

37. 8920, 4120, 5285, 9896

38. 3525, 7040, 2185, 2442

39. 8758, 3005, 8915, 3695

40. 3340, 1540, 2485, 2543

41. 2363, 5235, 4145, 4240

42. 9030, 8000, 5445, 1238

43. 1269, 5550, 4065, 5165

44. 7871, 9595, 3745, 4480


Ktoré z nasledujúcich čísel nie je v cvičeniach 45 - 52 deliteľné 6?

45. 328, 372, 990, 528

46. 720, 288, 148, 966

47. 744, 174, 924, 538

48. 858, 964, 930, 330

49. 586, 234, 636, 474

50. 618, 372, 262, 558

51. 702, 168, 678, 658

52. 780, 336, 742, 312


Ktoré z nasledujúcich čísel nie je v cvičeniach 53 - 60 deliteľné 8?

53. 1792, 8216, 2640, 5418

54. 2168, 2826, 1104, 2816

55. 8506, 3208, 9016, 2208

56. 2626, 5016, 1392, 1736

57. 4712, 3192, 2594, 7640

58. 9050, 9808, 8408, 7280

59. 9808, 1232, 7850, 7912

60. 3312, 1736, 9338, 3912


Ktoré z nasledujúcich čísel nie je v Cvičeniach 61 - 68 deliteľné 9?

61. 477, 297, 216, 991

62. 153, 981, 909, 919

63. 153, 234, 937, 675

64. 343, 756, 927, 891

65. 216, 783, 594, 928

66. 504, 279, 307, 432

67. 423, 801, 676, 936

68. 396, 684, 567, 388


Na cvičeniach 69 - 80 identifikujte dané číslo ako primárne, zložené alebo žiadne.

69. 19

70. 95

71. 41

72. 88

73. 27

74. 61

75. 91

76. 72

77. 21

78. 65

79. 23

80. 36


V cvičeniach 81 - 98 nájdite prvočíselnú faktorizáciu prirodzeného čísla.

81. 224

82. 320

83. 108

84. 96

85. 243

86. 324

87. 160

88. 252

89. 32

90. 128

91. 360

92. 72

93. 144

94. 64

95. 48

96. 200

97. 216

98. 392


V cvičeniach 99 - 110 vypočítajte presnú hodnotu daného exponenciálneho výrazu.

99. 52 · 41

100. 23 · 41

101. 01

102. 13

103. 33 · 02

104. 33 · 22

105. 41

106. 52

107. 43

108. 42

109. 33 · 12

110. 52 · 23


V Cvičeniach 111 - 114 nájdite plochu štvorca s danou stranou.

111. 28 palcov

112,31 palca

113. 22 palcov

114. 13 palcov


Vytvorte stromy faktorov pre každé číslo v Cvičeniach 115-122. Pre každé číslo napíšte prvočíselnú faktorizáciu v kompaktnom tvare pomocou exponentov.

115. 12

116. 18

117. 105

118. 70

119. 56

120. 56

121. 72

122. 270


123. Sito Eratosthenes. Toto cvičenie predstavuje Sito Eratosthenes, starodávny algoritmus na hľadanie prvočísiel menší ako určitý počet n, ktorý prvýkrát vytvoril grécky matematik Eratosthenes. Zvážte mriežku celých čísel od 2 do 100.

Ak chcete nájsť prvočísla menej ako 100, postupujte takto.

i) prečiarknite všetky násobky 2 (4, 6, 8 atď.)

ii) Ďalšie číslo v zozname, ktoré nebolo vyčiarknuté, je prvočíslo.

iii) zo zoznamu vyčiarknite všetky násobky čísla, ktoré ste identifikovali v kroku (ii).

iv) Opakujte kroky (ii) a (iii), až kým už nebudete môcť udrieť na ďalšie násobky.

v) Všetky čísla bez čísla v zozname sú prvočísla.

Odpovede

1. 1, 2, 3, 5, 6, 10, 15, 30

3. 1, 83

5. 1, 7, 13, 91

7. 1, 3, 5, 15, 25, 75

9. 1, 2, 4, 8, 16, 32, 64

11. 1, 2, 7, 14

13. 117

15. 13

17. 105

19. 31

21. 364

23. 550

25. 820

27. 493

29. 3797

31. 9701

33. 7517

35. 7033

37. 9896

39. 8758

41. 2363

43. 1269

45. 328

47. 538

49. 586

51. 658

53. 5418

55. 8506

57. 2594

59. 7850

61. 991

63. 937

65. 928

67. 676

69. prime

71. prime

73. zložený

75. zložený

77. zložený

79. prim

81. 2 · 2 · 2 · 2 · 2 · 7

83. 2 · 2 · 3 · 3 · 3

85. 3 · 3 · 3 · 3 · 3

87. 2 · 2 · 2 · 2 · 2 · 5

89. 2 · 2 · 2 · 2 · 2

91. 2 · 2 · 2 · 3 · 3 · 5

93. 2 · 2 · 2 · 2 · 3 · 3

95. 2 · 2 · 2 · 2 · 3

97. 2 · 2 · 2 · 3 · 3 · 3

99. 100

101. 0

103. 0

105. 4

107. 64

109. 27

111. 784 palcov2

113. 484 palcov2

115. 12 = 22 · 3

117. 105 = 3 · 5 · 7

119. 56 = 23 · 7

121. 72 = 23 · 32

123. Unstruck numbers are prvočísla: 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


Prime faktorizácia

Keď sa začneme učiť o zlomkoch, je dôležité naučiť sa nájsť prvočíselnú faktorizáciu čísla. To je obzvlášť dôležité, keď začneme znižovať zlomky. Tu je niekoľko slovíčok, ktoré vám v tejto lekcii pomôžu:

  • Faktor & # 61 číslo, ktoré sa rovnomerne rozdelí na iné číslo (Príklad: 3 je faktor 12, pretože 12 & delenie 3 je celé číslo).
  • akékoľvek číslo, kde jedinými faktormi sú 1 a jeho samotné (Príklad: 11 je prvočíslo. Neexistuje iné číslo ako 1 a 11, môžete ho vydeliť tým, že získate celé číslo).

Prvé video vysvetlí viac o prvočíslach a o tom, ako zistiť, či je číslo prvočíslo.

Keď vieme, čo sú prvočísla, zistíme, že každé číslo je zložené z menších prvočísiel. Rozdelenie čísla na prvočísla, ktoré ho tvoria, sa nazýva jeho primárna faktorizácia. Každé číslo má prvočíselnú faktorizáciu. Pre prvočísla sú ich jedinými faktormi oni sami a 1. Toto video ukáže, ako nájsť prvočíselnú faktorizáciu čísla a bude pracovať na niekoľkých príkladoch.

Je užitočné zapamätať si niektoré prvočísla, čo uľahčí hľadanie prvočíselnej chyby v budúcich problémoch. Pomocou tohto grafu si zapamätáte prvočísla do 20. Poznajte prvočísla do 100.

Dodatočné zdroje

Nájdite prvočíselnú faktorizáciu nasledujúcich čísel:

Riešenia

3 a # 215 7 a # 61 21 a 3 a 7 sú hlavnými faktormi. Primárna faktorizácia čísla 21 je 3 a 7

Definícia prvočísla je akékoľvek číslo, kde sú jedinými faktormi 1 a sám.

Jedinými faktormi 13 sú 1 a samotný faktor 13. Primárna faktorizácia 13 je iba 13.

Najskôr nájdite faktory 12. Tu uvádzame niekoľko spôsobov, ako faktor 12. Môže sa zohľadniť ako 4 & # 215 3 alebo 6 & # 215 2.

Čísla 3 a 2 sú prvočísla, ale 4 a 6 nie.

Ďalej nájdite faktory 4 alebo 6. Všimnite si, ako je prvočíselná faktorizácia 12 2 & # 215 2 & # 215 3, či boli východiskové faktory 4 & # 215 3 zo 6 & # 215 2. Prvotná faktorizácia je rovnaká .

54 je párne číslo, takže vieme, že je deliteľné dvoma.

Číslo 2 je prvočíslo, ale 27 nie je, takže musíme nájsť faktory 27.

Číslo 3 je prvočíslo, ale 9 nie je prvočíslo, takže musíme nájsť faktory 9.

Číslo 3 je prvočíslo, takže v našej prvočíselnej faktorizácii sú vlastne ďalšie dve čísla 3.

Teraz sa vrátime späť a nájdeme všetky prvočísla vo faktorizácii 54.


Kalkulačka Prime Factorization

Zadajte celé číslo, aby ste našli jeho hlavné faktory a strom faktorov.

Čo je to prvočíslo?

Prvočísla sú prirodzené čísla (kladné celé čísla, ktoré niekedy v určitých definíciách obsahujú 0), ktoré sú väčšie ako 1 a ktoré nemožno vytvoriť vynásobením dvoch menších čísel. Príkladom prvočísla je 7, pretože ho možno vytvoriť iba vynásobením čísel 1 a 7. Medzi ďalšie príklady patrí 2, 3, 5, 11 atď.

Čísla, ktoré môžu byť tvorené dvoma ďalšími prirodzenými číslami, ktoré sú väčšie ako 1, sa nazývajú zložené čísla. Medzi príklady patria čísla ako 4, 6, 9 atď.

Prvočísla sú v teórii čísel široko používané kvôli základnej vete aritmetiky. Táto veta tvrdí, že prirodzené čísla väčšie ako 1 sú buď prvočísla, alebo ich možno považovať za súčin prvočísel. Ako príklad možno číslo 60 zapracovať do súčtu prvočísel nasledovne:

Ako je zrejmé z vyššie uvedeného príkladu, vo faktorizácii nie sú žiadne zložené čísla.

Čo je primárna faktorizácia?

Prime factorization je rozklad zloženého čísla na produkt prvočísel. Existuje veľa faktoringových algoritmov, niektoré zložitejšie ako iné.

Jednou z metód na zistenie hlavných faktorov zloženého čísla je skúšobné delenie. Skúšobné delenie je jedným z najzákladnejších algoritmov, aj keď je veľmi zdĺhavé. Zahŕňa to testovanie každého celého čísla vydelením príslušného zloženého čísla celým číslom a určením, či a koľkokrát môže celé číslo toto číslo rovnomerne rozdeliť. Ako jednoduchý príklad nižšie uvádzame hlavnú faktorizáciu čísla 820 pomocou skúšobného rozdelenia:

Pretože číslo 205 už nie je deliteľné číslom 2, otestujte nasledujúce celé čísla. 205 sa nedá rovnomerne vydeliť číslom 3. 4 nie je prvočíslo. Môže sa však vydeliť 5:

Pretože 41 je prvočíslo, týmto sa uzatvára skúšobné rozdelenie. Takto:

Produkty môžu byť tiež napísané ako:

Jedná sa v podstate o metódu „hrubej sily“ na určovanie hlavných faktorov čísla, a hoci je 820 jednoduchým príkladom, môže byť veľmi rýchlo zdĺhavý.

Ďalším bežným spôsobom, ako uskutočniť prvočíselnú faktorizáciu, je primárny rozklad a môže zahŕňať použitie faktorového stromu. Vytvorenie faktorového stromu zahŕňa rozdelenie zloženého čísla na faktory zloženého čísla, až kým nebudú všetky čísla prvočíselné. V nižšie uvedenom príklade sa primárne faktory zistia vydelením 820 prvočíselným faktorom 2, potom sa pokračuje v delení výsledku, kým nie sú primárne všetky faktory. Nasledujúci príklad ukazuje dva spôsoby, ako je možné vytvoriť faktorový strom pomocou čísla 820:

Je teda zrejmé, že prvou faktorizáciou 820 je v obidvoch prípadoch:

Aj keď tieto metódy fungujú pre menšie počty (a existuje veľa ďalších algoritmov), nie je známy algoritmus pre oveľa väčšie počty, a dokonca môže strojovým počítačom trvať dlho, kým spočítajú hlavné faktorizácie väčších počtov v roku 2009, vedci uzavrel projekt využívajúci stovky strojov na zohľadnenie 232-ciferného čísla RSA-768 a trvalo dva roky.


Faktorizácia

Od delenia cez množenie až po faktoring.

Delenie a množenie sú súvisiace operácie.

Delenie 6 ÷ 3 = 2 sa dá zapísať ako násobenie: 6 = 2 × 3

Faktorovanie celého čísla znamená jeho napísanie ako súčin dvoch alebo viacerých celých čísel.

1) 6 = 1 × 6 6 = 2 × 3 1, 2, 3 a 6 sa nazývajú faktory 6.

2) 12 = 12 × 1 = 3 × 4 = 6 × 2 1, 2, 3, 4, 6 a 12 sa nazývajú faktory 12.

3) 20 = 1 × 20 = 2 × 10 = 2 × 2 × 5 = 4 × 5 1, 2, 3, 4, 5, 10 a 20 sa nazývajú faktory 20.


1.4: Prime Factorization - Mathematics

1.1.1. Definícia. Celé číslo a sa nazýva násobok celého čísla b, ak a = bq pre nejaké celé číslo q. V tomto prípade tiež hovoríme, že b je deliteľom a, a použijeme zápis b | a.

V uvedenom prípade tiež môžeme povedať, že b je faktor a, alebo že a je deliteľné b. Ak b nie je deliteľom a, čo znamená, že bq pre všetky q Z, potom napíšeme b a. Množina všetkých násobkov celého čísla a bude označená

1.1.2. Axiom. [Princíp objednávania] Každá neprázdna množina prirodzených čísel obsahuje najmenší prvok.

1.1.3 Veta. [Algoritmus rozdelenia] Pre akékoľvek celé čísla a a b, s b & gt0, existujú jedinečné celé čísla q (kvocient) ar (zvyšok) také, že a = bq + r, s 0 r & ltb.

1.1.4. Veta. Nech som prázdna množina celých čísel, ktorá je uzavretá pri sčítaní a odčítaní. Potom buď pozostáva iba z nuly, alebo obsahuje najmenší pozitívny prvok, v takom prípade pozostávam zo všetkých násobkov jeho najmenšieho pozitívneho prvku.

1.1.5. Definícia. Kladné celé číslo d sa nazýva najväčší spoločný deliteľ nenulových celých čísel a a b, ak (i) d je deliteľom oboch a a b a

(ii) ktorýkoľvek deliteľ oboch a a b je tiež deliteľom d. Pre najväčší spoločný deliteľ a a b použijeme notáciu gcd (a, b) alebo jednoducho (a, b).

1.1.6. Veta. Akékoľvek dve nenulové celé čísla a a b majú najväčší spoločný deliteľ, ktorý sa dá vyjadriť ako najmenšia kladná lineárna kombinácia a a b.
Celé číslo je navyše lineárnou kombináciou a a b, len ak je násobkom ich najväčšieho spoločného deliteľa.

Najväčší spoločný deliteľ dvoch čísel je možné vypočítať pomocou postupu známeho ako euklidovský algoritmus. Najskôr si všimnite, že ak je 0 a b | a, potom gcd (a, b) = | b |. Nasledujúce pozorovanie poskytuje základ pre euklidovský algoritmus. Ak a = bq + r, potom (a, b) = (b, r). Takto dané celé čísla a & gtb & gt0, euklidovský algoritmus opakovane používa algoritmus delenia na získanie

Od r1 & gt r2 & gt. . . , zvyšky sa zmenšujú a zmenšujú a po konečnom počte krokov získame zvyšok rn + 1 = 0. Teda gcd (a, b) = gcd (b, r1) =. . . = rn.

1.2.1. Definícia. Nenulové celé čísla a a b sú považované za relatívne prvočíselné, ak (a, b) = 1.

1.2.2 Návrh. Nech a, b sú nenulové celé čísla. Potom (a, b) = 1 práve vtedy, ak existujú celé čísla m, n také, že

1.2.3 Návrh. Nech a, b, c sú celé čísla. a) Ak b | ac, potom b | (a, b) c.

b) Ak b | ac a (a, b) = 1, potom b | c.

c) Ak b | a, c | a a (b, c) = 1, potom bc | a.

(d) (a, bc) = 1 práve vtedy, ak (a, b) = 1 a (a, c) = 1. 1.2.4. Definícia. Celé číslo p & gt1 sa nazýva prvočíslo, ak jeho jedinými deliteľmi sú & plusmn 1 a & plusmn p. Celé číslo a & gt 1 sa nazýva zložené, ak nie je prvočíslo.

1.2.5. Lemma. [Euclid] Celé číslo p & gt1 je prvočíslo práve vtedy, ak vyhovuje nasledujúcej vlastnosti: Ak p | ab pre celé čísla a a b, potom buď p | a alebo p | b.

1.2.6. Veta. [Fundamental Theorem of Arithmetic] Každé celé číslo a & gt1 je možné jedinečne zohľadniť ako produkt prvočísel, a to vo forme

1.2.7. Veta. [Euclid] Existuje nekonečne veľa prvočísel.

1.2.8. Definícia. Kladné celé číslo m sa nazýva najmenší spoločný násobok nenulových celých čísel a a b, ak (i) m je násobkom oboch a a b a

(ii) akýkoľvek násobok a a b je tiež násobkom m. Pre najmenší spoločný násobok a a b použijeme zápis lcm [a, b].

1.2.9. Propozícia. Nech a a b sú kladné celé čísla s prvočíselnými faktorizáciami

kdei 0 a bi 0 pre všetky i (umožňujúce použitie rovnakých prvočíselných faktorov.)
Za každú nechám di = mini, bi > a nech mi = max i, bi >. Potom máme nasledujúce faktorizácie: (a) gcd (a, b) = p1 d1 p2 d2 & middot & middot & middot strn dn

Zhody

1.3.2. Propozícia. Nech a, b a n & gt0 sú celé čísla. Potom a b (mod n) práve vtedy, ak n | (a-b).

Pri práci s kongruenciou modulo n sa celé číslo n nazýva modul. Podľa predchádzajúceho tvrdenia, a b (mod n) práve vtedy, ak a-b = nq pre nejaké celé číslo q. Môžeme to napísať v tvare a = b + nq, pre nejaké celé číslo q. Toto pozorovanie poskytuje veľmi užitočnú metódu nahradenia kongruencie rovnicou (nad Z). Na druhej strane, návrh 1.3.3 ukazuje, že ktorúkoľvek rovnicu je možné previesť na kongruenčný modul jednoducho zmenou znaku = na. Pritom je možné jednoducho vynechať akýkoľvek výraz zhodný s 0. Takto by sa rovnica a = b + nq konvertovala späť na a b (mod n).

1.3.3 Návrh. Nech n & gt0 je celé číslo. Potom pre všetky celé čísla a, b, c, d platia nasledujúce podmienky: (a) Ak a c (mod n) a b d (mod n), potom

potom a b c d (mod n) a ab cd (mod n).

(b) Ak a + c a + d (mod n), potom c d (mod n).

Ak ac ad (mod n) a (a, n) = 1, potom c d (mod n). 1.3.4. Propozícia. Nech a a n & gt1 sú celé čísla. Existuje celé číslo b také, že ab 1 (mod n) práve vtedy, ak (a, n) = 1.

1.3.5. Veta. Kongruenčná os b (mod n) má riešenie práve vtedy, ak je b deliteľné číslom d, kde d = (a, n).
Ak d | b, potom existuje d odlišných riešení modulo n a tieto riešenia sú kongruentné modulo n / d.

1.3.6. Veta. [Veta o čínskom zvyšku] Nech n a m sú kladné celé čísla, pričom (n, m) = 1. Potom systém kongruencií

má riešenie. Navyše, akékoľvek dve riešenia sú kongruentné modulárne.

1.4.1. Definícia. Nech a a n & gt0 sú celé čísla. Množina všetkých celých čísel, ktoré majú rovnaký zvyšok ako a po delení n, sa nazýva trieda zhody modulo n a označuje sa [a]n, kde

Zbierka všetkých tried kongruencie modulo n sa nazýva množina celých čísel modulo n, označených Z n.

1.4.2 Návrh. Nech n je kladné celé číslo a nech a, b sú celé čísla. Potom je presne definované sčítanie a násobenie tried zhody uvedených nižšie:

1.4.3. Definícia. Ak]n patrí Z n, a [a]n[b]n = [0]n pre nejakú nenulovú triedu zhody [b]n, potom]n sa nazýva deliteľ nuly, modulo n.

1.4.4. Definícia. Ak]n patrí Z n, a [a]n[b]n = [1]n, pre určitú triedu zhody [b]n, potom [b]n sa nazýva multiplikatívna inverzná hodnota [a]n a označuje sa [a]n -1 .
V tomto prípade hovoríme, že [a]n a [b]n sú invertibilné prvky Z nalebo jednotky Z n.

1.4.5. Propozícia. Nech n je celé kladné číslo. a) Trieda kongruencie [a]n má multiplikatívnu inverziu v Z n keby a len keby (a, n) = 1.

(b) Nenulový prvok Z n buď má multiplikatívnu inverziu, alebo je deliteľom nuly. 1.4.6. Dodatok. Nasledujúce podmienky na module n> 0 sú ekvivalentné: (1) Číslo n je prvočíslo.

(2) Z n nemá žiadne delitele nuly, okrem [0]n.

(3) Každý nenulový prvok Z n má multiplikatívnu inverziu. 1.4.7. Definícia. Nech n je celé kladné číslo. Počet kladných celých čísel menších alebo rovných n, ktoré sú relatívne prvočíselné k n, bude označený ako (n). Táto funkcia sa nazýva Eulerova fí-funkcia alebo totientná funkcia.

1.4.9. Definícia. Súbor jednotiek Z n, triedy zhody [a]n, také, že (a, n) = 1, bude označené
Z n & krát.

Nasledujúca veta ukazuje, že zvýšenie akejkoľvek triedy zhody v Z n & times to the power (n) yields the congruence class of 1. Je možné v tomto bode poskytnúť čisto početný teoretický dôkaz, ale v príklade 3.2.12 existuje elegantnejší dôkaz využívajúci teóriu elementárnych skupín.

1.4.11. Veta. [Euler] Ak (a, n) = 1, potom a (n) 1 (mod n).

1.4.12 Dodatok. [Fermat] Ak je p prvočíslo, potom a p a (mod p) pre akékoľvek celé číslo a.


Stromy Prime Factor (rozsah 4 až 48) (A)

Učiteľ s môže používať matematické pracovné listy ako testy, praktické úlohy alebo učebné nástroje (napríklad v skupinovej práci, na lešení alebo v učebnom centre). Rodič s môžu pracovať so svojimi deťmi, aby im poskytli ďalšie tréningy, pomohli im naučiť sa nové matematické zručnosti alebo aby si udržali svoje zručnosti čerstvé počas školských prázdnin. Študent s môže použiť matematické pracovné listy na osvojenie si matematických zručností prostredníctvom praxe, v študijnej skupine alebo na doučovanie spolužiakov.

Pomocou tlačidiel dole môžete tlačiť, otvárať alebo sťahovať verziu súboru PDF Matematický list Prime Factor Trees (rozsah 4 až 48) (A). Veľkosť súboru PDF je 34804 bajtov. Zobrazia sa ukážky obrázkov prvej a druhej (ak existuje) stránky. Ak existuje viac verzií tohto pracovného hárka, ďalšie verzie budú k dispozícii pod obrázkami ukážky. Ak chcete získať viac podobných informácií, pomocou vyhľadávacieho panela vyhľadajte niektoré alebo všetky z týchto kľúčových slov: číslovanie, počet, zmysel, matematika, matematika, činitele, prvočísla, stromové diagramy .

The Tlač Toto tlačidlo spustí dialógové okno pre tlač v prehliadači. The Otvorené tlačidlo otvorí kompletný súbor PDF na novej karte vášho prehliadača. The Učiteľ tlačidlo inicializuje stiahnutie celého súboru PDF vrátane otázok a odpovedí (ak nejaké sú). Ak Študent tlačidlo je k dispozícii, inicializuje sa stiahnutie iba stránok s otázkami. Ďalšie možnosti môžu byť dostupné kliknutím pravým tlačidlom myši na tlačidlo (alebo podržaním klepnutia na dotykovej obrazovke). Nevidím tlačidlá!

Stromy Prime Factor (rozsah 4 až 48) (A) matematický pracovný list Strana 1 Stromy Prime Factor (rozsah 4 až 48) (A) matematický pracovný list Strana 2

Lekcia: Prime faktorizácia

· Zatiahnite za dve tyčinky - študenti vyplnia odpovede na tabuli - študenti porovnajú prácu s prácou študentov (2 minúty) Učiteľ stále chodí a kontroluje porozumenie, zatiaľ čo študenti pracujú na palube.

· Začiarknuť všetko - umiestniť všetky odpovede na tabuľu

· Študenti si všetky úlohy skontrolujú na domácich úlohách (3 minúty - 1 minúta dopredu, 1 minúta dozadu)

· Učiteľ chodí okolo, zatiaľ čo študenti kontrolujú prácu, aby mohli zasiahnuť.

· Učiteľ identifikuje jednu alebo dve najbežnejšie chyby v domácich úlohách a celú triedu skontroluje ich transparentnosť. (1 - 2 minúty) Pred vykonaním kontroly - požiadajte študentov, aby sa porozmýšľali nad krokmi, ktoré podnikám, kým vyriešim problém (y) - zdieľajú potom celú triedu.

Prechod papiera pri prechode:

· Učiteľ číta a ukazuje problém

· Študent potiahne palicu, aby vyzval študenta, aby odpovedal

· Posledný reťazec problému - všetci študenti dokončia a odpovedajú zdvihnutím ruky - najrýchlejšia vyvolaná ruka

§ Otvorenie: Dnes sa naučíme veľmi dôležitú teóriu matematiky. Táto teória hovorí, že každé číslo možno premeniť na produkt prvočísel presne jedným spôsobom. Predtým, ako sa začneme učiť túto mimoriadne dôležitú teóriu, rozoberme si ju na základe našich znalostí slovnej zásoby. Čo znamená slovo prime? Čo znamená slovo faktor? Čo znamená slovo produkt?

§ Spustenie: rozdávať kalkulačky každému študentovi.

o Uveďte na réžii toto: 15 x 28/20 x 7 x 3/3 x 35 x 4

o Požiadajte študentov, aby pri hľadaní produktov používali kalkulačku. Spýtajte sa študentov, čo si všimnú. Všetky sa rovnajú 420.

o Povedzte študentom, že existuje veľa spôsobov, ako napísať 420 ako produkt (pripomenúť študentom produktové prostriedky ako odpoveď na problém znásobenia) Nájde niekto iný spôsob?

o Spýtajte sa študentov, ako našli každý produkt - študenti majú problémy s vysvetlením svojho uvažovania alebo sa nezdržiavajú hľadaním rôznych spôsobov, ako nájsť iný produkt, a potom vyhľadajte:

o Stratégia kombinovania - Vezmite časti problémov, ktoré už máme, a skombinujte ich tak, aby vytvorili nové číslo (namiesto 20 x 7 x 3 - viacnásobné 7 x 3 a vytvorte úlohu 20 x 21.

o Stratégia rozpadu - vezmeme číslo a rozdelíme ho na dva jeho faktory (15 x 28 - à 5 x 3 x 28, ak rozdelíte 15 od seba)

o Zobraziť hádanku produktu pre študentov - umožniť im používať kalkulačky

o Vysvetlite, že skladačka je ako hľadanie slov - až na to, že zoskupíme reťazec čísel, ktorého súčin sa rovná 1350. Reťazce môžu ísť horizontálne, vertikálne alebo za rohy.

o Nájdite jeden z nich ako príklad (horný riadok - kruh 5 x 6 x 5 x 9) Požiadajte študenta, aby použil kalkulačky, aby zistil, či to funguje.

o Nájdite zvisle - 5 x 3 x 10 x 9 - požiadajte študenta, aby skontroloval, či to funguje

o Umožnite študentom hľadať ďalšie reťazce, ktoré nájdu.

o Zdieľajte s celou triedou niektoré nájdené reťazce.

o Vezmite jeden reťazec z hlavolamu produktu a povedzte študentom, že ho chceme rozdeliť ešte ďalej, kým nebudeme mať čo najdlhší reťazec. Dozvieme sa, že máme čo najdlhší reťazec, keď ho rozdelíme až na jeho hlavné faktory.

o Model rozkladajúci to isté číslo iným spôsobom

o Ukážte krúžením všetkých prvočísel signál na zastavenie tejto vetvy stromu.

o Robte si poznámky o hlavnej faktorizácii a o tom, ako prejsť procesom

o Študenti si precvičia výrobu stromov faktorov pre rôzne množiny čísel.

o Diskutujte o tom, ako môžeme písať produkt alebo prvočísla aj s exponentmi - demonštrovať študentom - ukázať študentom pracujúcim od reťazca s exponentmi po najdlhší reťazec. Model pre študentov a doplňte niekoľko príkladov.

§ Kľúčový bod: Každé číslo má iba jeden najdlhší reťazec faktorov. Primárna faktorizácia ľubovoľného čísla je pre toto číslo jedinečná.


KOMPLETNÁ FAKTORIZÁCIA

CIELE

  1. Najprv hľadajte spoločné faktory.
  2. Zostrojte zostávajúci trinomiál pomocou metód uvedených v tejto kapitole.

Teraz sme študovali všetky obvyklé metódy faktoringu nájdené v elementárnej algebre. Musíte si však uvedomiť, že jeden problém môže vyžadovať viac ako jednu z týchto metód. Pamätajte, že existujú dve kontroly správneho faktoringu.

Len čo sa nájde spoločný faktor, musíte skontrolovať, či je výsledný trinomiál faktorovateľný.

Ak má trinomiál nejaké spoločné faktory, je zvyčajne jednoduchšie, ak sa najskôr zohľadní.

Dobrým postupom, ktorý je potrebné pri factoringu dodržať, je vždy najskôr odstrániť najväčší spoločný faktor a potom podľa možnosti zohľadniť to, čo zostane.


Laplaceova transformácia

Michael Carr,. Eabhnat Ní Fhloinn, Calculus for Engineering Students, 2020

14.1.3 Čiastkové zlomky

S mnohými štandardnými výrazmi sme sa zaoberali v predchádzajúcej podsekcii. Stále však musíme zvážiť, čo sa stane, keď dostaneme výraz ako

Pre tento výraz nemáme žiadnu štandardnú transformáciu. Ale dá sa to ukázať

Vieme, ako si máme poradiť s pravou stranou ekv. (14,37), takže teraz môžeme hodnotiť

kde 1 s + 7 a 1 s + 4 sa nazývajú parciálne zlomky výrazu 2 s + 11 s 2 + 11 s + 28. Teraz zvážime, ako postupujeme pri hľadaní čiastkových zlomkov výrazu.

Pravidlá pre hľadanie čiastkových zlomkov

Prvým krokom pri pokuse o rozklad výrazu na čiastkové zlomky je faktorizácia menovateľa na jeho hlavné faktory. Napríklad 1 s 2 + 9 s + 14 sa delí na 1 (s + 7) (s + 2). V tomto okamihu musíme zvážiť, akú formu majú faktory.

Lineárny faktor, napr. 1 (s + a), dáva čiastočný zlomok formy A s + a, kde A je konštanta, ktorá sa má určiť.

Príklad 14.9

Opakovaný faktor formy (s + a) 2 dáva čiastkové zlomky A s + a + B (s + a) 2.

Príklad 14.10

Ak má opakovaný faktor formu 1 (s + a) 3, dá to čiastkové zlomky E s + a + F (s + a) 2 + G (s + a) 3.

Príklad 14.11

Kvadratický faktor 1 (s 2 + a s + b) dáva parciálny zlomok E s + F s 2 + a s + b.

Príklad 14.12

Príklad 14.13

Pomocou pravidiel 1 - 4 vyššie môžeme prepísať nasledujúce výrazy do formátu čiastkových zlomkov:

Nasledujúce výrazy napíšte ako čiastkové zlomky: 1.

Keď sme spočítali parciálne zlomky, musíme nájsť hodnoty konštánt. Napríklad predpokladajme, že máme

Na určenie inverzných Laplaceových transformácií

Príklad 14.14

Existuje niekoľko krokov, ktoré je potrebné určiť

Faktorizujte menovateľa 3 s - 5 s 2 - 8 s - 33 = 3 s - 5 (s - 11) (s + 3).

Parciálne zlomky majú tvar A s + 3 + B s - 11, čo nám dáva identitu 3 s - 5 s 2 - 8 s - 33 = A s + 3 + B s - 11.


1.4: Prime Factorization - Matematika

Táto stránka pojednáva o základnej matematike a počítačových algoritmoch používaných pri efektívnom vyhľadávaní Mersennych prvočísel. Pretože som viac počítačový programátor ako matematik, nebudem zachádzať do prílišných matematických podrobností, ale pokúsim sa namiesto toho poskytnúť ukazovatele.

Forming an Exponent List

Mersenne numbers are of the simple form 2 P -1, where P is the exponent to be tested. It is easy to prove that if 2 P -1 is prime, then P must be a prime. Thus, the first step in the search is to create a list of prime exponents to test.

Trial Factoring

The next step is to eliminate exponents by finding a small factor. There are very efficient algorithms for determining if a number divides 2 P -1. For example, let's see if 47 divides 2 23 -1. Convert the exponent 23 to binary, you get 10111. Starting with 1, repeatedly square, remove the top bit of the exponent and if 1 multiply squared value by 2, then compute the remainder upon division by 47.

Thus, 2 23 = 1 mod 47. Subtract 1 from both sides. 2 23 -1 = 0 mod 47. Since we've shown that 47 is a factor, 2 23 -1 is not prime.

One very nice property of Mersenne numbers is that any factor q of 2 p -1 must be of the form 2kp+1. Furthermore, q must be 1 or 7 mod 8. A proof is available. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime.

The GIMPS factoring code creates a modified sieve of Eratosthenes with each bit representing a potential 2kp+1 factor. The sieve then eliminates any potential factors that are divisible by prime numbers below 40,000 or so. Also, bits representing potential factors of 3 or 5 mod 8 are cleared. This process eliminates roughly 95% of potential factors. The remaining potential factors are tested using the powering algorithm above.

Now the only question remaining is how much trial factoring should be done? The answer depends on three variables: the cost of factoring, the chance of finding a factor, and the cost of a primality test. The formula used is:

Exponents up to Trial factor to
02 65
23,390,0002 66
29,690,0002 67
37,800,0002 68
47,450,0002 69
58,520,0002 70
75,670,0002 71
96,830,0002 72
115,300,0002 73
147,500,0002 74
186,400,0002 75
227,300,0002 76
264,600,0002 77
337,400,0002 78
420,400,0002 79
516,000,0002 80

P-1 Factoring

There is another factoring method that GIMPS uses to find factors and thereby avoid costly primality tests. This method is called Pollard's (P-1) method. If q is a factor of a number, then the P-1 method will find the factor q if q-1 is highly composite &ndash that is, it has nothing but small factors.

This method when adapted to Mersenne numbers is even more effective. Remember, that the factor q is of the form 2kp+1. It is easy to modify the P-1 method such that it will find the factor q whenever k is highly composite.

The P-1 method is quite simple. In stage 1 we pick a bound B1. P-1 factoring will find the factor q as long as all factors of k are less than B1 (k is called B1-smooth). We compute E &ndash the product of all primes less than B1. Then we compute x = 3 E*2*P . Finally, we check the GCD (x-1, 2 P -1) to see if a factor was found.

There is an enhancement to Pollard's algorithm called stage 2 that uses a second bound, B2. Stage 2 will find the factor q if k has just one factor between B1 and B2 and all remaining factors are below B1. This stage uses lots of memory.

GIMPS has used this method to find some impressive factors. Napríklad:

So how does GIMPS intelligently choose B1 and B2? We use a variation of the formula used in trial factoring. We must maximize:

The chance of finding a factor and the factoring cost both vary with different B1 and B2 values. Dickman's function (see Knuth's Art of Computer Programming Vol. 2) is used to determine the probability of finding a factor, that is k is B1-smooth or B1-smooth with just one factor between B1 and B2. The program tries many values of B1 and (if there is sufficient available memory) several values of B2, selecting the B1 and B2 values that maximize the formula above.

Lucas-Lehmer Primality Testing

The methods described above are first used to attempt to find a factor for the Mersenne number and therefore eliminate the prime exponent P from the testing list before performing the relatively costly Lucas-Lehmer primality test.

The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2 P -1 is prime if and only if Sp-2 is zero in this sequence: S0 = 4, SN = (SN-1 2 - 2) mod (2 P -1).
For example, to prove 2 7 - 1 is prime:

To implement the Lucas-Lehmer test efficiently, one must find the fastest way to square huge numbers modulo 2 P -1. Since the late 1960's the fastest algorithm for squaring large numbers is to split the large number into pieces forming a large array, then perform a Fast Fourier Transform (FFT), a squaring, and an Inverse Fast Fourier Transform (IFFT). See the "How Fast Can We Multiply?" section in Knuth's Art of Computer Programming Vol. 2. In a January, 1994 Mathematics of Computation article by Richard Crandall and Barry Fagin titled " Discrete Weighted Transforms and Large-Integer Arithmetic ", the concept of using an irrational base FFT was introduced. This improvement more than doubled the speed of the squaring by allowing us to use a smaller FFT and it performs the mod 2 P -1 step for free. Although GIMPS uses a floating point FFT for reasons specific to the Intel Pentium architecture, Peter Montgomery showed that an all-integer weighted transform can also be used.

As mentioned in the last paragraph, GIMPS uses floating point FFTs written in highly pipelined, cache friendly assembly language. Since floating point computations are inexact, after every iteration the floating point values are rounded back to integers. The discrepancy between the proper integer result and the actual floating point result is called the convolution or roundoff error. If the convolution error ever exceeds 0.5 then the rounding step will produce incorrect results &ndash meaning a larger FFT should have been used. One of GIMPS' error checks is to make sure the maximum convolution error does not exceed 0.4.

What are the chances that the Lucas-Lehmer test will find a new Mersenne prime number? A simple approach is to repeatedly apply the observation that the chance of finding a factor between 2 X and 2 X+1 is about 1/x. For example, you are testing 2 10,000,139 -1 for which trial factoring has proved there are no factors less than 2 64 . The chance that it is prime is the chance of no 65-bit factor * chance of no 66-bit factor * . * chance of no 5,000,070-bit factor. That is:

This simplifies to 64 / 5000070 or 1 in 78126. This simple approach isn't quite right. It would give a formula of how_far_factored divided by (exponent divided by 2). However, more rigorous work has shown the formula to be (how_far_factored-1) / (exponent times Euler's constant (0.577. )). In this case, 1 in 91623. Even these more rigourous formulas are unproven.

Double-Checking

To verify that a first-time Lucas-Lehmer primality test was performed without error, GIMPS runs the primality test a second time. During each Lucas-Lehmer primality test, the low order 64 bits of the final SP-2 value, called a residue, are sent to PrimeNet and recorded. If these match, then GIMPS declares the exponent properly double-checked. If they do not match, then the primality test is run again until a match finally occurs. The double-check, which takes just as long as a first-time test, is usually done about 2 years after the first-time test. GIMPS assigns double-checks to slower PCs because the exponents are smaller than first-time tests, resulting in work units that can complete in a reasonable time on a slower PC.

GIMPS double-checking goes a bit further to guard against programming errors. Prior to starting the Lucas-Lehmer test, the S0 value is left-shifted by a random amount. Each squaring just doubles how much we have shifted the S value. Note that the mod 2 P -1 step merely rotates the p-th bits and above to the least significant bits, so there is no loss of information. Why do we go to this trouble? If there were a bug in the FFT code, then the shifting of the S values ensures that the FFTs in the first primality test are dealing with completely different data than the FFTs in the second primality test. It would be near impossible for a programming bug to produce the same final 64 bit residues.

Historically, the error rate for a Lucas-Lehmer test where no serious errors were reported during the run is around 1.5%. For Lucas-Lehmer tests where an error was reported the error rate is in the neighborhood of 50%.

Is there a better method than Lucas-Lehmer?

Starting in 2018, GIMPS started using a Fermat probable prime test rather than a Lucas-Lehmer test to search for new Mersenne primes. Robert Gerbicz devised a way to almost completely eliminate the chance of a hardware error corrupting the primality test. Even though results are 99.999+% reliable double-checking is still necessary to guard against program error or forged results. Gerbicz error checking does mean that GIMPS is extremely unlikely to miss a new Mersenne prime on the first test -- a big improvement a 1 or 2% chance of missing a new Mersenne prime on the first test.

Another breakthrough lets GIMPS completely avoid the double-checking process! Krzysztof Pietrzak showed how to create a PRP proof that cannot be faked and can be verified over 100 times faster than a standard double-check. In 2020 proofs were added to the GIMPS software and PRP with proofs became the preferred way to search for new Mersenne primes.


Pozri si video: 6th Grade Math Concepts - Prime Factorization (November 2021).