Взаимно прости числа

от Уикипедия, свободната енциклопедия

Взаимно прости числа в математиката се наричат две или повече цели числа, чиито единствени общи делители са 1 и −1 или, изразено по друг начин, чийто най-голям общ делител е единица.

Например 6 и 35 са взаимнопрости, но 6 и 27 не са, понеже и двете се делят на 3. Числото 1 е взаимно просто с всяко цяло число, а 0 е взаимно просто само с 1 и −1.

Един бърз начин за определяне дали две числа са взаимно прости е най-древният известен алгоритъм, алгоритъмът на Евклид, с който се намира най-големия общ делител на две числа. В частност алгоритъмът разпознава дали две числа са взаимно прости.

Функцията на Ойлер от положително цяло число n дава броя цели числа между 1 и n−1, които са взаимно прости с n.

[редактиране] Свойства

Има няколко условия, които са еквивалентни на това числата a и b да са взаимно прости:

Съществуват цели числа x и y, такива, че ax + by = 1 (виж Теорема на Безу).
Цялото число b има реципрочен модул a: съществува цяло число y, такова, че by ≡ 1 (mod a). С други думи, b е неутрален елемент в пръстена Z/aZ от цели числа с модул a.

Вследствие на това, ако a и b са взаимно прости и br ≡ bs (mod a), то r ≡ s (mod a) (тъй като можем да „делим на b“, когато работим с модул a). Освен това, ако a и b₁ са взаимно прости и a и b₂ са взаимно прости, то a и b₁b₂ са също взаимно прости (тъй като прозиведението на неутрални елементи е неутрален елемент).

Ако a и b са взаимно прости и a е делител на произведението bc, то a е делител на c. Това може да се разглежда като обобщение на лемата на Евклид, която твърди, че ако p е просто и p е делител на произведението bc, то или p е делител на b, или p е делител на c.

Две цели числа a и b са взаимно прости тогава и само тогава, когато точката с координати (a, b) в една декартова координатна система „се вижда“ от началото (0,0), в смисъл, че няма друга точка с цели координати на отсечката между началото и (a, b).

Вероятността две произволно взети цели числа да са взаимно прости е 6/π², което е около 60%.

Две естествени числа a и b са взаимно прости тогава и само тогава, когато числата 2^a − 1 и 2^b − 1 са взаимно прости.

Ако n≥1 е цяло число, числата, взаимно прости с n, взети по модул n, образуват група относно умножението. Тя се записва като (Z/nZ)^× or Z_n^*.

[редактиране] Обобщения

Два идеала A и B в комутативния пръстен R са взаимно прости, ако A + B = R. Това е обобщение на теоремата на Безу: с тази дефииниция два главни идеала (a) и (b) в пръстена от цели числа Z са взаимно прости тогава и само тогава, когато a и b са взаимно прости.

Ако идеалите A и B в R са взаимно прости, то AB = A∩B. Освен това, ако C е трети идеал, такъв, че A съдържа BC, то A съдържа C. Китайската теорема за остатъците е много важно твърдение за взаимно простите идеали.

Понятието „взаимно прости“ може да се разшири за произволно крайно множество от цели числа S = {a₁, a₂, .... a_n}, в смисъл, че най-голям общ делител на множеството е 1. Ако всяка двойка цели числа в множеството са взаимно прости, множеството се нарича „взаимно просто по двойки“.

Всако взаимно просто по двойки множество е взаимно просто. Обратното, обаче, не е вярно: {6, 10, 15} е взаимно просто, но не е взаимно просто по двойки. (Всъщност всяка двойка цели числа в множеството има нетривиален общ делител.)