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

Підручники математики часом складні для сприйняття. Сухий і чіткий мова авторів не завжди доступний для розуміння. Та й теми там завжди взаємопов`язані, взаімовитекающіе. Для освоєння однієї теми доводиться піднімати ряд попередніх, а часом і перегортати весь підручник. Складно? Так. А давайте ризикнемо обійти ці складності і спробуємо знайти до теми не зовсім стандартний підхід. Зробимо такий собі екскурс в країну чисел. Визначення, однак, ми все-таки залишимо колишнім, так як правила математики скасувати не можна. Отже, взаємно прості числа - числа натуральні, із загальним дільником, що дорівнює одиниці. Це зрозуміло? Цілком.

Для більш наочного прикладу давайте візьмемо числа 6 і 13. І те, і інше - подільні на одиницю (взаємно прості). А ось числа 12 і 14 - такими не можуть бути, оскільки діляться не тільки на 1, але і на 2. Наступні числа - 21 і 47 теж не підходять до категорії "взаємно прості числа": Їх можна розділити не тільки на 1, але ще і на 7.

позначають взаємно прості числа так: (а, у) = 1.

Відео: Найбільший спільний дільник. Взаємно прості числа Рішення прикладів

Можна сказати навіть простіше: загальний дільник (найбільший) тут дорівнює одиниці.

Для чого нам такі знання? Причин достатньо.

Взаємно прості числа включені до деяких системи шифрування. Ті, хто працює з шифрами Хілла або з системою підстановок Цезаря, розуміють: без цих знань - нікуди. Якщо ви чули про генераторах псевдовипадкових чисел, то навряд чи зважитеся заперечувати: взаємно прості числа використовуються і там.

Тепер поговоримо про способи отримання таких чисел. Числа прості, як ви розумієте, можуть мати лише два подільника: вони подільні на самих себе і на одиницю. Скажімо, 11, 7, 5, 3 - числа прості, а от 9 - немає, адже це число вже ділимо і на 9, і на 3, і на 1.

І якщо а - число просте, а у - з безлічі {1, 2, ... а - 1}, то тоді гарантовано (а, у) = 1, або взаємно прості числа - а й у.

Це, скоріше, навіть не пояснення, а повторення або підведення підсумків щойно сказаного.

Отримання простих чисел можливо решетом Ератосфена, однак для значних чисел (мільярдів, наприклад) цей метод занадто довгий, але, на відміну від супер-формул, які часом і помиляються, більш надійний.

Можна працювати шляхом підбору у gt; а. Для цього у вибирається так, щоб число на а не ділилося. Для цього число просте множиться на число натуральне і додається (або, навпаки, віднімається) величина (припустимо, р), яка менше а:

у = ра + k

Якщо, наприклад, а = 71, р = 3, q = 10, то, відповідно, у тут буде дорівнює 713. Можливий і інший підбір, зі ступенями.

Відео: 6.06. Найбільший спільний дільник. Взаємно прості числа

Складові числа, на відміну від взаємно простих, діляться і на себе, і на 1, і на інші числа (теж без залишку).

Іншими словами, натуральні числа (крім одиниці) розбиті на складові і прості.

Прості числа - числа натуральні, не мають нетривіальних (відмінних від самого числа і одиниці) подільників. Особливо важлива їх роль у сьогоднішній, сучасної, швидко розвивається криптографії, завдяки якій теорія чисел, яку вважали раніше дисципліною гранично абстрактній, стала так затребувана: алгоритми захисту даних постійно удосконалюються.

Найбільше просте число знайдено доктором-офтальмологом Мартіном Новаком, які брали участь у проекті GIMPS (розподільні обчислення) разом з іншими ентузіастами, яких налічувалося близько 15 тис. На розрахунки пішло шість довгих років. Було задіяно два з половиною десятка комп`ютерів, що знаходяться в очній клініці Новака. Результатом титанічної праці і завзятості стало число 225964951-1, із записуванням в 7816230-десяткових знаках. До речі, рекорд найбільшого числа був поставлений за півроку до цього відкриття. І знаків там було на півмільйона менше.

У генія, який бажає назвати число, де тривалість десяткового запису "перестрибне" десятимільйонну позначку, є шанс отримати не тільки всесвітню славу, а й 100 000 доларів. До речі, за число, що подолали мільйонний рубіж знаків, Наян Хайратвал отримав меншу суму (50 000 доларів).