Вычисление НОД и НОК на основе канонического разложения числа.

Любое составное число m можно однозначно представить в виде произведения простых сомножителей p, m = p₁*p₂*.....*p_k, где m – составное число, p – простое. Составное число может раскладываться на простые, при этом могут быть две формы:

1)когда все сомножители разные 2) когда есть кратные сомножители

Пример: 720 = 2⁴*3²*5 - такая форма носит название – каноническое разложение на простые сомножители. M=p₁^α1* p₂^α2* p_k^αk. Это позволяет при большем числе кратных

сомножителей достаточно компактно записать разложение.

 

Найдем НОД по след формуле: НОД=П_ip_i^min(ai*bi), где П_i-произведение.

Min(a_i*b_i) - из каждой пары сомножителей выбирается сомножитель с минимальным показателем.

Пример 90= 2*3²*5, 720= 2⁴*3²*5.

Берем минимальные показатели: НОД=П_ip_i^min(ai*bi)=2*3²*5=90 - т.е. число 90 является НОД(d) чисел 90 и 720. Аналогично НОК :

НОK= П_ip_i^max(ai*bi)= 2⁴*3²*5=720 - т.е. число 720 является НОК(k) чисел 90 и 720.

 

Тестирование чисел Мерена

Числами Мерсенна называются числа вида М(p) = 2 ^p - 1, pÎN.

Задача для чисел Мерсенна - поиск в ряду этих чисел простых.

Мерсенн рассматривал значения функции 2^p - 1 только при простых p .

Действительно, если p - составное, то такое же и М(p). Предположим, что

p = r * s , 1 < r и s < p , тогда

М(p)=2^p-1=2^rs -1=(2^r -l)(2^r(s-1) +2^r(s-2) +...+2^r +1).

Следовательно, если r делит p, то и М(r) делит М(p).

В то же время, если p - простое, то М(p) не обязательно является простым.

Например, для простого числа p = 11 число Мерсенна М(p)=211−1=2047=23×89 получается составным.

При доказательстве простоты чисел Мерсена Ферма использовал метод разложения на множители. Более эффективен тест Люка-Лемера.

Тест Люка - Лемера

Тест создает последовательность натуральных чисел: S₀, S₁, S₂, ..., S_p-2, определяемую рекуррентной формулой S_k+1 = S_k² - 2, где S₀ = 4. Пусть р – простое число. Число Мерсена является простым тогда и только тогда, когда S_p-2 mod M(p) ≡ 0, т.е. остаток равен 0.

 

Поясним, каким образом задается ряд S_k. Члены последовательности можно записать в виде сумм степеней некоторых иррациональных чисел.  Пусть = 2 +√3 и  =2 +√3 . Докажем индукцией по n, что  ^{2^n} +  ^{2^n}=S_n.

Очевидно,   +  =S₀. Предположим, что  ^{2^(n-1)} +  ^{2^(n-1)}=S_n-1.

Возводя в квадрат обе части равенства, получаем  ^{2^n} +2( )^{2^(n-1)}+  ^{2^ n} =S² _{n -1}. Поскольку  =1,то следует соотношение  ^{2^n} +  ^{2^n}=S² _{n -1} -2, что, по определению, дает S_n.

 

Описание алгоритма.

1. Ввод p. Если p < 3, то выход (не удовлетворяет условиям алгоритма).

2.Вычисление M(p) = 2^p-1

3. Установить S = 4.

4. Для "i = 1…p-2 вычислить S = (S² mod M(p)) - 2

5. Если S mod (M(p)-1)º0, то M(p) является простым, иначе составным.

 

 

4. Функция Эйлера

Эйлер установил такую закономерность, что существует определенная формула, по которой можно вычислить число взаимно простых чисел. Эта формула определяется на основе разложения числа m=p₁^a1*…*p_k^ak. Функция Эйлера устанавливает число взаимно простых чисел с заданным числом m.

Формулы для вычисления:

1) j(m)=m(1-1/p₁)(1-1/p₂)(1-1/p_i)

2) j(m)=(p₁^a1-p₁^a1-1)(p₂^a2-p₂^a2-1)…(p_k^ak-p_k^ak-1)

где  p_i-числа, на которые мы делим, a_i-их степени

Классическое приложение этой функции такое: Заданно некоторое натуральное число a и заданно некоторое число m, пусть m-составное, натуральное, положительное. Если эти два числа взаимно просты, тогда для этой пары чисел справедлива следующая теорема (теорема Эйлера):

a^j(m)mod m = 1.

Берем число a, возводим в j(m) , берем модуль от a^j(m): т.е. остаток будет равен всегда единице.

Частный случай: m- простое(p), то: a^p-1modp  1

⇐ Предыдущая12345Следующая ⇒

Поделиться: