3 in 6 sta relativno praštevili. Definicija soprostih števil





Nazaj naprej

Pozor! Predogledi diapozitivov so zgolj informativne narave in morda ne predstavljajo vseh funkcij predstavitve. Če vas to delo zanima, prenesite polno različico.

To delo je namenjeno spremljanju razlage nova tema. Učitelj izbere praktične in domače naloge po lastni presoji.

Oprema: računalnik, projektor, platno.

Napredek razlage

Diapozitiv 1. Največji skupni delitelj.

Ustno delo.

1. Izračunaj:

A)

0,7
* 10
: 2
- 0,3
: 0,4
_________
?

 b)

5
: 10
* 0,2
+ 2
: 0,7
_______
?

Odgovori: a) 8; b) 3.

2. Ovrzi trditev: Število »2« je skupni delilec vseh števil.«

Očitno je, da liha števila niso deljiva z 2.

3. Kako se imenujejo števila, ki so večkratnika 2?

4. Poimenuj število, ki je delitelj poljubnega števila.

Pisno.

1. Razštej število 2376 na prafaktorje.

2. Poišči vse skupne delitelje števil 18 in 60.

Kaj je največji skupni delitelj števil 18 in 60?

Poskusite formulirati, katero število imenujemo največji skupni delitelj dveh naravnih števil

Pravilo. Največje naravno število, ki ga lahko delimo brez ostanka, imenujemo največji skupni delitelj.

Zapišejo: GCD (18; 60) = 6.

Prosim, povejte mi, ali je obravnavani način iskanja GCD primeren?

Številke so lahko prevelike in je težko našteti vse delilnike.

Poskusimo najti drug način za iskanje GCD.

Razstavimo števili 18 in 60 na prafaktorje:

18 =

Navedite primere deliteljev števila 18.

Številke: 1; 2; 3; 6; 9; 18.

Navedite primere deliteljev števila 60.

Številke: 1; 2; 3; 4; 5; 6; 10; 12; 15; 20; trideset; 60.

Navedite primere skupnih deliteljev števil 18 in 60.

Številke: 1; 2; 3; 6.

Kako najdeš največji skupni delitelj 18 in 60?

Algoritem.

1. Dana števila razdeli na prafaktorje.

2. Primerjaj faktorje števil in prečrtaj različne.

3. Izračunaj zmnožek preostalih faktorjev.

Diapozitiv 4. Vzajemno praštevila.

telovadba. Poišči gcd števil 24 in 35.

Pravilo. Naravna števila so relativno praštevila, če je njihov največji skupni delitelj 1.

To je zanimivo!

  • Delitelji 18: 1; 2; 3; 6; 9; 18.
  • Delitelji 60: 1; 2; 3; 4; 5; 6; 10; 12; 15; 20; trideset; 60.
  • GCD (18;60) = 6.
  • Delitelji 6: 1; 2; 3; 6.
  • Upoštevajte, da so številke 1; 2; 3; 6 je skupni delitelj števil 18 in 60.
  • NOT (108;196) = 4. To pomeni, da lahko takoj rečemo, da sta skupna delitelja števil 108 in 196 delitelja števila 4, torej 1; 2; 4.

Vsak delitelj števila NOD (a;b) je skupni delitelj števil a in b in obratno, vsak njun skupni delitelj je delitelj števila NOD (a;b).

Kaj so soprosta števila?

Definicija soprostih števil

Definicija soprostih števil:

Kopraštevila so cela števila, ki nimajo skupnih faktorjev razen ena.

Primeri soprostih števil

Primer soprostih števil:

2 in 3 nimata drugih skupnih deliteljev razen ena.

Še en primer soprostih števil:

3 in 7 nimata drugih skupnih faktorjev razen ena.

Še en primer soprostih števil:

11 in 13 nimata drugih skupnih faktorjev razen ena.

Zdaj lahko odgovorimo na vprašanje, kaj pomenijo soprosta števila.

Kaj pomenijo soprosta števila?

To so cela števila, ki nimajo skupnih deliteljev razen ena.

Dve soprosti števili

Vsak od teh parov sta dve relativno praštevili.

11 in 15
15 in 16
16 in 23

Skupni delitelji soprostih števil

Skupni delitelj soprostih števil je samo eden, kot izhaja iz definicije sopraštevil.

Največji skupni delitelj soprostih števil

Največji skupni delitelj soprostih števil je ena, kot izhaja iz definicije soprostih števil.

Ali so števila enako praštevilna?

Ali sta števili 3 in 13 soprosti? Da, ker nimata skupnih deliteljev razen ena.

Ali sta števili 3 in 12 soprosti? Ne, ker sta njuna skupna delitelja 1 in 3. In po definiciji soprostih števil bi moral biti skupni delitelj le ena.

Ali sta števili 3 in 108 soprosti? Ne, ker sta njuna skupna delitelja 1 in 3. In po definiciji soprostih števil bi moral biti skupni delitelj le ena.

Ali sta števili 108 in 5 soprosti? Da, ker nimata skupnih deliteljev razen ena.

Učbenike za matematiko je včasih težko razumeti. Suhega in jasnega jezika avtorjev ni vedno lahko razumeti. In tam so teme vedno povezane in se medsebojno posledično dopolnjujejo. Če želite obvladati eno temo, morate obravnavati številne prejšnje in včasih celo prelistati cel učbenik. Težko? ja Tvegajmo, da se izognemo tem težavam in poskusimo najti nestandarden pristop k temi. Naredimo nekakšen izlet v deželo številk. Vendar pa bomo definicijo še vedno pustili enako, saj pravil matematike ni mogoče preklicati. Kopraštevila so torej naravna števila, katerih skupni delitelj je enak ena. To je jasno? Čisto.

Za bolj nazoren primer vzemimo števili 6 in 13. Obe sta deljivi z ena (coprime). Toda števili 12 in 14 ne moreta biti takšni, saj nista deljivi le z 1, ampak tudi z 2. Naslednji števili, 21 in 47, prav tako ne spadata v kategorijo »soprostih števil«: ni jih mogoče deliti samo za 1, ampak tudi pri 7.

Kopraštevila so označena na naslednji način: ( A, y) = 1.

Lahko rečemo še preprosteje: skupni delitelj (največji) je tukaj enak ena.
Zakaj potrebujemo takšno znanje? Razlogov je dovolj.

Vzajemno vključeni v nekatere sisteme šifriranja. Tisti, ki delajo s Hillovimi šiframi ali Cezarjevim substitucijskim sistemom, razumejo: brez tega znanja ne morete priti nikamor. Če ste že slišali za generatorje, si verjetno ne boste upali zanikati: tudi tam se uporabljajo relativno praštevila.

Zdaj pa se pogovorimo o načinih, kako pridobiti tako preproste, kot razumete, imajo lahko samo dva delitelja: deljivi so sami in z enim. Recimo, da so 11, 7, 5, 3 praštevila, 9 pa ni, ker je to število že deljivo z 9, 3 in 1.

In če A- število je praštevilo in pri- iz kompleta (1, 2, ... A- 1), potem je zagotovljeno ( A, pri) = 1 ali soprosta števila - A in pri.

To sploh ni razlaga, ampak ponavljanje ali povzemanje pravkar povedanega.

Pridobivanje praštevil je možno, vendar je za velika števila (na primer milijarde) ta metoda predolga, vendar je za razliko od superformul, ki se včasih zmotijo, bolj zanesljiva.

Lahko delate z izbiro pri > A. Da bi to naredili, je y izbran tako, da je številka na A ni delil. Da bi to naredili, praštevilo pomnožimo z naravnim številom in dodamo količino (ali, nasprotno, odštejemo) (npr. R), kar je manj A:

y = R a + k

Če npr. A = 71, R= 3, q=10, potem je v skladu s tem pri tukaj bo enako 713. Možna je še ena izbira, s stopnjami.

Sestavljena števila so za razliko od relativno praštevil deljiva sama s seboj, z 1 in z drugimi števili (tudi brez ostanka).

Z drugimi besedami, (razen enega) so razdeljeni na sestavljene in preproste.

Praštevila so naravna števila, ki nimajo netrivialnih (različnih od samega števila in enote) deliteljev. Njihova vloga je še posebej pomembna v današnji sodobni, hitro razvijajoči se kriptografiji, zaradi katere je disciplina, ki je prej veljala za izjemno abstraktno, postala tako zahtevna: algoritmi za zaščito podatkov se nenehno izboljšujejo.

Največje praštevilo je našel oftalmolog Martin Nowak, ki je sodeloval pri projektu GIMPS (distribuirano računalništvo) skupaj z drugimi navdušenci, ki jih je bilo okoli 15 tisoč.Izračuni so trajali šest dolga leta. Vključenih je bilo dva in pol računalnikov, ki se nahajajo na Novakovi očesni kliniki. Rezultat titanskega dela in vztrajnosti je bila številka 225964951-1, zapisana na 7816230 decimalnih mest. Mimogrede, sam zapis veliko število je bila uprizorjena pol leta pred to otvoritvijo. In bilo je pol milijona manj znakov.

Genij, ki hoče poimenovati številko, kjer je trajanje decimalni zapis»skoči« na deset milijonov, obstaja možnost, da prejmete ne le svetovno slavo, ampak tudi 100.000 $. Mimogrede, za številko, ki je presegla milijonsko številko, je Nayan Khairatwal prejel manjši znesek (50.000 $).


Informacije v tem članku pokrivajo temo " soprosta števila" Najprej je podana definicija dveh soprostih števil ter definicija treh ali več soprostih števil. Za tem so podani primeri soprostih števil in prikazano je, kako dokazati, da so dana števila enako praštevilna. V nadaljevanju so navedene in dokazane osnovne lastnosti soprostih števil. Na koncu so omenjena praštevila po parih, ker so tesno povezana s sopraštevili.

Navigacija po straneh.

Pogosto obstajajo naloge, pri katerih morate dokazati, da so dana cela števila relativno praštevila. Dokaz se zmanjša na izračun največjega skupni delilnik danih števil in preverjanje GCD glede enakosti z ena. Koristno je tudi pogledati tabelo praštevil pred izračunom GCD: nenadoma so prvotna cela števila praštevila in vemo, da je največji skupni delitelj praštevil enak ena. Poglejmo primer rešitve.

Primer.

Dokaži, da sta števili 84 in 275 sorazmerno praštevili.

rešitev.

Očitno ti števili nista praštevili, zato ne moremo takoj govoriti o relativni praštevili števil 84 in 275, zato bomo morali izračunati gcd. Za iskanje GCD uporabimo evklidski algoritem: 275=84·3+23, 84=23·3+15, 23=15·1+8, 15=8·1+7, 8=7·1+1, 7 =7 ·1, torej gcd(84, 275)=1. To dokazuje, da sta števili 84 in 275 relativno praštevili.

Definicija soprostih števil se lahko razširi na tri ali več števil.

Opredelitev.

Imenujemo cela števila a 1 , a 2 , …, a k , k>2 medsebojno prime, če je največji skupni delitelj teh števil enak ena.

Iz navedene definicije sledi, da če ima določena množica celih števil pozitiven skupni delitelj, ki ni ena, potem ta cela števila niso soprapraštevilna.

Navedimo primere. Tri cela števila −99, 17 in −27 so sorazmerno praštevila. Vsaka zbirka praštevil sestavlja niz soprostih števil, na primer 2, 3, 11, 19, 151, 293 in 677 so enako praštevila. In štiri števila 12, −9, 900 in −72 niso sopraštevilna, ker imajo pozitiven skupni delitelj 3, ki ni 1. Tudi števila 17, 85 in 187 niso sorazmerno praštevila, saj je vsako od njih deljivo s 17.

Običajno še zdaleč ni očitno, da so nekatera števila relativno praštevila, in to dejstvo je treba dokazati. Če želite ugotoviti, ali so podana števila enako praštevila, morate poiskati največji skupni delitelj teh števil in potegniti sklep na podlagi definicije soprostih števil.

Primer.

Ali so števila 331, 463 in 733 sorazmerno praštevila?

rešitev.

Če pogledamo tabelo praštevil, bomo ugotovili, da je vsako od števil 331, 463 in 733 praštevilo. Zato imajo en sam pozitiven skupni delitelj - ena. Tako so tri števila 331, 463 in 733 relativno praštevila.

odgovor:

ja

Primer.

Dokaži, da števila −14 , 105 , −2 107 in −91 niso sopraštevilna.

rešitev.

Če želite dokazati, da ta števila niso relativno praštevila, lahko poiščete njihov gcd in se prepričate, da ni enak ena. To bomo storili.

Ker delitelji negativnih celih števil sovpadajo z delitelji ustreznih, potem GCD(−14, 105, 2 107, −91)= GCD(14, 105, 2 107, 91) . Če se obrnemo na gradivo v članku o iskanju največjega skupnega delitelja treh ali več števil, ugotovimo, da je GCD(14, 105, 2 107, 91) = 7. Zato je največji skupni delitelj prvotnih števil sedem, torej ta števila niso sopraštevilna.

Lastnosti soprostih števil

Soprosta števila imajo številne lastnosti. Poglejmo glavno lastnosti soprostih števil.

    Števili, ki jih dobimo z deljenjem celih števil a in b z največjim skupnim deliteljem, so sopraprosti, to pomeni, da sta a:NOD(a, b) in b:NOD(a, b) soprosto.

    To lastnost smo dokazali, ko smo preučevali lastnosti GCD.

    Obravnavana lastnost soprostih števil nam omogoča iskanje parov soprostih števil. Če želite to narediti, je dovolj, da vzamete kateri koli dve celi števili in ju delite z največjim skupnim deliteljem, dobljeni številki bosta relativno praštevili.

    Da bi bili celi števili a in b relativno praštevili, je nujno in zadostno, da obstajata celi števili u 0 in v 0 takšni, da je a·u 0 +b·v 0 =1.

    Najprej dokažimo nujnost.

    Naj bosta števili a in b relativno praštevili. Potem je po definiciji soprostih števil gcd(a, b)=1. In iz lastnosti GCD vemo, da za cela števila a in b velja Bezoutova relacija a·u 0 +b·v 0 =NOT(a, b). Zato je a·u 0 +b·v 0 =1.

    Treba je še dokazati zadostnost.

    Naj velja enakost a·u 0 +b·v 0 =1. Ker NOD(a, b) deli tako a kot b, mora NOD(a, b) zaradi lastnosti deljivosti deliti vsoto a·u 0 +b·v 0 in torej enoto. In to je možno le, če GCD(a, b)=1. Zato sta a in b relativno praštevili.

    Naslednja lastnost soprostih števil je naslednja: če sta števili a in b enako praštevili in je produkt a·c deljiv z b, potem je c deljiv z b.

    Ker sta a in b relativno praštevila, potem iz prejšnje lastnosti izhaja enakost a·u 0 +b·v 0 =1. Če pomnožimo obe strani te enakosti s c, dobimo a·c·u 0 +b·c·v 0 =c. Prvi člen vsote a·c·u 0 +b·c·v 0 je deljen z b, ker je a·c po pogoju deljen z b, drugi člen te vsote je prav tako deljen z b, saj eden od faktorjev je enak b, zato celotno vsoto delimo z b. In ker je vsota a·c·u 0 +b·c·v 0 enaka c, potem je c deljiv z b.

    Če sta števili a in b relativno praštevili, potem je gcd(a c, b) = gcd(c, b) .

    Pokažimo, prvič, da gcd(a c, b) deli gcd(c, b), in drugič, da gcd(c, b) deli gcd(a c, b), to bo dokazalo enakost GCD(a c, b) =NOT(c, b) .

    GCD(a c, b) deli tako a c kot b, in ker gcd(a c, b) deli b, deli tudi b c. To pomeni, da gcd(a c, b) deli tako a c kot b c, zato zaradi lastnosti največjega skupnega delitelja deli tudi gcd(a c, b c), ki je glede na lastnosti gcd enak c GCD(a, b)=c. Tako gcd(a c, b) deli oba, b in c, zato deli tudi gcd(c, b).

    Po drugi strani pa GCD(c, b) deli tako c kot b, in ker deli c, deli tudi a·c. Tako gcd(c, b) deli tako a c kot b, zato deli tudi gcd(a c, b).

    Pokazali smo torej, da se gcd(a c, b) in gcd(c, b) med seboj delita, kar pomeni, da sta enaka.

    Če je vsako od števil a 1, a 2, …, a k soprosto z vsakim od števil b 1, b 2, …, b m (kjer sta k in m nekaj cela števila), potem sta produkta a 1 ·a 2 ·…·a k in b 1 ·b 2 ·…·b m relativno praštevila, zlasti če je a 1 =a 2 =…=a k =a in b 1 =b 2 = …=b m =b , potem sta a k in b m relativno praštevili.

    Prejšnja lastnost soprostih števil nam omogoča, da zapišemo niz enakosti oblike GCD(a 1 · a 2 ·…·a k , b m)= NOT(a 2 ·…·a k , b m)=…=NOT(a k , b m)=1, kjer je možen zadnji prehod, saj sta a k in b m po pogoju medsebojno praštevili. Torej, GCD(a 1 · a 2 ·…·a k , b m)=1.

    Če zdaj označimo a 1 ·a 2 ·…·a k =A, imamo
    GCD(b 1 ·b 2 ·…·b m , a 1 ·a 2 ·…·a k)= GCD(b 1 · b 2 ·…·b m , A)=
    =NOT(b 2 ·…·b m , A)=… =NOT(b m , A)=1
    (velja zadnji prehod, zaradi zadnje enakosti iz prejšnjega odstavka). Tako smo dosegli enakost GCD(b 1 ·b 2 ·…·b m , a 1 ·a 2 ·…·a k)=1, kar dokazuje, da sta produkta a 1 ·a 2 ·…·a k in b 1 ·b 2 ·…·b m enako praštevili.

S tem smo zaključili naš pregled osnovnih lastnosti soprostih števil.

Praštevila po parih – definicije in primeri

Preko soprostih števil je podana prepoznavanje parov praštevil.

Opredelitev.

Cela števila a 1, a 2, …, a k, od katerih je vsako relativno praštevilo glede na vsa ostala, imenujemo praštevila po parih.

Dajmo primer praštevil po parih. Števila 14, 9, 17 in −25 so po parih praštevila, saj so pari števil 14 in 9, 14 in 17, 14 in −25, 9 in 17, 9 in −25, 17 in −25 enako praštevila. Tukaj ugotavljamo, da so praštevila po parih vedno sopraštevila.

Po drugi strani pa sorazmerno praštevila niso vedno po paru praštevila, kar potrjuje naslednji primer. Števila 8, 16, 5 in 15 niso po paru praštevila, saj števili 8 in 16 nista praštevila. Vendar pa so števila 8, 16, 5 in 15 relativno praštevilna. Tako so 8, 16, 5 in 15 sorazmerno praštevila, ne pa praštevila v paru.

Posebej moramo izpostaviti zbirko določenega števila praštevil. Ta števila so vedno relativno praštevila in po paru praštevila. Na primer, 71, 443, 857, 991 so po paru praštevila in sopraštevila.

Jasno je tudi, da kdaj govorimo o o dveh celih številih, potem zanje pojma "parno praštevilo" in "medsebojno praštevilo" sovpadata.

Bibliografija.

  • Vilenkin N.Y. in drugi Matematika. 6. razred: učbenik za splošnoizobraževalne ustanove.
  • Vinogradov I.M. Osnove teorije števil.
  • Mikhelovich Sh.H. Teorija števil.
  • Kulikov L.Ya. in drugi Zbirka nalog iz algebre in teorije števil: Vadnica za študente fizike in matematike. specialnosti pedagoških zavodov.


 

Morda bi bilo koristno prebrati: