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

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

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

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

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

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

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

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

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

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

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

у = ра + k

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

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

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

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

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

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