Взаимно прости числа
 | За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. |  |
Взаимно прости числа в математиката се наричат две или повече цели числа, чиито единствени общи делители са 1 и −1 или, изразено по друг начин, чийто най-голям общ делител е единица. Следствия от това определение:
- Всеки две последователни естествени числа са взаимно прости.
- Всеки две прости числа са взаимно прости.
- Числото 1 е взаимно просто с всяко цяло число.
- Нула е взаимно просто само с 1 и −1.
- Две четни числа не може да са взаимно прости, защото имат общ делител 2.
Например: 6 и 35 са взаимно прости, но 6 и 27 не са, понеже и двете се делят на 3.
Един бърз начин за определяне дали две числа са взаимно прости е най-древният известен алгоритъм - алгоритъмът на Евклид, с който се намира най-големият общ делител на две числа. В частност алгоритъмът разпознава дали две числа са взаимно прости.
Функцията на Ойлер от положително цяло число n дава броя на целите числа между 1 и n−1, които са взаимно прости с n.
Свойства
[редактиране | редактиране на кода]Има няколко условия, които са еквивалентни на това числата a и b да са взаимно прости:
- Съществуват цели числа x и y, такива, че ax + by = 1 (виж Теорема на Безу).
- Цялото число b има реципрочен модул a: съществува цяло число y, такова, че by ≡ 1 (mod a). С други думи, b е неутрален елемент в пръстена Z/aZ от цели числа с модул a.
sama и b са взаимно прости и br ≡ bs (mod a), то r ≡ s'' (mod ''a) (тъй като можем да „делим на b“, когато работим с модул a). Освен това, ако a и b1 са взаимно прости и a и b2 са взаимно прости, то a и b1b2 са също взаимно прости (тъй като произведението на неутрални елементи е неутрален елемент).
Ако a и b са взаимно прости и a е делител на произведението bc, то a е делител на c. Това може да се разглежда като обобщение на лемата на Евклид, която твърди, че ако p е просто и p е делител на произведението bc, то или p е делител на b, или p е делител на c.
Две цели числа a и b са взаимно прости тогава и само тогава, когато точката с координати (a, b) в една декартова координатна система „се вижда“ от началото (0,0), в смисъл че няма друга точка с цели координати на отсечката между началото и (a, b).
Вероятността две произволно взети цели числа да са взаимно прости е 6/π2, което е около 60%.
Две естествени числа a и b са взаимно прости тогава и само тогава, когато числата 2a − 1 и 2b − 1 са взаимно прости.
Ако n≥1 е цяло число, числата, взаимно прости с n, взети по модул n, образуват група относно умножението. Тя се записва като (Z/nZ)× или Zn*.
Обобщения
[редактиране | редактиране на кода]Два идеала A и B в комутативния пръстен R са взаимно прости, ако A + B = R. Това е обобщение на теоремата на Безу: с тази дефиниция два главни идеала (a) и (b) в пръстена от цели числа Z са взаимно прости тогава и само тогава, когато a и b са взаимно прости.
Ако идеалите A и B в R са взаимно прости, то AB = A∩B. Освен това, ако C е трети идеал, такъв че A съдържа BC, то A съдържа C. Китайската теорема за остатъците е много важно твърдение за взаимно простите идеали.
Понятието „взаимно прости“ може да се разшири за произволно крайно множество от цели числа S = {a1, a2, .... an}, в смисъл че най-голям общ делител на множеството е 1. Ако всяка двойка цели числа в множеството са взаимно прости, множеството се нарича „взаимно просто по двойки“.
Всяко взаимно просто по двойки множество е взаимно просто. Обратното обаче не е вярно: {6, 10, 15} е взаимно просто, но не е взаимно просто по двойки. (Всъщност всяка двойка цели числа в множеството има нетривиален общ делител.)