Keskinäiset alkuluvut, niiden ominaisuudet. Koprime-luvut
Mitä ovat koprime-luvut?
Koprime-lukujen määritelmä
Koprime-lukujen määritelmä:
Koprime-luvut ovat kokonaislukuja, joilla ei ole muita yhteisiä tekijöitä kuin yksi.
Esimerkkejä koprime-luvuista
Esimerkki koprime-luvuista:
2:lla ja 3:lla ei ole muita yhteisiä jakajia kuin yksi.
Toinen esimerkki koprime-luvuista:
3:lla ja 7:llä ei ole muita yhteisiä tekijöitä kuin yksi.
Toinen esimerkki koprime-luvuista:
11 ja 13 ei ole muita yhteisiä tekijöitä kuin yksi.
Nyt voimme vastata kysymykseen, mitä koprime-luvut tarkoittavat.
Mitä koprime-luvut tarkoittavat?
Nämä ovat kokonaislukuja, joilla ei ole muita yhteisiä jakajia kuin yksi.
Kaksi alkulukua
Jokainen näistä pareista on kaksi suhteellisen alkulukua.
11 ja 15
15 ja 16
16 ja 23
Koalkilukujen yhteiset jakajat
Kopiaalisten lukujen yhteiset jakajat ovat vain yksi, kuten seuraavien lukujen määritelmästä seuraa.
Suurin koprime-lukujen yhteinen jakaja
Koalkilukujen suurin yhteinen jakaja on yksi, kuten koalkilukujen määritelmästä seuraa.
Ovatko luvut koprimeja?
Ovatko luvut 3 ja 13 koprime? Kyllä, koska niillä ei ole yhteistä jakajaa yhtä lukuun ottamatta.
Ovatko luvut 3 ja 12 koprime? Ei, koska niiden yhteiset jakajat ovat 1 ja 3. Ja koprime-lukujen määritelmän mukaan yhteinen jakaja pitäisi olla vain yksi.
Ovatko luvut 3 ja 108 koprime? Ei, koska niiden yhteiset jakajat ovat 1 ja 3. Ja koalkilukujen määritelmän mukaan yhteisen jakajan tulisi olla vain yksi.
Ovatko luvut 108 ja 5 koprime? Kyllä, koska niillä ei ole yhteistä jakajaa yhtä lukuun ottamatta.
Matematiikan oppikirjoja on joskus vaikea ymmärtää. Kirjoittajien kuivaa ja selkeää kieltä ei aina ole helppo ymmärtää. Ja siellä olevat aiheet liittyvät aina toisiinsa ja ovat toisiaan seuravia. Yhden aiheen hallitsemiseksi sinun on nostettava esille useita aikaisempia ja joskus jopa selata koko oppikirja. Vaikea? Joo. Otetaan näiden vaikeuksien kiertämisen riski ja yritetään löytää epätyypillinen lähestymistapa aiheeseen. Tehdään eräänlainen retki numeroiden maahan. Jätämme kuitenkin määritelmän ennalleen, koska matematiikan sääntöjä ei voi kumota. Koalkilukuluvut ovat siis luonnollisia lukuja, joiden yhteinen jakaja on yksi. Se on selvää? Melko.
Visuaalisempaa esimerkkiä varten otetaan luvut 6 ja 13. Molemmat ovat jaollisia yhdellä (koprime). Mutta luvut 12 ja 14 eivät voi olla sellaisia, koska ne ovat jaollisia paitsi 1:llä, myös 2:lla. Myöskään seuraavat luvut, 21 ja 47, eivät mahdu "kopruslukujen" luokkaan: niitä ei voida jakaa. vain 1, mutta myös 7.
Koprime-luvut merkitään seuraavasti: ( A, y) = 1.
Voidaan sanoa vielä yksinkertaisemmin: yhteinen jakaja (suurin) tässä on yhtä suuri kuin yksi.
Miksi tarvitsemme tällaista tietoa? Syitä riittää.
Sisältyy molemminpuolisesti joihinkin salausjärjestelmiin. Hill-salausten tai Caesar-korvausjärjestelmän kanssa työskentelevät ymmärtävät: ilman tätä tietoa et pääse minnekään. Jos olet kuullut generaattoreista, et todennäköisesti uskalla kiistää: sielläkin käytetään suhteellisen alkulukuja.
Puhutaanpa nyt tavoista saada tällaisia yksinkertaisia, kuten ymmärrät, niillä voi olla vain kaksi jakajaa: ne ovat jaettavissa itsellään ja yhdellä. Oletetaan, että 11, 7, 5, 3 ovat alkulukuja, mutta 9 ei ole, koska tämä luku on jo jaollinen luvuilla 9, 3 ja 1.
Ja jos A- luku on alkuluku ja klo- sarjasta (1, 2, ... A- 1), niin se on taattu ( A, klo) = 1 tai alkulukuja - A Ja klo.
Tämä ei pikemminkin ole edes selitys, vaan toisto tai yhteenveto siitä, mitä juuri sanottiin.
Alkulukujen saaminen on kuitenkin mahdollista suurille luvuille (esimerkiksi miljardeille) tämä menetelmä on liian pitkä, mutta toisin kuin superkaavat, jotka tekevät joskus virheitä, se on luotettavampi.
Voit työskennellä valitsemalla klo > A. Tätä varten y valitaan siten, että numero on päällä A ei jakanut. Tätä varten alkuluku kerrotaan luonnollisella luvulla ja määrä lisätään (tai päinvastoin vähennetään) (esim. R), joka on pienempi A:
y = R a + k
Jos esim. A = 71, R= 3, q = 10, niin vastaavasti klo tässä se on yhtä suuri kuin 713. Toinen valinta on mahdollinen, asteilla.
Yhdistetyt luvut, toisin kuin suhteellisen alkuluvut, ovat jaollisia itsellään, luvulla 1 ja muilla luvuilla (myös ilman jäännöstä).
Toisin sanoen (yksi lukuun ottamatta) jaetaan yhdistelmä- ja yksinkertaisiin.
alkuluvut- luonnolliset luvut, joilla ei ole ei-triviaaleja (eri kuin itse luku ja yksikkö) jakajia. Niiden rooli on erityisen tärkeä nykyaikaisessa, nopeasti kehittyvässä kryptografiassa, jonka ansiosta aiemmin äärimmäisen abstraktina pidetty tieteenala on tullut niin kysytyksi: tietosuoja-algoritmeja kehitetään jatkuvasti.
Suurimman alkuluvun löysi GIMPS-projektiin (distributed computing) osallistunut silmälääkäri Martin Nowak muiden harrastajien kanssa, joita oli noin 15 tuhatta pitkiä vuosia. Mukana oli kaksi ja puoli tusinaa Novakin silmäklinikalla sijaitsevaa tietokonetta. Titaanisen työn ja sinnikkyyden tulos oli 7816230 desimaalin tarkkuudella kirjoitettu numero 225964951-1. Muuten, suurimman luvun ennätys tehtiin kuusi kuukautta ennen tätä löytöä. Ja merkkejä oli puoli miljoonaa vähemmän.
Nero, joka haluaa nimetä numeron, missä on kesto desimaalimerkintä"hyppää" kymmenen miljoonan rajan, on mahdollisuus saada paitsi maailmanlaajuista mainetta, myös 100 000 dollaria. Muuten, miljoonan numeron rajan ylittäneestä numerosta Nayan Khairatwal sai pienemmän summan (50 000 dollaria).
Tässä artikkelissa puhumme siitä, mitä koprime-luvut ovat. Ensimmäisessä kappaleessa muotoillaan määritelmät kahdelle, kolmelle tai useammalle suhteellisen alkuluvulle, annetaan useita esimerkkejä ja näytetään, missä tapauksissa kahta lukua voidaan pitää alkulukuna suhteessa toisiinsa. Tämän jälkeen siirrytään pääominaisuuksien ja niiden todisteiden muotoiluun. Viimeisessä kappaleessa puhumme liittyvästä käsitteestä - parittaisista alkuluvuista.
Yandex.RTB R-A-339285-1
Mitä ovat koprime-luvut
Joko kaksi kokonaislukua tai useampi niistä voi olla keskenään alkulukuja. Esitetään ensin määritelmä kahdelle luvulle, joita varten tarvitsemme niiden suurimman yhteisen jakajan käsitteen. Toista tarvittaessa sille omistettu materiaali.
Määritelmä 1
Kaksi tällaista lukua a ja b ovat keskenään alkulukuja, joiden suurin yhteinen jakaja on 1, ts. GCD (a, b) = 1.
From tämä määritelmä voimme päätellä, että kahden koalkiluvun ainoa positiivinen yhteinen jakaja on 1. Vain kahdella tällaisella numerolla on kaksi yhteistä jakajaa - yksi ja miinus yksi.
Mitkä ovat esimerkkejä koprime-luvuista? Tällainen pari olisi esimerkiksi 5 ja 11. Niillä on vain yksi yhteinen positiivinen jakaja, joka on yhtä suuri kuin 1, mikä vahvistaa niiden keskinäisen yksinkertaisuuden.
Jos otamme kaksi alkulukua, niin ne ovat suhteessa toisiinsa kaikissa tapauksissa keskenään alkulukuja, mutta tällaisia keskinäisiä suhteita muodostuu myös yhdistelmälukujen välille. On tapauksia, joissa yksi luku suhteellisten alkulukujen parissa on yhdistelmäluku ja toinen alkuluku tai molemmat ovat yhdistelmälukuja.
Tätä väitettä havainnollistaa seuraava esimerkki: yhdistelmäluvut 9 ja 8 muodostavat suhteellisen alkuparin. Todistetaan tämä laskemalla niiden suurin yhteinen jakaja. Tätä varten kirjoitamme muistiin kaikki niiden jakajat (suosittelemme lukemaan uudelleen artikkelin luvun jakajien löytämisestä). 8:lle nämä luvut ovat ± 1, ± 2, ± 4, ± 8 ja 9 - ± 1, ± 3, ± 9. Valitsemme kaikista jakajista sen, joka on yhteinen ja suurin - tämä on yhtenäisyys. Siksi, jos GCD (8, − 9) = 1, niin 8 ja - 9 ovat toistensa alkulukuja.
Koprime-luvut eivät ole 500 ja 45, koska niillä on toinen yhteinen jakaja - 5 (katso artikkeli 5:llä jaollisuuden kriteereistä). Viisi on suurempi kuin yksi ja positiivinen luku. Toinen samanlainen pari voisi olla - 201 ja 3, koska molemmat voidaan jakaa kolmella, kuten vastaava jakomerkki osoittaa.
Käytännössä melko usein on tarpeen määrittää kahden kokonaisluvun suhteellinen alkuluku. Tämän selvittäminen voidaan pelkistää suurimman yhteisen jakajan löytämiseen ja sen vertaamiseen ykseyteen. On myös kätevää käyttää alkulukutaulukkoa, jotta ei tehdä tarpeettomia laskelmia: jos jokin annetuista luvuista on tässä taulukossa, se on jaollinen vain yhdellä ja itsellään. Katsotaanpa ratkaisua tällaiseen ongelmaan.
Esimerkki 1
Kunto: selvittää, ovatko luvut 275 ja 84 koprime.
Ratkaisu
Molemmilla luvuilla on selvästi useampi kuin yksi jakaja, joten emme voi heti kutsua niitä suhteellisen alkulukuiksi.
Laskemme suurimman yhteisen jakajan euklidisen algoritmin avulla: 275 = 84 3 + 23, 84 = 23 3 + 15, 23 = 15 1 + 8, 15 = 8 1 + 7, 8 = 7 1 + 1, 7 = 7 · 1.
Vastaus: koska GCD (84, 275) = 1, nämä luvut ovat suhteellisen alkulukuja.
Kuten aiemmin sanoimme, tällaisten numeroiden määritelmää voidaan laajentaa tapauksiin, joissa meillä ei ole kahta numeroa, vaan enemmän.
Määritelmä 2
Kokonaisluvut a 1 , a 2 , … , a k , k > 2 ovat keskenään alkulukuja, kun niillä on suurin yhteinen jakaja, joka on yhtä suuri kuin 1 .
Toisin sanoen, jos meillä on joukko lukuja, joiden suurin positiivinen jakaja on suurempi kuin 1, niin kaikki nämä luvut eivät ole keskenään käänteisiä toistensa suhteen.
Otetaan muutama esimerkki. Näin ollen kokonaisluvut − 99, 17 ja − 27 ovat suhteellisen alkulukuja. Mikä tahansa määrä alkulukuja on parriluku suhteessa kaikkiin populaation jäseniin, kuten sarjoissa 2, 3, 11, 19, 151, 293 ja 667. Mutta numerot 12, − 9, 900 ja − 72 eivät ole suhteellisen alkulukuja, koska ykseyden lisäksi niillä on vielä yksi positiivinen jakaja, joka on yhtä suuri kuin 3. Sama koskee lukuja 17, 85 ja 187: yhtä lukuun ottamatta ne kaikki voidaan jakaa 17:llä.
Yleensä lukujen keskinäinen ensisijaisuus ei ole ilmeinen ensi silmäyksellä, tämä tosiasia tarvitsee todisteita. Saadaksesi selville, ovatko jotkin luvut suhteellisen alkulukuja, sinun on löydettävä niiden suurin yhteinen jakaja ja tehtävä johtopäätös sen vertailun perusteella yhteen.
Esimerkki 2
Kunto: määrittää, ovatko luvut 331, 463 ja 733 suhteellisen alkulukuja.
Ratkaisu
Tarkastellaan alkulukutaulukkoa ja määritetään, että kaikki nämä kolme lukua ovat siinä. Silloin niiden yhteinen jakaja voi olla vain yksi.
Vastaus: kaikki nämä luvut ovat toistensa alkulukuja.
Esimerkki 3
Kunto: todista, että luvut − 14, 105, − 2 107 ja − 91 eivät ole alkulukuja.
Ratkaisu
Aloitetaan tunnistamalla niiden suurin yhteinen jakaja ja varmista sitten, että se ei ole yhtä suuri kuin 1. Siitä asti kun negatiivisia lukuja samat jakajat kuin vastaavat positiiviset, niin gcd (− 14, 105, 2 107, − 91) = gcd (14, 105, 2 107, 91). Sääntöjen mukaan, jotka annoimme artikkelissa suurimman yhteisen jakajan löytämisestä, gcd on tässä tapauksessa seitsemän.
Vastaus: seitsemän on suurempi kuin yksi, mikä tarkoittaa, että nämä luvut eivät ole suhteellisen alkulukuja.
Koalkilukujen perusominaisuudet
Tällaisilla luvuilla on joitain käytännössä tärkeitä ominaisuuksia. Listataan ne järjestyksessä ja todistetaan ne.
Määritelmä 3
Jos jaamme kokonaisluvut a ja b niiden suurinta yhteistä jakajaa vastaavalla luvulla, saadaan suhteellisen alkulukuja. Toisin sanoen a: gcd (a, b) ja b: gcd (a, b) ovat suhteellisen alkulukuja.
Olemme jo todistaneet tämän ominaisuuden. Todiste löytyy suurimman yhteisen jakajan ominaisuuksia käsittelevästä artikkelista. Sen ansiosta voimme määrittää suhteellisen alkulukujen parit: meidän tarvitsee vain ottaa mitkä tahansa kaksi kokonaislukua ja jakaa GCD:llä. Tämän seurauksena meidän pitäisi saada koprime-luvut.
Määritelmä 4
Välttämätön ja riittävä ehto lukujen a ja b keskinäiselle alkuluvulle on tällaisten kokonaislukujen olemassaolo u 0 Ja v 0, jolle tasa-arvo a · u 0 + b · v 0 = 1 tulee olemaan totta.
Todiste 1
Aloitetaan todistamalla tämän ehdon välttämättömyys. Oletetaan, että meillä on kaksi suhteellisen alkulukua, merkitty a ja b. Sitten tämän käsitteen määritelmän mukaan niiden suurin yhteinen jakaja on yhtä suuri kuin yksi. GCD:n ominaisuuksista tiedämme, että kokonaisluvuilla a ja b on Bezout-relaatio a · u 0 + b · v 0 = gcd (a, b). Siitä saamme sen a · u 0 + b · v 0 = 1. Tämän jälkeen meidän on todistettava ehdon riittävyys. Olkoon tasa-arvo a · u 0 + b · v 0 = 1 on totta tässä tapauksessa, jos GCD (a, b) jakaa ja a , ja b , silloin se myös jakaa summan a · u 0 + b · v 0, ja yksikkö, vastaavasti (tämä voidaan väittää jaollisuuden ominaisuuksien perusteella). Ja tämä on mahdollista vain jos GCD (a, b) = 1, joka todistaa a:n ja b:n keskinäisen yksinkertaisuuden.
Itse asiassa, jos a ja b ovat koprime, niin edellisen ominaisuuden mukaan yhtäläisyys on totta a · u 0 + b · v 0 = 1. Kerromme molemmat puolet c:llä ja saamme sen a · c · u 0 + b · c · v 0 = c. Voimme jakaa ensimmäisen termin a · c · u 0 + b · c · v 0 b:llä, koska tämä on mahdollista a · c:lle ja toinen termi on myös jaollinen b:llä, koska yksi tekijöistämme on yhtä suuri kuin b. Tästä päätämme, että koko summa voidaan jakaa b:llä, ja koska tämä summa on yhtä suuri kuin c, niin c voidaan jakaa b:llä.
Määritelmä 5
Jos kaksi kokonaislukua a ja b ovat yhteislukuja, niin gcd (a c, b) = gcd (c, b).
Todisteet 2
Osoitetaan, että GCD (a c, b) jakaa GCD:n (c, b) ja sen jälkeen, että GCD (c, b) jakaa GCD:n (a c, b), mikä on todiste yhtälön GCD oikeellisuudesta. (a · c, b) = GCD (c, b) .
Koska GCD (a · c, b) jakaa sekä a · c:n että b:n ja GCD (a · c, b) jakaa b, niin se jakaa myös b · c:n. Tämä tarkoittaa, että GCD (a c, b) jakaa sekä a c:n että b c:n, joten GCD:n ominaisuuksista johtuen se jakaa myös GCD:n (a c, b c), joka on yhtä suuri kuin c GCD (a, b ) = c . Siksi GCD (a · c, b) jakaa sekä b:n että c:n, joten se jakaa myös GCD:n (c, b).
Voidaan myös sanoa, että koska GCD (c, b) jakaa sekä c:n että b:n, niin se jakaa sekä c:n että a c:n. Tämä tarkoittaa, että GCD (c, b) jakaa sekä a · c:n että b:n, joten se jakaa myös GCD:n (a · c, b).
Siten gcd (a c, b) ja gcd (c, b) jakavat keskenään, mikä tarkoittaa, että ne ovat yhtä suuret.
Määritelmä 6
Jos numerot ovat sarjasta a 1 , a 2 , … , a k on suhteellisen alkuluku suhteessa sekvenssin numeroihin b 1, b 2, …, b m(luonnonarvoille k ja m), sitten niiden tuotteet a 1 · a 2 · … · a k Ja b 1 · b 2 · … · b m ovat myös suhteellisen hyviä, erityisesti a 1 = a 2 = … = a k = a Ja b 1 = b 2 = … = b m = b, Tuo a k Ja b m- molemminpuolisesti yksinkertainen.
Todisteet 3
Edellisen ominaisuuden mukaan voidaan kirjoittaa seuraavan muotoisia yhtäläisyyksiä: GCD (a 1 · a 2 · … · a k, b m) = GCD (a 2 · … · a k, b m) = … = GCD (a k, b m) = 1. Viimeisen siirtymän mahdollisuus varmistetaan sillä, että a k ja b m ovat ehdon mukaan suhteellisia alkulukuja. Tämä tarkoittaa, että GCD (a 1 · a 2 · … · a k , b m) = 1 .
Merkitään a 1 · a 2 · … · a k = A ja saadaan, että GCD (b 1 · b 2 · … · b m , a 1 · a 2 · … · a k) = GCD (b 1 · b 2 · … · bm, A) = GCD (b2 · … · b · b m, A) = … = GCD (bm, A) = 1. Tämä on totta johtuen yllä rakennetun ketjun viimeisestä yhtälöstä. Näin ollen meillä on yhtälö GCD (b 1 · b 2 · … · b m, a 1 · a 2 · … · a k) = 1, jolla voimme todistaa tulojen keskinäisen primeness a 1 · a 2 · … · a k Ja b 1 · b 2 · … · b m
Nämä ovat kaikki koprime-lukujen ominaisuudet, joista haluamme kertoa sinulle.
Pareittainen alkulukujen käsite
Kun tiedämme, mitä yhteisalkuluvut ovat, voimme muodostaa määritelmän parittaisille alkuluvuille.
Määritelmä 7
Parittaiset alkuluvut on sarja kokonaislukuja a 1 , a 2 , ... , a k , jossa jokainen luku on suhteellisen alkuluku suhteessa muihin.
Esimerkki parittaisten alkulukujen sarjasta olisi 14, 9, 17 ja −25. Tässä kaikki parit (14 ja 9, 14 ja 17, 14 ja −25, 9 ja 17, 9 ja −25, 17 ja −25) ovat koprime. Huomaa, että keskinäisen alkuluvun ehto on pakollinen parittaisille alkuluvuille, mutta keskinäiset alkuluvut eivät ole parittaisia alkulukuja kaikissa tapauksissa. Esimerkiksi sarjoissa 8, 16, 5 ja 15 luvut eivät ole tällaisia lukuja, koska 8 ja 16 eivät ole suhteellisen alkulukuja.
Sinun tulisi myös pohtia tietyn määrän alkulukujen kokoelman käsitettä. Ne ovat aina sekä keskenään että pareittain yksinkertaisia. Esimerkki olisi sekvenssi 71, 443, 857, 991. Alkulukujen tapauksessa keskinäisen ja parin alkuluvun käsitteet osuvat yhteen.
Jos huomaat tekstissä virheen, korosta se ja paina Ctrl+Enter
Määritelmä1. Kokonaisluvut a 1,a 2,…,a k kutsutaan yhteisalkuluvuksi, jos (a 1 ,a 2 ,…,a k) =1
Määritelmä 2. Kokonaislukuja a 1,a 2,…,a k kutsutaan pareittain koprimeiksi, jos i,s (i, s = 1, 2, .. , k, is, (a i, a s) =1) .
Jos luvut täyttävät määritelmän 2, silloin ne täyttävät määritelmän 1. Käänteinen väite on yleensä epätosi, esimerkiksi: (15, 21, 19) = 1, mutta (15, 21) = 3
Lause (yhteisalkuperuste)
(a, b) = 1<=> x, y Z: ax + by = 1
Todiste:
Todistakaamme tarpeellisuus. Olkoon (a, b) = 1. Yllä osoitimme, että jos d = (a, b), niin x, y Z: d = ax + by.
Koska tässä tapauksessa d =1, silloin tulee x, y Z (määritetty euklidisesta algoritmista): 1 = ax + bу.
Riittävyys. Olkoon (*) ax + by = 1, todistetaan, että (a, b) = 1. Oletetaan, että (a, b) = d, sitten yhtälön (*) vasemmalla puolella
(a / d ) & ( b/d ) => (ah + by) /d => (1/d) => (d=l) => (a, b) = 1.
§4. Kokonaislukujen nok ja sen ominaisuudet.
Määritelmä 1. Nollasta poikkeavan äärellisen kokonaislukujoukon a 1,a 2,…,a k yhteinen kerrannainen on kokonaisluku m, joka on jaollinen kaikilla luvuilla a i (i=l, 2,…, k)
Määritelmä 2. Kokonaislukua (m) kutsutaan nollasta poikkeavien lukujen a 1, a 2,..., a k pienimmäksi yhteiseksi kerrannaiseksi, jos:
1 m - on niiden yhteinen kerrannainen;
2 (m) jakaa näiden lukujen minkä tahansa muun yhteisen kerrannaisen.
Nimitys: m = LCM (a 1,a 2,…,a k) tai m = [a 1,a 2,…,a k]
Esimerkki. Numerot on annettu: 2, 3, 4, 6, 12.
Luvut 12, 24. 48. 96 ovat lukujen 2, 3, 4, 6, 12 yhteisiä kerrannaisia. Pienin yhteinen kerrannainen on luku 12. ts.
LCM määritetään yksilöllisesti tekijöiden järjestyksen mukaan. Todellakin, jos oletetaan, että m 1 = [a, b] & m 2 = (m 1 / m 2) & (m 2 / m 1) => [(m 1 = m 2) v (m 1 = - m 2)]. Kahden kokonaisluvun pienimmän yhteiskerran ja suurimman yhteisen jakajan välillä on suhde, joka ilmaistaan kaavalla: [a, b] = ab/(a, b) (johdat itse)
Tämän yhteyden avulla voimme todeta, että jokaisella muulla kokonaislukuparilla kuin nolla on niiden pienin yhteinen kerrannainen. Todellakin, (a, b) voidaan aina yksiselitteisesti päätellä euklidisesta algoritmista ja määritelmän mukaan (a, b) 0, silloin murto-osa ab/(a, b) 0 määritetään yksiselitteisesti.
Kahden kokonaisluvun LCM on helpoimmin laskettavissa, kun (a, b) = 1, silloin [a, b] = ab/1 = a b
Esimerkiksi = 215/1 = 105, koska (21, 5) = 1.
§5. Alkuluvut ja niiden ominaisuudet.
Määritelmä 1. Luonnollista lukua (p) kutsutaan alkuluvuksi, jos p > 1 ja sillä ei ole positiivista lukua. muut jakajat kuin 1 ja p.
Määritelmä 2. Luonnollista lukua a > 1, jolla on 1:n lisäksi muita positiivisia jakajia ja itseään kutsutaan yhdistelmäluvuksi.
Näistä määritelmistä seuraa, että luonnollisten lukujen joukko voidaan jakaa kolmeen luokkaan:
a) yhdistelmäluvut;
b) alkuluvut;
c) yksikkö.
Jos a on komposiitti, niin a = nq, missä 1 Tehtävä 1. Todista, että jos aZ ja p ovat alkuluku, niin (a, p) = 1 v (a / p) Todiste. Olkoon d = (a, p) =>
(a /d) & (p /d), koska p on alkuluku, silloin sillä on kaksi jakajaa 1 ja p. Jos (a, p) = 1, niin a ja p ovat suhteellisen alkulukuja, jos (a, p) = p, niin (a/p). Tehtävä 2. Jos usean tekijän tulo on jaollinen p:llä, niin ainakin yksi tekijöistä on jaollinen p:llä. Ratkaisu. Anna tuotteen (a 1,a 2, ...,
ja k)/р, jos kaikki a i eivät ole jaollisia p:llä, tulo on koprime p:n kanssa, joten jokin tekijä on jaollinen p:llä. Tehtävä 3. Osoita, että kokonaisluvun a>1 pienin ei-1 jakaja on alkuluku. Todiste. Olkoon aZ ja a yhdistelmäluku (jos a = p, niin väite on todistettu), niin a = a 1 q. Olkoon q pienin jakaja, näytämme, että se on alkuluku. Jos oletetaan, että q on yhdistelmäluku, niin q = q 1 k ja a = a 1 q 1 k, koska q 1 Tehtävä 4. Osoita, että luonnollisen luvun (n) pienin alkujakaja (p) ei ylitä arvoa n. Todiste. Olkoon n = pn 1 ja p< n 1
и р - простое. Тогда n
р 2
=>R<n
. Tästä väitteestä seuraa, että jos luonnollinen luku (n) ei ole jaollinen millään alkuluvulla p n, niin n on alkuluku, muuten se on yhdistelmä. Esimerkki 1. Selvitä, onko 137 alkuluku? yksitoista<137
<12. Kirjataan muistiin alkutekijät, jotka eivät ylitä 137: 2, 3, 5, 7, 11. Tarkistamme, että 137 ei ole jaollinen luvuilla 2, 3, 5, 7, 11. Siksi luku 137 on alkuluku. Eukleideen lause. Alkulukujen joukko on ääretön. Todiste. Oletetaan päinvastoin, olkoon p 1 ,p 2, ...,
p k ovat kaikki alkulukuja, joissa p 1 = 2 ja p k on suurin alkuluku. Muodostetaan luonnollinen luku = p 1 p 2 ...
p +1, koska p i , silloin sen täytyy olla komposiitti, silloin sen pienin jakaja on alkuluku (katso Tehtävä 3). ei kuitenkaan ole jaollinen luvuilla p 1, p 2,... tai p k, koska 1 ei ole jaollinen millään p I:llä. Siksi olettamuksemme, että alkulukujen joukko on äärellinen, oli virheellinen. On kuitenkin olemassa lause, jonka mukaan alkuluvut muodostavat vain pienen osan luonnollisista luvuista. Intervallilause. Luonnollisessa sarjassa on mielivaltaisen pitkiä välejä, jotka eivät sisällä yhtä alkulukua. Todiste. Otetaan mielivaltainen luonnollinen luku (n) ja luodaan luonnollisten lukujen sarja (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1). Tässä sarjassa jokainen seuraava luku on 1 suurempi kuin edellinen, koska kaikki nämä luvut ovat yhdistettyjä jokaisella on enemmän kuin kaksi jakajaa (esimerkiksi ensimmäinen luku on jaollinen 1:llä, 2:lla ja itsellään). Koska n→∞ saamme mielivaltaisen pitkän välin, joka koostuu vain yhdistelmäluvuista. Eukleideen lause ja intervallilause osoittavat alkulukujakauman monimutkaisen luonteen luonnollisessa sarjassa. Aritmetiikan peruslause Mikä tahansa luonnollinen luku n>1 voidaan esittää ainutlaatuisella tavalla alkulukujen tulona tekijöiden järjestykseen asti. Todiste. Todistakaamme edustuksen mahdollisuus: Olkoon nN ja n>1, jos n on alkuluku, niin n = p ja lause on todistettu. Jos n on yhdistetty, niin sen pienin jakaja on alkuluku ja n = p 1 n 1 , missä n 1 Seuraavaksi väittelemme samalla tavalla. Jos n 1 on alkuluku, niin lause on todistettu, jos n 1 on yhdistelmäluku, niin n 1 = p 2 n 2, missä n 2< n 1
и тогда n
= p 1 p 2 n 2
. На каком-то шаге получим n
= p 1 p 2
…p n
, где все p i
- простые числа. Todistakaamme hajoamisen ainutlaatuisuus: Oletetaan, että luvulle (n) on kaksi erilaista esitystapaa: n = p 1 p 2 …p k, n = q 1 q 2 …q n ja n>k. Sitten saadaan, että p 1 p 2 …p k = q 1 q 2 …q n (1). Yhtälön (1) vasen puoli on jaollinen p 1 :llä, jolloin alkulukujen ominaisuudella (katso Tehtävä 2) ainakin yhden oikean puolen tekijöistä on oltava jaollinen p 1 :llä. Olkoon (q 1 /p 1) => (q 1 =p 1). Jakamalla yhtälön (1) molemmat puolet p 1:llä, saadaan yhtäläisyys p 2 p 3 …p k = q 2 q 3 …q n. Toistamalla edellinen päättely vielä (k-1) kertaa, saadaan yhtälö 1 = q k +1 q k +2 …q n , koska kaikki q i >1, niin tämä yhtäläisyys on mahdoton. Näin ollen molemmissa laajennuksissa tekijöiden lukumäärä on sama (k=n) ja itse tekijät ovat samat. Kommentti. Kun luku (n) jaetaan yksinkertaisiksi tekijöiksi, osa niistä saattaa toistua. Merkitsemällä kirjaimilla 1 , 2 ,…, k niiden esiintymisen moninkertaisuutta kohdassa (n), saadaan luvun (n) ns. kanoninen laajennus: Esimerkki 2. Kanoninen luvun 588000 laajennus = 2 5 35 3 7 2 Seuraus 1. Jos Esimerkki 3. Kaikki luvun 720 = 2 4 3 2 5 jakajat saadaan, jos lausekkeessa Vaaditut jakajat ovat yhtä suuria kuin: 1; 2; 4; 8; 16; 3; 6; 12; 24; 48; 9; 18; 36; 72; 144; 5; 10; 20; 40; 80; 15; kolmekymmentä; 60; 120; 240; 45; 90; 180; 360; 720. Seuraus 2. Jos P 1 1 p 2 2 …p k k, missä i = max( I , i). Esimerkki 4. Etsi GCD(a, b) ja LCM(a, b) käyttämällä kanonista laajennusta if (24,
42) = 23
= 6 $p$ kutsutaan alkuluvuksi, jos sillä on vain $2$ jakaja: $1$ ja itse. Luonnollisen luvun $a$ jakaja on luonnollinen luku, joka jakaa alkuperäisen luvun $a$ jättämättä jäännöstä. Esimerkki 1 Etsi luvun $6$ jakajat. Ratkaisu: Meidän on löydettävä kaikki luvut, joilla annettu luku $6$ on jaollinen ilman jäännöstä. Nämä ovat numerot: $1,2,3,6$. Joten luvun $6$ jakaja on luvut $1,2,3,6.$ Vastaus: $1,2,3,6$. Tämä tarkoittaa, että luvun jakajien löytämiseksi sinun on löydettävä kaikki luonnolliset luvut, joihin annettu luku on jaollinen ilman jäännöstä. On helppo nähdä, että luku $1$ on minkä tahansa luonnollisen luvun jakaja. Määritelmä 2 Komposiitti He kutsuvat numeroa, jolla on muita jakajia yhden ja itsensä lisäksi. Esimerkki alkuluvusta olisi luku $13$, esimerkki yhdistelmäluvusta olisi $14.$ Huomautus 1 Lukulla $1$ on vain yksi jakaja - itse luku, joten se ei ole alkuluku eikä yhdistelmä. Määritelmä 3 Keskinäiset alkuluvut ne ovat niitä, joiden gcd on yhtä suuri kuin $1$. Tämä tarkoittaa, että saadaksesi selville, ovatko luvut suhteellisen ensisijaisia, sinun on löydettävä niiden gcd ja verrattava sitä arvoon $1. Määritelmä 4 Jos lukujoukossa mitkä tahansa kaksi ovat yhteisalkulukuja, tällaisia lukuja kutsutaan pareittain koprime. Kahden luvun käsitteet "koprime" ja "parittainen koprime" ovat samat. Esimerkki 2 8 dollaria, 15 dollaria - ei yksinkertainen, mutta suhteellisen yksinkertainen. $6, 8, 9$ ovat alkulukuja, mutta eivät parittaisia alkulukuja. $8, 15, 49 $ ovat pareittain suhteellisen prime. Kuten näemme, sen määrittämiseksi, ovatko luvut suhteellisen alkulukuja, ne on ensin otettava huomioon alkutekijöihin. Kiinnitämme huomiota siihen, kuinka tämä tehdään oikein. Otetaan esimerkiksi luku $180$ alkutekijöihin: 180 $=2\cdot 2\cdot 3\cdot 3\cdot 5$ Käyttäkäämme voimien omaisuutta, niin saamme, 180 $=2^2\cdot 3^2\cdot 5$ Tätä alkutekijöiksi hajoamisen merkintää kutsutaan kanoniseksi, ts. jotta luku voidaan kertoa kanonisessa muodossa, on tarpeen käyttää potenssien ominaisuutta ja esittää luku eri kantalukujen potenssien tulona Luonnollisen luvun kanoninen laajennus yleisessä muodossa on muotoa: $m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$ missä $p_1,p_2\pisteet \pisteet .p_k$ ovat alkulukuja ja eksponentit ovat luonnollisia lukuja. Lukujen esittäminen kanonisena jaotteluna alkujoukkoon helpottaa lukujen suurimman yhteisen jakajan löytämistä, ja se toimii koprime-lukujen todistuksen tai määritelmän seurauksena. Esimerkki 3 Etsi lukujen $180$ ja $240$ suurin yhteinen jakaja. Ratkaisu: Jaetaan luvut yksinkertaisiksi joukoiksi käyttämällä kanonista hajotusta 180 $=2\cdot 2\cdot 3\cdot 3\cdot 5$, sitten 180 $=2^2\cdot 3^2\cdot 5$ 240 $=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, sitten $240=2^4\cdot 3\cdot 5$ Etsitään nyt näiden lukujen gcd, tätä varten valitaan potenssit, joilla on sama kanta ja pienin eksponentti, sitten $GCD\(180;240)= 2^2\cdot 3\cdot 5=60$ Säveldään algoritmi GCD:n löytämiseksi ottaen huomioon kanonisen tekijöiden jakamisen alkutekijöiksi. Jotta voit löytää kahden luvun suurimman yhteisen jakajan kanonisen laajennuksen avulla, sinun on: Esimerkki 4 Selvitä, ovatko luvut $195$ ja $336$ alkulukuja. 195 dollaria = 3\cdot 5\cdot 13 $ 336 $=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$ $GCD\(195;336) =3\cdot 5=15$ Näemme, että näiden lukujen gcd eroaa $1$:sta, mikä tarkoittaa, että luvut eivät ole suhteellisen alkulukuja. Näemme myös, että jokainen luku sisältää tekijöitä $1$:n ja itse luvun lisäksi, mikä tarkoittaa, että luvut eivät ole alkulukuja, vaan yhdistelmä. Esimerkki 5 Selvitä, ovatko luvut $39$ ja $112$ alkulukuja. Ratkaisu: Käytetään kanonista tekijöiden jakoa: 112 $=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$ $GCD\(39;112)=1$ Näemme, että näiden lukujen gcd on yhtä suuri kuin $1$, mikä tarkoittaa, että luvut ovat suhteellisen alkulukuja. Näemme myös, että jokainen luku sisältää tekijöitä $1$:n ja itse luvun lisäksi, mikä tarkoittaa, että luvut eivät ole alkulukuja, vaan yhdistelmä. Esimerkki 6 Selvitä, ovatko luvut $883$ ja $997$ alkulukuja. Ratkaisu: Käytetään kanonista tekijöiden jakoa: $883=1\cdot 883$ $997=1\cdot 997$ $GCD\(883;997)=1$ Näemme, että näiden lukujen gcd on yhtä suuri kuin $1 $, mikä tarkoittaa, että luvut ovat suhteellisen alkulukuja. Näemme myös, että jokainen luku sisältää vain kertoimet, jotka ovat yhtä suuria kuin $1$ ja itse luvun, mikä tarkoittaa, että luvut ovat alkulukuja.
silloin kaikilla luvun (n) jakajilla on muoto: 
missä 0 i i (i = 1, 2,…,k).
1, 2, 3 sijasta korvaamme toisistaan riippumatta seuraavat arvot: 1 =0, 1, 2, 3, 4, 2 =0, 1, 2, 3 = 0, 1.
Ja 
sitten (a, b) = p 1 1 p 2 2 …p k k , missä i = min( I , i)
Koprime-luvut
Parillinen koprime
Alkutekijähajotelma
Luonnollisen luvun kanoninen laajennus yleisessä muodossa
Ladataan...
