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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

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

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

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

Вследствие на това, ако a и b са взаимно прости и brbs (mod a), то rs'' (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)× or Zn*.

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

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

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

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

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

Вижте също[редактиране | edit source]