Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Как подобрать взаимно простые числа

На главную Математический раздел Криптография и т.д. Новости

1. Что такое взаимно простые числа и зачем они нам?

Взаимно простые числа? Что это за ерунда такая?

Взаимно простые числа - это натуральные числа, у которых только один общий делитель - 1.

Допустим, 5 и 12 - такие. А вот 10 и 12 нет - эти сволочи оба делятся на 2. 49 и 63 - тоже не взаимно простые числа: оба умудряются делиться на 7.
Если числа x и y - взаимно простые числа, это обозначают как (x, y) = 1.

Также можно определить взаимно простые числа как числа, наибольший общий делитель которых равен единице. Звучит солидно)

Зачем они нам?
1.Во-первых, взаимно простые числа используются в некоторых системах шифрования. В том числе среди тех, которые мы рассматривали. Взгляните, допустим, на систему подстановок Цезаря или шифр Хилла.
2.Если кому-то первого мало, есть ещё момент. Взаимно простые числа могут использоваться в генераторах псевдослучайных чисел.
В общем, достаточно причин.

2. Способы получения взаимно простых чисел

Использование простых чисел

Простые числа - которые имеют только 2 делителя - 1 и само себя.

Допустим, 5, 7, 11 - простые числа, 9 - нет, так как 9 делится на 1, самого себя и на 3.

Если x - простое число, а y - число из множества {1, 2, 3, ..., x - 1}, то гарантированно (x, y) = 1, то есть x и y - взаимно простые числа.
Едва ли это надо особо пояснять.
О том, как получать большие простые числа, немного есть в описании случайных генераторов.
Есть ещё такая издревле известная штука, как решето Эратосфена, но для больших чисел (миллиарды, например) это медленный метод. Зато надёжнее: супер-формулы получения простых чисел иногда ошибаются.

Также несложно будет подобрать y > x, чтобы x и y были взаимно простыми числами. Нужно всего лишь выбрать y так, чтобы это число не делилось на x. Для этого простое число x умножаем на любое натуральное число и прибавляем (вычитаем) величину k < x, то есть y = qx + k, где q и k - натуральные, k < x.

Допустим, x = 71 - простое число. Берём q=10, k = 3, получаем y = 713.

Также отметим, что если x и y - простые числа, то они также образуют пару взаимно простых чисел. Так что если знаете два простых числа - смело их берите. Пример: x = 29 и y = 83.

Подбор взаимно простых чисел с помощью степеней

Если x - степень числа m, то для обеспечения (x, y) = 1 можно выбрать любое y, не делящееся на m.

Самый простой вариант: x - степень двойки, y - нечётное число.
Другой вариант: x - степень пятёрки, а младшая цифра числа y - не 0 и не 5. Допустим, 390625 (5 в степени 6) и 24242424 - взаимно простые числа.
В силу особенностей компов из названного популярен ход со степенью двойки: степень двойки и нечётное число суть взаимно простые числа. При получении больших x и y это ещё проще, чем опираться на простые числа. Не нужно даже никаких специальных формул. Тем более что очень легко определить, делится какое-то число на 2 или нет. m = 5 - также простой вариант. Также хорошие признаки делимости (или неделимости) есть для m = 3, 9, 10.
Можно, скажем, смело заявить, что (65536, 12121212121) = 1. Также 729 (3 в степени 6) и 112 (не делится на 3) - взаимно простые числа.

Близко расположенные числа

Два предыдущих способа хороши, но могут быть проблемными, если одно из чисел задано наперёд. Но может же такое быть, что нужно обязательно использовать число x, оно имеет тысячу делителей и уж точно x - не степень какого-то числа. Тогда выкрутимся чуточку по-другому.

Если |x - y| < m, то x и y не могут иметь общих делителей, равных m или больших, чем m.
Допустим, это не так. Если x и y делятся на p, то x = kp, y = np, где k, n - натуральные числа. Значит, |x - y| = qp, где q - натуральное число. Если p > (m - 1), то qp > (m - 1), так как q суть 1 или большее число. Итак, |x - y| < m и |x - y| > (m - 1), что при натуральных m не бывает. Вот вам и третий способ получения взаимно простых чисел.

При малых m легко подобрать x, y со свойством (x, y) = 1.
Так, если x = y + 1 либо y = x + 1, то гарантированно x и y - взаимно простые числа.
Если x = y + 2 либо y = x + 2, то x и y не могут иметь в качестве общего делителя 3, 4, 5, ... Жаль, но могут двойку. Но если x и y - нечётные, то и это исключено.

Примеры взаимно простых чисел по этому методу: (1000000, 999999) = 1; (1000003, 1000001) = 1.

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X