Zasada liczb wzajemnie pierwszych. Liczby względnie pierwsze: definicja, przykłady i własności

$ p $ nazywa się liczbą pierwszą, jeśli ma tylko 2 $ dzielnik: 1 $ i samą siebie.

Dzielnik liczby naturalnej $ a $ jest liczbą naturalną, przez którą pierwotna liczba $ a $ jest podzielna bez reszty.

Przykład 1

Znajdź dzielniki 6 $.

Rozwiązanie: Musimy znaleźć wszystkie liczby, przez które dana liczba 6 $ jest podzielna bez reszty. Będą to liczby: 1,2,3, 6 USD. Zatem dzielnikiem liczby $ 6 $ będą liczby $ 1,2,3,6

Odpowiedź: 1,2,3,6 USD.

Aby znaleźć dzielniki liczby, musisz znaleźć wszystkie liczby całkowite, na które dane jest dzielone bez reszty. Łatwo zauważyć, że liczba $ 1 $ będzie dzielnikiem dowolnej liczby naturalnej.

Definicja 2

Złożony wywoływana jest liczba, która oprócz jednego i samego siebie ma inne dzielniki.

Przykładem liczby pierwszej jest 13 $, przykładem liczby złożonej 14 $

Uwaga 1

Liczba $ 1 $ ma tylko jeden dzielnik, tę samą liczbę, więc nie jest klasyfikowana ani jako pierwsza, ani jako złożona.

Wzajemnie pierwsze liczby

Definicja 3

Wzajemnie pierwsze liczby nazywane są tymi, których gcd wynosi 1 $, więc aby dowiedzieć się, czy liczby będą względnie pierwsze, musisz znaleźć ich gcd i porównać je z 1 $.

parami względnie pierwszymi

Definicja 4

Jeżeli w zbiorze liczb dowolne dwie są względnie pierwsze, to takie liczby nazywamy parami względnie pierwszymi... W przypadku dwóch liczb pojęcia „coprime” i „pairwise coprime” są zbieżne.

Przykład 2

8 USD, 15 USD - nie proste, ale wzajemnie proste.

6, 8, 9 $ - liczby względnie pierwsze, ale nie pary względnie pierwsze.

8, 15, 49 $ - parami względnie pierwsze.

Jak widać, aby ustalić, czy liczby są względnie pierwsze, należy je najpierw rozłożyć na czynniki pierwsze. Zwróćmy uwagę, jak to zrobić poprawnie.

Rozkład na czynniki pierwsze

Na przykład podzielmy liczbę 180 $ na czynniki pierwsze:

180 $ = 2 \ cdot 2 \ cdot 3 \ cdot 3 \ cdot 5 $

Korzystamy z własności stopni, wtedy otrzymujemy

180 $ = 2 ^ 2 \ cdot 3 ^ 2 \ cdot 5 $

To zapisanie rozkładu na czynniki pierwsze nazywa się kanonicznym, tj. w celu rozłożenia liczby na czynniki w postaci kanonicznej konieczne jest użycie właściwości stopni i przedstawienie liczby jako iloczynu stopni o różnych podstawach

Ogólny rozkład kanoniczny liczby naturalnej

Rozkład kanoniczny liczby naturalnej w ogólna perspektywa wygląda jak:

$ m = p ^ (n1) _1 \ cdot p ^ (n2) _2 \ cdot \ dots \ dots .. \ cdot p ^ (nk) _k $

gdzie $ p_1, p_2 \ kropki \ kropki .p_k $ są liczbami pierwszymi, a wykładniki są liczbami naturalnymi.

Przedstawienie liczby w postaci rozkładu kanonicznego na zbiory pierwsze ułatwia znalezienie największego wspólnego dzielnika liczb i działa jako konsekwencja dowodu lub definicji liczb względnie pierwszych.

Przykład 3

Znajdź największy wspólny dzielnik 180 i 240 USD.

Rozwiązanie: Rozłóż liczby na zbiory pierwsze za pomocą rozkładu kanonicznego

180 $ = 2 \ cdot 2 \ cdot 3 \ cdot 3 \ cdot 5 $, wtedy 180 $ = 2 ^ 2 \ cdot 3 ^ 2 \ cdot 5 $

240 $ = 2 \ cdot 2 \ cdot 2 \ cdot 2 \ cdot 3 \ cdot 5 $, potem 240 $ = 2 ^ 4 \ cdot 3 \ cdot 5 $

Teraz znajdujemy NWD tych liczb, w tym celu wybieramy stopnie z na tej samej podstawie i z najmniejszym wykładnikiem, wtedy

$ Gcd \ (180; 240) = 2 ^ 2 \ cdot 3 \ cdot 5 = 60 $

skomponujmy algorytm znajdowania GCD z uwzględnieniem faktoryzacji kanonicznej.

Aby znaleźć największy wspólny dzielnik dwóch liczb za pomocą rozkładu kanonicznego, potrzebujesz:

rozłożyć liczby na czynniki pierwsze w formie kanonicznej
wybierz stopnie o tej samej podstawie iz najmniejszym wykładnikiem zawartym w rozkładzie tych liczb
Znajdź iloczyn liczb znalezionych w kroku 2. Otrzymana liczba będzie pożądanym największym wspólnym dzielnikiem.

Przykład 4

Ustal, czy liczby 195 $ i 336 $ są liczbami pierwszymi, względnie pierwszymi.

195 $ = 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 $

Widzimy, że gcd tych liczb różni się od 1 $, co oznacza, że liczby nie są względnie pierwsze. Widzimy też, że w skład każdej z liczb oprócz 1$ i samej liczby wchodzą czynniki, co oznacza, że liczby pierwsze też nie będą, ale będą złożone.

Przykład 5

Ustal, czy liczby 39 $ i 112 $ są liczbami pierwszymi, względnie pierwszymi.

Rozwiązanie: Użyjmy faktoryzacji kanonicznej do faktoryzacji:

112 $ = 2 \ cdot 2 \ cdot 2 \ cdot 2 \ cdot 7 = 2 ^ 4 \ cdot 7 $

$ Gcd \ (39; 112) = 1 $

Widzimy, że gcd tych liczb jest równe 1 $, co oznacza, że liczby są względnie pierwsze. Widzimy też, że w skład każdej z liczb oprócz 1$ i samej liczby wchodzą czynniki, co oznacza, że liczby pierwsze też nie będą, ale będą złożone.

Przykład 6

Ustal, czy liczby 883 $ i 997 $ będą liczbami pierwszymi, względnie pierwszymi.

Rozwiązanie: Użyjmy faktoryzacji kanonicznej do faktoryzacji:

883 $ = 1 \ cdot 883 $

997 $ = 1 \ cdot 997 $

$ Gcd \ (883; 997) = 1 $

Widzimy, że gcd tych liczb jest równe 1 $, co oznacza, że liczby są względnie pierwsze. Widzimy również, że każda z liczb zawiera tylko czynniki równe 1 $ i samą liczbę, co oznacza, że liczby będą pierwsze.

Co to są liczby względnie pierwsze?

Definicja względnych liczb pierwszych

Definicja liczb względnie pierwszych:

Liczby względnie pierwsze to liczby całkowite, które nie mają wspólnego dzielnika innego niż jeden.

Przykłady względnych liczb pierwszych

Przykład liczb względnie pierwszych:

2 i 3 nie mają innych wspólnych czynników oprócz jednego.

Inny przykład wzajemnie pierwszych liczb:

3 i 7 nie mają innych wspólnych czynników oprócz jednego.

Inny przykład wzajemnie pierwszych liczb:

11 i 13 nie mają innych wspólnych czynników oprócz jednego.

Teraz możemy odpowiedzieć na pytanie, co oznaczają liczby względnie pierwsze.

Co oznaczają liczby względnie pierwsze?

Są to liczby całkowite, które nie mają wspólnych dzielników innych niż jeden.

Dwie liczby względnie pierwsze

Każda z tych par ma dwie liczby względnie pierwsze.

11 i 15
15 i 16
16 i 23

Wspólne dzielniki liczb względnie pierwszych

Wspólne dzielniki liczb względnie pierwszych to tylko jeden, co wynika z definicji liczb względnie pierwszych.

Największy wspólny dzielnik liczb względnie pierwszych

Największym wspólnym dzielnikiem liczb względnie pierwszych jest jeden, który wynika z definicji liczb względnie pierwszych.

Czy liczby są względnie pierwsze?

Czy 3 i 13 są względnie pierwsze? Tak, ponieważ nie mają wspólnych dzielników poza jednym.

Czy 3 i 12 są względnie pierwsze? Nie, ponieważ ich wspólnymi dzielnikami są 1 i 3. A z definicji liczb względnie pierwszych tylko jedna powinna być wspólnym dzielnikiem.

Czy 3 i 108 są względnie pierwsze? Nie, ponieważ ich wspólnymi dzielnikami są 1 i 3. A z definicji liczb względnie pierwszych tylko jedna powinna być wspólnym dzielnikiem.

Czy 108 i 5 są względnie pierwsze? Tak, ponieważ nie mają wspólnych dzielników poza jednym.

W tym artykule porozmawiamy o tym, czym są liczby względnie pierwsze. W pierwszej części formułujemy definicje dla dwóch, trzech lub więcej liczb względnie pierwszych, podajemy kilka przykładów i pokazujemy, w jakich przypadkach dwie liczby można uznać za pierwsze względem siebie. Następnie przejdźmy do sformułowania głównych właściwości i ich dowodów. W ostatnim akapicie omówimy pokrewną koncepcję - liczby pierwsze parami.

Yandex.RTB R-A-339285-1

Czym są liczby względnie pierwsze

Dwie liczby całkowite mogą być wzajemnie pierwsze lub ich duża ilość... Na początek wprowadzamy definicję dwóch liczb, dla których potrzebujemy pojęcia ich największego wspólnego dzielnika. W razie potrzeby powtórz poświęcony mu materiał.

Definicja 1

Dwie takie liczby a i b będą wzajemnie pierwsze, których największym wspólnym dzielnikiem jest 1, tj. NWD (a, b) = 1.

Z ta definicja możemy wywnioskować, że jedyny dodatni wspólny dzielnik dwóch liczb względnie pierwszych będzie równy 1. Tylko dwie takie liczby mają dwa wspólne czynniki - jeden i minus jeden.

Jakie są przykłady liczb względnie pierwszych? Na przykład taka para to 5 i 11. Mają tylko jeden wspólny dodatni dzielnik równy 1, co jest potwierdzeniem ich wzajemnej prostoty.

Jeśli weźmiemy dwie liczby pierwsze, to w stosunku do siebie będą one we wszystkich przypadkach wzajemnie pierwsze, ale takie wzajemne relacje tworzą się również między liczbami złożonymi. Zdarzają się przypadki, gdy jedna liczba w parze wzajemnie pierwszych jest złożona, a druga jest liczbą pierwszą lub obie są złożone.

To stwierdzenie ilustruje następujący przykład: liczby złożone - 9 i 8 tworzą parę względnie pierwszych. Udowodnijmy to, obliczając ich największy wspólny dzielnik. Aby to zrobić, zapisz wszystkie ich dzielniki (zalecamy ponowne przeczytanie artykułu o znajdowaniu dzielników liczby). Dla 8 będą to liczby ± 1, ± 2, ± 4, ± 8, a dla 9 - ± 1, ± 3, ± 9. Spośród wszystkich dzielników wybieramy ten, który będzie wspólny i największy – to jest jeden. Dlatego, jeśli NWD (8, - 9) = 1, to 8 i - 9 będą względem siebie pierwsze.

500 i 45 nie są wzajemnie pierwszymi liczbami, ponieważ mają inny wspólny dzielnik - 5 (patrz artykuł o kryteriach podzielności przez 5). Pięć jest większe niż jeden i jest liczbą dodatnią. Inną podobną parą może być - 201 i 3, ponieważ obie można podzielić przez 3, na co wskazuje odpowiednie kryterium podzielności.

W praktyce często konieczne jest wyznaczenie wzajemnej prostoty dwóch liczb całkowitych. Odkrycie tego można sprowadzić do znalezienia największego wspólnego dzielnika i porównania go z jednością. Wygodnie jest również korzystać z tabeli liczb pierwszych, aby nie dokonywać niepotrzebnych obliczeń: jeśli jedna z podanych liczb znajduje się w tej tabeli, to jest podzielna tylko przez jeden i przez siebie. Przeanalizujmy rozwiązanie podobnego problemu.

Przykład 1

Stan: schorzenie: dowiedz się, czy 275 i 84 są względnie pierwsze.

Rozwiązanie

Obie liczby mają wyraźnie więcej niż jeden dzielnik, więc nie możemy ich od razu nazwać względnie pierwszymi.

Oblicz największy wspólny dzielnik za pomocą algorytmu Euklidesa: 275 = 84 3 + 23, 84 = 23 3 + 15, 23 = 15 1 + 8, 15 = 8 1 + 7, 8 = 7 1 + 1, 7 = 7 1.

Odpowiedź: ponieważ NWD (84, 275) = 1, to liczby te będą względnie pierwsze.

Jak powiedzieliśmy wcześniej, definicję takich liczb można rozszerzyć na przypadki, gdy mamy nie dwie liczby, ale więcej.

Definicja 2

Liczby całkowite a 1, a 2,…, a k, k> 2 będą wzajemnie pierwsze, jeśli mają największy wspólny dzielnik równy 1.

Innymi słowy, jeśli mamy zbiór liczb o największym dodatnim dzielniku większym niż 1, to wszystkie te liczby nie są wzajemnie odwrotne względem siebie.

Weźmy kilka przykładów. Tak więc liczby całkowite - 99, 17 i - 27 - są względnie pierwsze. Dowolna liczba liczb pierwszych będzie wzajemnie pierwsza dla wszystkich członków populacji, na przykład w sekwencji 2, 3, 11, 19, 151, 293 i 667. Ale liczby 12, - 9, 900 i − 72 Nie będą względnie pierwsze, bo oprócz jedności będą miały jeszcze jeden dodatni dzielnik równy 3. To samo dotyczy liczb 17, 85 i 187: oprócz jednej można je wszystkie podzielić przez 17.

Zwykle wzajemna prostota liczb nie jest na pierwszy rzut oka oczywista, trzeba to udowodnić. Aby dowiedzieć się, czy niektóre liczby będą względnie pierwsze, musisz znaleźć ich największy wspólny dzielnik i wyciągnąć wniosek na podstawie porównania ich z jednością.

Przykład 2

Stan: schorzenie: Sprawdź, czy liczby 331, 463 i 733 są względnie pierwsze.

Rozwiązanie

Sprawdźmy w tabeli liczb pierwszych i ustalmy, że są w niej wszystkie trzy z tych liczb. Wtedy tylko jeden może być ich wspólnym dzielnikiem.

Odpowiedź: wszystkie te liczby będą względem siebie względem siebie pierwsze.

Przykład 3

Stan: schorzenie: przedstawić dowód, że liczby - 14, 105, - 2 107 i - 91 nie są względnie pierwsze.

Rozwiązanie

Zacznijmy od określenia ich największego wspólnego dzielnika, po czym upewnimy się, że nie jest on równy 1. Ponieważ liczby ujemne mają takie same dzielniki jak odpowiadające im liczby dodatnie, to NWD (-14, 105, 2 107, - 91) = NWD (14, 105, 2 107, 91). Zgodnie z zasadami, które podaliśmy w artykule dotyczącym znajdowania największego wspólnego dzielnika, w tym przypadku NWD będzie równe siedmiu.

Odpowiedź: siedem to więcej niż jeden, co oznacza, że liczby te nie są wzajemnie pierwsze.

Podstawowe własności liczb względnie pierwszych

Takie liczby mają kilka praktycznie ważne właściwości... Wymieniamy je w kolejności i udowadniamy.

Definicja 3

Jeśli podzielimy liczby całkowite a i b przez liczbę odpowiadającą ich największemu wspólnemu dzielnikowi, otrzymamy liczby względnie pierwsze. Innymi słowy, a: gcd (a, b) i b: gcd (a, b) będą względnie pierwsze.

Udowodniliśmy już tę właściwość. Dowód można znaleźć w artykule o własnościach największego wspólnego dzielnika. Dzięki niemu możemy wyznaczyć pary wzajemnie pierwszych liczb: wystarczy wziąć dowolne dwie liczby całkowite i podzielić przez NWD. W rezultacie powinniśmy otrzymać wzajemnie liczby pierwsze.

Definicja 4

Warunkiem koniecznym i wystarczającym wzajemnej prostoty liczb a i b jest istnienie takich liczb całkowitych ty 0 oraz v 0 dla której równość a u 0 + b v 0 = 1 będzie prawdziwe.

Dowód 1

Zacznijmy od udowodnienia konieczności tego warunku. Powiedzmy, że mamy dwie liczby względnie pierwsze, oznaczone a i b. Wtedy, zgodnie z definicją tego pojęcia, ich największy wspólny dzielnik będzie równy jeden. Z właściwości NWD wiemy, że dla liczb całkowitych a i b istnieje relacja Bezout a u 0 + b v 0 = gcd (a, b)... Z tego otrzymujemy to a u 0 + b v 0 = 1... Następnie musimy udowodnić wystarczalność warunku. Niech równość a u 0 + b v 0 = 1 będzie prawdziwe, w takim przypadku, jeśli Gcd (a, b) dzieli i a , i b, to podzieli i suma a u 0 + b v 0, i odpowiednio jedność (można to stwierdzić na podstawie właściwości podzielności). A jest to możliwe tylko wtedy, gdy Gcd (a, b) = 1, co świadczy o wzajemnej prostocie a i b.

Rzeczywiście, jeśli a i b są względnie pierwsze, to zgodnie z poprzednią własnością równość a u 0 + b v 0 = 1... Mnożymy obie strony przez c i otrzymujemy to a c u 0 + b c v 0 = c... Możemy podzielić pierwszy termin a c u 0 + b c v 0 przez b, ponieważ jest to możliwe dla a · c, a drugi wyraz jest również podzielny przez b, ponieważ jeden z naszych czynników jest równy b. Z tego wnioskujemy, że całą kwotę można podzielić przez b, a ponieważ ta kwota jest równa c, to c można podzielić przez b.

Definicja 5

Jeśli dwie liczby całkowite a i b są względnie pierwsze, to NWD (a c, b) = NWD (c, b).

Dowód 2

Udowodnijmy, że NWD (a c, b) podzieli NWD (c, b), a następnie - że NWD (c, b) podzieli NWD (a c, b), co udowodni, że równość NWD (a C, b ) = gcd (c, b).

Ponieważ NWD (ac, b) dzieli oba ac i b, a NWD (ac, b) dzieli b, podzieli również bc. Oznacza to, że NWD (a c, b) dzieli zarówno ac, jak i b c, a zatem, ze względu na właściwości NWD, dzieli również NWD (ac, b c), co będzie równe c NWD (a, b ) = c. Dlatego NWD (a c, b) dzieli zarówno b i c, dlatego NWD (c, b) również dzieli.

Można również powiedzieć, że skoro NWD (c, b) dzieli oba c i b, to podzieli zarówno c, jak i a · c. Stąd NWD (c, b) dzieli zarówno ac, jak i b, dlatego NWD (a c, b) również dzieli.

Zatem gcd (a c, b) i gcd (c, b) współdzielą się wzajemnie, co oznacza, że są sobie równe.

Definicja 6

Jeśli liczby z ciągu 1, 2,…, k będzie względnie pierwsza w stosunku do numerów ciągu b 1, b 2, ..., b m(dla naturalnych wartości k i m), to ich produkty a 1 · a 2 ·… · a k oraz b 1 b 2 ... b m są również względnie pierwsze, w szczególności a 1 = a 2 =… = a k = a oraz b 1 = b 2 =… = b m = b, następnie K oraz bm- wzajemnie proste.

Dowód 3

Zgodnie z poprzednią własnością możemy zapisać równości następującego typu: GCD (a 1 · a 2 ·… · a k, b m) = GCD (a 2 ·… · a k, b m) =… = GCD (a k, b m) = 1. Możliwość ostatniego przejścia wynika z faktu, że ak i bm są wzajemnie proste pod względem warunku. Stąd GCD (a 1 · a 2 ·… · a k, b m) = 1.

Oznaczamy a 1 a 2 ... ak = A i otrzymujemy, że NWD (b 1 b 2 ... bm, a 1 a 2 ... ak) = NWD (b 1 b 2 ... bm , A) = NWD (b 2 ... b bm, A) =… = NWD (bm, A) = 1. Będzie to prawdą ze względu na ostatnią równość w łańcuchu skonstruowanym powyżej. W ten sposób otrzymaliśmy równość NWD (b 1 b 2… b m, a 1 a 2… a k) = 1, którą można wykorzystać do udowodnienia wzajemnej prostoty produktów a 1 · a 2 ·… · a k oraz b 1 b 2 ... b m

To są wszystkie właściwości liczb względnie pierwszych, o których chcielibyśmy opowiedzieć.

Pojęcie par pierwszych liczb pierwszych

Wiedząc, czym są liczby względnie pierwsze, możemy sformułować definicję liczb pierwszych parami.

Definicja 7

Liczby pierwsze parami Jest ciągiem liczb całkowitych a 1, a 2,…, a k, gdzie każda liczba będzie pierwsza względem innych.

Przykładowa sekwencja par pierwszych to 14, 9, 17 i - 25. Tutaj wszystkie pary (14 i 9, 14 i 17, 14 i - 25, 9 i 17, 9 i - 25, 17 i - 25) są względnie pierwsze. Zauważ, że warunek wzajemnej prostoty jest obowiązkowy dla par pierwszych, ale liczby względnie pierwsze nie będą we wszystkich przypadkach liczbami pierwszymi parami. Na przykład w sekwencji 8, 16, 5 i 15 liczby nie są, ponieważ 8 i 16 nie będą względnie pierwsze.

Powinieneś także zastanowić się nad koncepcją kolekcji określonej liczby liczb pierwszych. Zawsze będą proste zarówno względem siebie, jak i w parach. Przykładem może być sekwencja 71, 443, 857, 991. W przypadku liczb pierwszych koncepcje prostoty wzajemnej i parami będą zbieżne.

Jeśli zauważysz błąd w tekście, zaznacz go i naciśnij Ctrl + Enter

Słowa kluczowe: teoria liczb, wykłady, plus liczby pierwsze.

Definicja. Liczby całkowite a i b są nazywane względnie pierwszymi, jeśli (a, b) = 1.

Dwie liczby a i b są względnie pierwsze wtedy i tylko wtedy, gdy istnieją liczby całkowite u i v takie, że au + bv = 1.

Niech X = (x n | n = 1, 2, ...) będzie dowolnym ściśle rosnącym ciągiem liczb naturalnych (lub, jeśli chcesz, X jest dowolnym podzbiorem liczb naturalnych, uporządkowanym w sposób naturalny). Niech ξ (N; X) oznacza liczbę członków ciągu X nieprzekraczającą N.

Definicja. Liczbę nazywamy gęstością (górną asymptotyczną) ciągu X = (x n | n = 1, 2, ...) w zbiorze N.

Przykład 1. Niech x n = 2n, gdzie n rozciąga się na N, będzie ciągiem wszystkich liczb parzystych. To oczywiste, że

Nawiasem mówiąc, dobrze pasuje to do naszej intuicji, że parzyste liczby to połowa.

Przykład 2. Niech x n = 2 n, gdzie n obejmuje N, - postęp geometryczny... Intuicyjnie widać, że takich liczb w naturalnym rzędzie jest niewiele, ponieważ im „dalej w las” wzdłuż naturalnego rzędu, tym rzadziej spotyka się potęgę dwójki. Pojęcie gęstości potwierdza to odczucie: ξ (2 k; (x n)) = k i łatwo to sprawdzić

Gęstość to prawdopodobieństwo losowego wyciągnięcia liczby z ciągu naturalnego, który należy do danego ciągu.

Podobnie jak w przypadku definicji gęstości ciągu, można określić gęstość zbioru par liczb naturalnych. Niech będzie dowolny zbiór X uporządkowanych par liczb naturalnych. Niech ξ (N; X) oznacza liczbę par ze zbioru X, których każdy składnik nie przekracza N. Dobrze jest wyobrazić sobie pary liczb ze zbioru X jako współrzędne punktów na płaszczyźnie współrzędnych, wtedy ξ (N; X) to po prostu liczba punktów zbioru X wpadających do kwadratu ((x, y) | 0< x ≤ N ; 0 < y ≤ N }.

Definicja. Numer

nazywamy gęstością (górną asymptotyczną) zbioru par X w zbiorze N 2.

Przykład 3. Niech X będzie zbiorem wszystkich par liczb naturalnych, dla których pierwsza składowa jest ściśle większa od drugiej. Zbiór X odpowiada punktom pierwszej ćwiartki płaszczyzny współrzędnych leżących pod dwusieczną y = x. Gęstość takiego zestawu łatwo policzyć:

Niech X będzie zbiorem wszystkich uporządkowanych par (u, v) liczb naturalnych takim, że (u, v) = 1, czyli zbiór wszystkich par liczb względnie pierwszych.

Twierdzenie (Cesaro). Prawdopodobieństwo wyboru pary liczb względnie pierwszych z N jest równe 6/π 2, a dokładniej Dowód. Załóżmy od razu, że istnieje prawdopodobieństwo p, że losowo wybrane liczby naturalne a i b są względnie pierwsze. Niech d N. Przez P (S) jak zwykle oznaczamy prawdopodobieństwo zdarzenia S. Argumentujemy: P

Definicja1. Liczby całkowite a 1, a 2, ..., a k są nazywane względnie pierwsze, jeśli (a 1, a 2, ..., a k) =1

Definicja 2. Liczby całkowite a 1, a 2, ..., ak są nazywane parami względnie pierwszymi, jeśli i, s (i, s = 1, 2, .., k, is, (a i, a s) = 1) ...

Jeśli liczby spełniają definicję 2, wtedy również spełniają definicję 1. Zdanie odwrotne generalnie nie jest prawdziwe, na przykład: (15, 21, 19) = 1, ale (15, 21) = 3

Twierdzenie (kryterium wzajemnej prostoty)

(a, b) = 1<=> x, y Z: ax + by = 1

Dowód:

Udowodnijmy konieczność. Niech (a, b) = 1. Powyżej pokazaliśmy, że jeśli d = (a, b), to  х, y Z: d = ax + by.

Bo w tym przypadku d = 1, wtedy będzie  х, y Z (określone z algorytmu Euklidesa): 1 = ax + by.

Adekwatność. Niech (*) ax + by = 1, udowodnimy, że (a, b) = 1. Załóżmy, że (a, b) = d, a następnie po lewej stronie równości (*)

(a / D ) & ( b / d ) => (ax + by) / d => (1 / d) => (d = l) => (a, b) = 1.

§4. Nok liczb całkowitych i jego własności.

Definicja 1. Wspólna wielokrotność skończonego zbioru niezerowych liczb całkowitych a 1, a 2, ..., a k jest liczbą całkowitą m podzielną przez wszystkie liczby a i (i = l, 2, ..., k)

Definicja 2. Liczba całkowita (m) nazywana jest najmniejszą wspólną wielokrotnością liczb a 1, a 2, ..., a k, różną od zera, jeśli:

1 m - to ich wspólna wielokrotność;

2 (m) dzieli każdą inną wspólną wielokrotność tych liczb.

Oznaczenie: m = LCM (a 1, a 2, ..., a k) lub m = [a 1, a 2, ..., a k]

Przykład. Podane liczby: 2, 3, 4, 6, 12.

Liczby 12, 24, 48, 96 są wspólnymi wielokrotnościami 2, 3, 4, 6, 12. Najmniejsza wspólna wielokrotność to 12. tj.

LCM jest jednoznacznie określany zgodnie z kolejnością czynników. Rzeczywiście, jeśli założymy, że m 1 = [a, b] & m 2 =  (m 1 / m 2) & (m 2 / m 1) => [(m 1 = m 2) v (m 1 = - m 2)]. Istnieje zależność między najmniejszą wspólną wielokrotnością a największym wspólnym dzielnikiem dwóch liczb całkowitych, co wyraża się wzorem: [a, b] = ab / (a, b) (wypisz to sam)

Ta zależność pozwala nam stwierdzić, że dla każdej pary niezerowych liczb całkowitych istnieje ich najmniejsza wspólna wielokrotność. Rzeczywiście, (a, b) - zawsze można jednoznacznie wydedukować z algorytmu euklidesowego iz definicji (a, b)  0, to ułamek ab / (a, b)  0 i będzie jednoznacznie określony.

Najprostszy LCM dwóch liczb całkowitych jest obliczany w przypadku, gdy (a, b) = 1, to [a, b] = ab / 1 = a b

Na przykład = 215 / 1 = 105, ponieważ (21, 5) = 1.

§5. Liczby pierwsze i ich własności.

Definicja 1. Liczbę naturalną (p) nazywamy liczbą pierwszą, jeśli p> 1 i nie ma pozycji. dzielniki inne niż 1 i p.

Definicja 2. Liczba naturalna a> 1, która ma inne czynniki dodatnie oprócz 1 i samej siebie, nazywana jest złożoną.

Z tych definicji wynika, że zbiór liczb naturalnych można podzielić na trzy klasy:

a) liczby złożone;

b) liczby pierwsze;

c) jednostka.

Jeśli a jest złożony, to a = nq, gdzie 1

Cel 1. Udowodnij, że jeśli aZ i p jest liczbą pierwszą, to (a, p) = 1 v (a / p)

Dowód.

Niech d = (a, p) => (a / d) i (p / d), ponieważ p jest liczbą pierwszą, to ma dwa dzielniki 1 i p. Jeśli (a, p) = 1, to a i p są względnie pierwsze, jeśli (a, p) = p, to (a / p).

Cel 2. Jeżeli iloczyn kilku czynników jest podzielny przez p, to przynajmniej jeden z czynników jest podzielny przez p.

Rozwiązanie.

Niech iloczyn (a 1, 2, ..., a k) / p, jeśli wszystkie a i nie są podzielne przez p, to iloczyn będzie wzajemnie prosty z p, zatem pewien czynnik jest podzielny przez p.

Cel 3. Udowodnij, że najmniejszy dzielnik liczby całkowitej a>1 jest liczbą pierwszą.

Dowód.

Niech aZ i a będą liczbą złożoną (jeśli a = p, to zdanie jest udowodnione), wtedy a = a 1 q.

Niech q będzie najmniejszym dzielnikiem, pokażemy, że będzie to liczba pierwsza. Jeśli założymy, że q jest liczbą złożoną, to q = q 1 k i a = a 1 q 1 k, ponieważ q 1

Zadanie 4. Udowodnij, że najmniejszy dzielnik pierwszy (p) liczby całkowitej dodatniej (n) nie przekracza n.

Dowód.

Niech n = pn 1, ponadto р< n 1 и р - простое. Тогда n  р 2 =>r<n .

Z tego stwierdzenia wynika, że jeśli liczba naturalna (n) nie jest podzielna przez żadną liczbę pierwszą p n, to n jest liczbą pierwszą, w przeciwnym razie będzie złożona.

Przykład 1... Dowiedz się, czy 137 jest liczbą pierwszą? jedenaście<137 <12.

Wypisujemy dzielniki pierwsze nieprzekraczające 137: 2, 3, 5, 7, 11. Sprawdź, czy 137 nie jest podzielne przez 2, 3, 5, 7, 11. Zatem 137 jest liczbą pierwszą.

Twierdzenie Euklidesa... Zbiór liczb pierwszych jest nieskończony.

Dowód.

Załóżmy odwrotnie, niech p 1, p 2, ..., p k to wszystkie liczby pierwsze, gdzie p 1 = 2 i p k jest największą liczbą pierwszą.

Zrób liczbę naturalną  = p 1 p 2  ... p do +1, ponieważ  p i, to musi być złożona, to jej najmniejszy dzielnik będzie prosty (patrz Problem 3). Jednak  nie jest podzielna ani przez p 1, ani przez p 2,…, ani przez p k, ponieważ 1 nie jest podzielna przez żadne p I.

Dlatego nasze założenie o skończoności zbioru liczb pierwszych było błędne.

Istnieje jednak twierdzenie, które mówi, że liczby pierwsze stanowią tylko niewielką część liczb naturalnych.

Twierdzenie przedziałowe. W szeregu naturalnym występują dowolnie długie przedziały, które nie zawierają ani jednej liczby pierwszej.

Dowód.

Weź dowolną liczbę naturalną (n) i ułóż ciąg liczb naturalnych (n + 1)! + 2, n + 1)! + 3,…, (n + 1)! + (N + 1).

W tej sekwencji każda kolejna liczba jest o 1 większa od poprzedniej, wszystkie te liczby są złożone, ponieważ każdy ma więcej niż dwa dzielniki (na przykład pierwsza liczba jest podzielna przez 1, 2 i samą siebie). Jako n → ∞ otrzymujemy dowolnie długi przedział składający się tylko z liczb złożonych.

Twierdzenie Euklidesa i twierdzenie o przedziałach świadczą o złożonej naturze rozkładu liczb pierwszych w szeregach naturalnych.

Podstawowe twierdzenie arytmetyki

Dowolna liczba naturalna n> 1 może być jednoznacznie reprezentowana jako iloczyn liczb pierwszych, aż do rzędu czynników.

Dowód.

Wykażmy możliwość reprezentowania:

Niech nN i n> 1, jeśli n jest liczbą pierwszą, to n = p i twierdzenie jest udowodnione. Jeśli n jest złożone, to jego najmniejszym dzielnikiem będzie liczba pierwsza, a n = p 1 n 1, gdzie n 1

Następnie rozumujemy w podobny sposób. Jeśli n 1 jest liczbą pierwszą, to twierdzenie jest udowodnione, jeśli n 1 jest liczbą złożoną, to n 1 = p 2 n 2, gdzie n 2< n 1 и тогда n = p 1 p 2 n 2 . На каком-то шаге получим n = p 1 p 2 …p n , где все p i - простые числа.

Udowodnijmy wyjątkowość rozkładu:

Załóżmy, że istnieją dwie różne reprezentacje liczby (n): n = p 1 p 2… p k, n = q 1 q 2… q n i n> k.

Wtedy otrzymujemy, że p 1 p 2… p k = q 1 q 2… q n (1). Lewa strona równości (1) jest podzielna przez p 1, a następnie, przez własność liczb pierwszych (patrz Problem 2), co najmniej jeden z czynników po prawej stronie musi być podzielny przez p 1.

Niech (q 1 / p 1) => (q 1 = p 1). Dzieląc obie strony równości (1) przez p 1, otrzymujemy równość p 2 p 3… p k = q 2 q 3… q n. Powtarzając poprzednie rozumowanie (k-1) więcej razy, otrzymujemy równość 1 = q k +1 q k +2 ... q n, ponieważ wszystkie q i> 1, to ta równość jest niemożliwa. Dlatego w obu rozwinięciach liczba czynników jest taka sama (k = n) i same czynniki są takie same.

Komentarz. W rozkładzie liczby (n) na czynniki pierwsze niektóre z nich mogą się powtórzyć. Niech  1,  2,…,  k oznaczają krotność ich występowania w (n), otrzymujemy tzw. rozkład kanoniczny liczby (n):

Przykład 2.

Rozkład kanoniczny 588000 = 2 5 35 3 7 2

Wniosek 1. Jeśli
wtedy wszystkie dzielniki liczby (n) to:
gdzie 0 i  i (i = 1, 2,…, k).

Przykład 3. Wszystkie dzielniki liczby 720 = 2 4 3 2 5 otrzymujemy, jeśli w wyrażeniu
zamiast 1,  2,  3, niezależnie od siebie, podstawimy wartości:  1 = 0, 1, 2, 3, 4,  2 = 0, 1, 2,  3 = 0, 1.

Wymagane dzielniki będą równe: 1; 2; 4; osiem; szesnaście; 3; 6; 12; 24; 48; 9; osiemnaście; 36; 72; 144; 5; 10; dwadzieścia; 40; 80; 15; trzydzieści; 60; 120; 240; 45; 90; 180; 360; 720.

Następstwo 2. Jeśli
oraz
wtedy (a, b) = p 1  1 p 2  2… p k  k, gdzie i = min ( I,  i)