Përmbajtje

• Hapa
• Pjesa 1 nga 3: Testet e Thjeshtësisë
• Pjesa 2 nga 3: Si funksionojnë testet e thjeshtësisë
• Pjesa 3 nga 3: Përdorimi i Teoremës Kineze të Mbetjes
• Këshilla
• Cfare te nevojitet

Numrat e thjeshtë janë numra që ndahen vetëm me veten dhe me 1. Të gjithë numrat e tjerë quhen numra të përbërë. Ka shumë mënyra për të përcaktuar nëse një numër është i thjeshtë, dhe të gjithë kanë avantazhet dhe disavantazhet e tyre. Nga njëra anë, disa nga metodat janë shumë të sakta, por ato janë mjaft komplekse nëse keni të bëni me një numër të madh. Nga ana tjetër, ka mënyra shumë më të shpejta, por ato mund të çojnë në rezultate të pasakta. Zgjedhja e metodës së përshtatshme varet nga numri i madh i numrave me të cilët po punoni.

Hapa

Pjesa 1 nga 3: Testet e Thjeshtësisë

Shënim: në të gjitha formula n tregon numrin që duhet kontrolluar.

1. 1 Numërimi i pjesëtuesve. Mjafton të ndahet n për të gjithë numrat e thjeshtë nga 2 në vlerën e rrumbullakosur (${ displaystyle { sqrt {n}}}$).
2. 2 Teorema e vogël e Fermat. Paralajmërim: ndonjëherë testi do të identifikojë gabimisht numrat e përbërë si kryeministër, madje edhe për të gjitha vlerat e a.
   • Le të zgjedhim një numër të plotë ai tillë që 2 ≤ a ≤ n - 1.
   • Nëse a (mod n) = a (mod n) atëherë numri ndoshta është i thjeshtë. Nëse barazia nuk plotësohet, numri n është i përbërë.
   • Kontrolloni barazinë e dhënë për vlera të shumta apër të rritur gjasat që numri që testohet të jetë vërtet prim.
3. 3 Testi Miller-Rabin. Paralajmërim: ndonjëherë, edhe pse rrallë, për vlera të shumëfishta të a, testi do të identifikojë në mënyrë të rreme numrat e përbërë si kryeministër.
   • Gjeni sasitë s dhe d të tilla që ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Zgjidhni një numër të plotë a në rangun 2 ≤ a ≤ n - 1.
   • Nëse a = +1 (mod n) ose -1 (mod n), atëherë n është ndoshta kryeministër. Në këtë rast, shkoni te rezultati i testit. Nëse barazia nuk qëndron, shkoni në hapin tjetër.
   • Sheshoni përgjigjen tuaj (${ displaystyle a ^ {2d}}$) Nëse merrni -1 (mod n), atëherë n është ndoshta një numër i thjeshtë. Në këtë rast, shkoni te rezultati i testit. Nëse barazia dështon, përsëriteni (${ displaystyle a ^ {4d}}$ dhe kështu me radhë) derisa ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Nëse në një hap pas katrorimit të një numri tjetër përveç ${ displaystyle pm 1}$ (mod n), ju keni +1 (mod n), kështu që n është një numër i përbërë. Nëse ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), atëherë n nuk është kryesor.
   • Rezultati i testit: nëse n e kalon testin, përsëriteni atë për vlera të tjera apër të rritur besimin.

Pjesa 2 nga 3: Si funksionojnë testet e thjeshtësisë

1. 1 Numërimi i pjesëtuesve. Sipas përkufizimit, numri n është e thjeshtë vetëm nëse nuk ndahet me 2 dhe numra të plotë të tjerë përveç 1 dhe vetvetes. Formula e mësipërme ju lejon të hiqni hapat e panevojshëm dhe të kurseni kohë: për shembull, pasi të kontrolloni nëse një numër ndahet me 3, nuk ka nevojë të kontrolloni nëse është i ndashëm me 9.
   • Funksioni i dyshemesë (x) rrumbullakos x në numrin e plotë më të afërt më të vogël ose të barabartë me x.
2. 2 Mësoni rreth aritmetikës modulare. Operacioni "x mod y" (mod është një shkurtim i fjalës latine "modulo", domethënë "modul") do të thotë "ndani x me y dhe gjeni pjesën e mbetur". Me fjalë të tjera, në aritmetikën modulare, me arritjen e një vlere të caktuar, e cila quhet modul, numrat "kthehen" përsëri në zero. Për shembull, ora numëron mbrapsht me modulin 12: tregon 10, 11 dhe 12 orë, dhe pastaj kthehet në 1.
   • Shumë kalkulatorë kanë një çelës mod. Fundi i këtij seksioni ju tregon se si të llogarisni manualisht këtë funksion për një numër të madh.
3. 3 Mësoni rreth kurtheve të Teoremës së Vogël të Fermat. Të gjithë numrat për të cilët nuk plotësohen kushtet e provës janë të përbërë, por pjesa tjetër e numrave janë vetëm ndoshta jane te thjeshta Nëse doni të shmangni rezultatet e pasakta, kërkoni n në listën e "numrave Carmichael" (numrat e përbërë që plotësojnë këtë test) dhe "numrat pseudoprime Fermat" (këta numra plotësojnë kushtet e testimit vetëm për disa vlera a).
4. 4 Nëse është i përshtatshëm, përdorni testin Miller-Rabin. Edhe pse kjo metodë është mjaft e rëndë për llogaritjet manuale, shpesh përdoret në programet kompjuterike. Ofron shpejtësi të pranueshme dhe më pak gabime sesa metoda e Fermat. Një numër i përbërë nuk do të merret si numër kryesor nëse llogaritjet kryhen për më shumë se ¼ vlera a... Nëse zgjidhni rastësisht vlera të ndryshme a dhe për të gjithë ata testi do të japë një rezultat pozitiv, mund të supozojmë me një shkallë mjaft të lartë besimi se n është një numër i thjeshtë.
5. 5 Për numër të madh, përdorni aritmetikë modulare. Nëse nuk keni një kalkulator mod, ose llogaritësi nuk është krijuar për të trajtuar numra kaq të mëdhenj, përdorni vetitë e fuqisë dhe aritmetikën modulare për t'i bërë llogaritjet më të lehta. Më poshtë është një shembull për ${ displaystyle 3 ^ {50}}$ mod 50:
   • Rishkruajeni shprehjen në një formë më të përshtatshme: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Llogaritjet manuale mund të kërkojnë thjeshtime të tjera.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Këtu kemi marrë parasysh vetinë e shumëzimit modular.
   • ${ displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ displaystyle (43 * 43)}$ mod 50.
   • ${ displaystyle = 1849}$ mod 50.
   • ${ displaystyle = 49}$.

Pjesa 3 nga 3: Përdorimi i Teoremës Kineze të Mbetjes

1. 1 Zgjidhni dy numra. Njëri prej numrave duhet të jetë i përbërë dhe tjetri duhet të jetë pikërisht ai që dëshironi të provoni për thjeshtësinë.
   • Numri 1 = 35
   • Numri2 = 97
2. 2 Zgjidhni dy vlera që janë më të mëdha se zero dhe, përkatësisht, më pak se numrat Number1 dhe Number2. Këto vlera nuk duhet të jenë të njëjta.
   • Vlera 1 = 1
   • Vlera2 = 2
3. 3 Llogaritni MMI (Anasjellë Matematikore Shumëzuese) për Numrin 1 dhe Numrin 2.
   • Llogaritni MMI
     • MMI1 = Numri2 ^ -1 Mod Numri1
     • MMI2 = Numri1 ^ -1 Mod Numri2
   • Vetëm për numrat kryesorë (kjo do të japë një numër për numrat e përbërë, por nuk do të jetë MMI e tij):
     • MMI1 = (Numri2 ^ (Numri1-2))% Numri1
     • MMI2 = (Numri1 ^ (Numri2-2))% Numri2
   • Për shembull:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Krijoni një tabelë për secilën MMI poshtë në modulet log2:
   • Për MMI1
     • F (1) = Numri2% Numri1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Numri1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Numri1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Numri1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Numri1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Numri1 = 1 * 1% 35 = 1
   • Llogaritni Numrat e Çiftuar 1 - 2
     • 35 -2 = 33 (10001) bazë 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Për MMI2
     • F (1) = Numri 1% Numri2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Numri2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Numri2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Numri2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Numri2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Numri2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Numër2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Numri2 = 35 * 35 mod 97 = 61
   • Llogaritni Numrin e Çiftuar 2 - 2
     • 97 - 2 = 95 = (1011111) baza 2
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = ((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Llogarit (Vlera1 * Numri2 * MMI1 + Vlera2 * Numri1 * MMI2)% (Numri1 * Numri2)
   • Përgjigje = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Përgjigje = (2619 + 4270)% 3395
   • Përgjigje = 99
6. 6 Kontrolloni që Numri 1 të mos jetë kryesor
   • Llogarit (Përgjigje - Vlera 1)% Numër1
   • 99 – 1 % 35 = 28
   • Meqenëse 28 është më i madh se 0, 35 nuk është një numër i thjeshtë.
7. 7 Kontrolloni që Numri 2 të jetë kryesor.
   • Llogarit (Përgjigje - Vlera2)% Numri2
   • 99 – 2 % 97 = 0
   • Meqenëse 0 është 0, 97 ka shumë të ngjarë një numër i thjeshtë.
8. 8 Përsëritni hapat 1 deri në 7 të paktën dy herë të tjera.
   • Nëse merrni 0 në hapin 7:
     • Përdorni një Numër1 tjetër nëse Numri 1 nuk është i thjeshtë.
     • Përdorni një numër tjetër 1 nëse numri 1 është i thjeshtë. Në këtë rast, duhet të merrni 0 në hapat 6 dhe 7.
     • Përdorni kuptime të ndryshme 1 dhe kuptim2.
   • Nëse në hapin 7 ju merrni vazhdimisht 0, atëherë Numri 2 ka shumë të ngjarë të jetë kryesor.
   • Hapat 1 deri në 7 mund të rezultojnë në një gabim nëse Numri 1 nuk është i thjeshtë dhe Numri 2 është pjesëtues i Numrit 1. Metoda e përshkruar funksionon në të gjitha rastet kur të dy numrat janë të thjeshtë.
   • Arsyeja që ju duhet të përsërisni hapat 1 deri në 7 është sepse në disa raste, edhe nëse Numri 1 dhe Numri 2 nuk janë të thjeshtë, në hapin 7 do të merrni 0 (për një ose të dy numrat). Kjo ndodh rrallë.Zgjidhni një Numër tjetër 1 (të përbërë), dhe nëse Numri 2 nuk është i thjeshtë, atëherë Numri 2 nuk do të barazohet me zero në hapin 7 (me përjashtim të rastit kur Numri 1 është pjesëtues i Numrit 2 - këtu numrat e parë gjithmonë do të jenë të barabartë me zero në hapin 7).

Këshilla

• Numrat e parë nga 168 në 1000: 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, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Edhe pse testimi i forcës brutale është një test i lodhshëm kur punoni me numra të mëdhenj, është mjaft efikas për numrat e vegjël. Edhe në rastin e numrave të mëdhenj, filloni duke testuar pjesëtues të vegjël, dhe më pas kaloni në metoda më të sofistikuara për të kontrolluar thjeshtësinë e numrave (nëse nuk gjenden pjestues të vegjël).

Cfare te nevojitet

• Letër, stilolaps ose kompjuter