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

Алгоритм Евклида для нахождения НОД

Свой алгоритм Евклид (древнегреческий математик, живший примерно в 300 г. до
н.э.) придумал для решения задачи о соизмеримости двух отрезков. Общей мерой
(единицей измерения) отрезков с длинами $L_1$ и $L_2$ является отрезок
с наибольшей возможной длиной $L$, который можно уложить без остатка как в
первом отрезке, так и во втором. Например, для отрезков 10 и 15 такой общей мерой будет отрезок с длиной 5 (им
можно
пользоваться как единицей измерения для обоих отрезков). При этом 5 будет наибольшим общим
делителем
10 и 15.

В общем случае, алгоритм Евклида — это метод нахождения
наибольшего общего делителя (НОД) нескольких чисел.

Целое число $a$ делится на целое число $b$ ($b \ne 0$), если
существует целое число $k$, такое что $a=kb$. В таком случае $b$ называют делителем
числа $a$; число $a$ называют кратным числа $b$.

Если $a$ и $b$ делятся на $c$,
то их сумма $a+b$ и их разность $a-b$ делятся на $c$.

Если $a$ делится на $c$, а $b$ делится на $d$, то их
произведение $a*b$ делится на $c*d$.

$a$ и $b$ – положительные целые числа, $c$ — является общим делителем
чисел $a$ и $b$, если $a$ делится на $c$ и $b$ делится на $c$.

Среди общих делителей чисел $a$ и $b$ (не равных одновременно нулю) есть наибольший общий
делитель
(по-английски Greatest common divisor — GCD), обозначаемый НОД($a,b$) или $GCD(a,b)$.

Если $a$ делится на $b$, то $GCD(a,b) = b$. Например: $GCD(50,10)=10$.

$GCD(a,a)=a$. Например: $GCD(32,32)=32$.

Если $a \gt b$, то $GCD(a,b)=GCD(a-b,b)$.

Если $GCD(a,b)=1$, то числа $a$ и $b$ — взаимно простые.

Алгоритм Евклида с вычитаниями

Последовательно вычитая из большего числа меньшее до тех пор, пока они не станут равными, придем к НОД этих
чисел.

Пример: Найти НОД двух чисел 264 и 192.

Решение:
НОД(264, 192) = НОД(72, 192) = НОД(72, 120) = НОД(72, 48) =
НОД(24, 48) = НОД(24, 24) = 24

Задача. Найти НОД двух натуральных чисел $a$ и $b$.

Используем для решения задачи алгоритм Евклида с вычитаниями.

Реализация на Pascal:

function GCD( a,b:integer ):integer; { определение НОД двух чисел }
begin
  while a  b do
    if a > b then a:=a-b else b:=b-a;
  GCD := b;
end;

begin { Пример использования }
  writeln(GCD(10,15)); { Выведет 5 }
end.

Реализация на С/C++:

#include <stdio.h>

int GCD( int a, int b ){ // определение НОД двух чисел
  while(a != b)
    if (a > b) a-=b; else b-=a;
  return b;
}

int main(){ // Пример использования
  printf("%d",GCD(10,15)); // Выведет 5
  return 0;
}

Алгоритм Евклида с делением

Если применить алгоритм Евклида с вычитаниями к паре чисел $(1,10^{20})$, то будет выполнено около $10^{20}$
вычитаний, это слишком долго!

Можно за один раз вычитать из $a$ $b$ столько раз, сколько можно. Алгоритм Евклида с делением основан на том, что
если $a=bq+r$, где $r$ — остаток от деления $a$ на $b$ ($0 \le r

Последовательно
применяя это утверждение можно понять, что НОД двух чисел – это последний не
равный нулю остаток от деления большего числа на меньшее.

Пример: найти НОД двух чисел 6069 и 663.

Решение:

6069 = 663*9+102 НОД(6069, 663) = НОД
(663, 102)
663 = 102*6+51 НОД(663, 102) = НОД
(102, 51)
102 = 51*2+0 НОД(102, 51) = 51
(согласно утверждению 3)

Следовательно, 51 = НОД(102, 51) = НОД(663, 102) = НОД(6069, 663)

Демонстрационная Flash-программа показывает вычисление НОД любых 2 чисел:

Для содержимого этой страницы требуется более новая версия Adobe Flash Player.

Рассмотрим алгоритм и процедуру-функцию к решению задачи 1.1, используя для нахождения НОД двух
чисел алгоритм Евклида с делением.

Алгоритм:

Функция Вычисление_НОД(целое a, целое b)
  Пока (b <> 0)
    r := a по модулю b  (остаток от деления a на b), r - временная переменная (буфер)
    a := b
    b := r
  конец цикла
  Вывод результата - a
Конец функции

Реализация на Pascal:

function GCD( a,b:int64 ):int64; { Функция для вычисления НОД при помощи деления }begin  if b = 0 then { Если b = 0 }    GCD := a {  следовательно a=НОД }  else { Пока b <> 0 }    GCD := GCD(b,a mod b); { Вычисляем остаток от деления a на b, а заменяем на b, b заменяем на r }
end;

begin
  writeln(GCD(264, 192)); { Выведет: 24 }
end.

def GCD(a,b): # Функция для вычисления НОД при помощи деления
  return a if b == 0 else GCD(b,a%b) # Вычисляем остаток от деления a на b, а заменяем на b, b заменяем на r=a mod b
  # НОД = a если b = 0 иначе НОД=НОД(b,r), r - остаток от деления a на b

print GCD(264, 192) # Выведет: 24 

Вычислить НОД трех натуральных чисел $a$, $b$ и $c$ можно так:

$GCD(a,b,c)=GCD(GCD(a,b),c)$

В общем случае, справедлива следующая рекуррентная формула:

$GCD(a_1,a_2,…,a_n) = GCD(GCD(a_1,a_2,…,a_{n-1}), a_n)$.

Ниже приведена функция нахождения НОД для массива натуральных чисел $a(1..n)$ с использованием цикла.

function GCD( ... )...
    ....

function GCDM( a : array of int64 ):int64;
var d : int64; i : integer;
begin
  d := a;
  for i:= 1 to length(a)-1 do
    d := GCD(d, a);
  GCDM := d;
end;

begin { Пример вызова }
  writeln(GCDM());
end.  

Основные свойства взаимно простых чисел

Такие числа имеют некоторые практически важные свойства. Перечислим их по порядку и докажем.

Определение 3

Если разделить целые числа a и b на число, соответствующее их наибольшему общему делителю, мы получим взаимно простые числа. Иначе говоря, a: НОД (a, b) и b: НОД (a, b) будут взаимно простыми.

Это свойство мы уже доказывали. Доказательство можно посмотреть в статье о свойствах наибольшего общего делителя. Благодаря ему мы можем определять пары взаимно простых чисел: достаточно лишь взять два любых целых числа и выполнить деление на НОД. В итоге мы должны получить взаимно простые числа.

Определение 4

Необходимым и достаточным условием взаимной простоты чисел a и b является существование таких целых чисел u0 и v0, при которых равенство a·u0+b·v0=1 будет верным.

Доказательство 1

Начнем с доказательства необходимости этого условия. Допустим, у нас есть два взаимно простых числа, обозначенных a и b. Тогда по определению этого понятия их наибольший общий делитель будет равен единице. Из свойств НОД нам известно, что для целых a и b существует соотношение Безу a·u0+b·v0=НОД (a, b). Из него получим, что a·u0+b·v0=1. После этого нам надо доказать достаточность условия. Пусть равенство a·u0+b·v0=1 будет верным, в таком случае, если НОД (a, b) делит и a, и b, то он будет делить и сумму a·u0+b·v0, и единицу соответственно (это можно утверждать, исходя из свойств делимости). А такое возможно только в том случае, если НОД (a, b)=1, что доказывает взаимную простоту a и b.

В самом деле, если a и b являются взаимно простыми, то согласно предыдущему свойству, будет верным равенство a·u0+b·v0=1. Умножаем обе его части на c и получаем, что a·c·u0+b·c·v0=c. Мы можем разделить первое слагаемое a·c·u0+b·c·v0 на b, потому что это возможно для a·c, и второе слагаемое также делится на b, ведь один из множителей у нас равен b. Из этого заключаем, что всю сумму можно разделить на b, а поскольку эта сумма равна c, то c можно разделить на b.

Определение 5

Если два целых числа a и b являются взаимно простыми, то НОД (a·c, b)=НОД (c, b).

Доказательство 2

Докажем, что НОД (a·c, b) будет делить НОД (c, b), а после этого – что НОД (c, b) делит НОД (a·c, b), что и будет доказательством верности равенства НОД (a·c, b)=НОД (c, b).

Поскольку НОД (a·c, b) делит и a·c и b, а НОД(a·c, b) делит b, то он также будет делить и b·c. Значит, НОД (a·c, b) делит и a·c и b·c, следовательно, в силу свойств НОД он делит и НОД (a·c, b·c), который будет равен c·НОД (a, b)=c. Следовательно, НОД (a·c, b) делит и b и c, следовательно, делит и НОД (c, b).

Также можно сказать, что поскольку НОД (c, b) делит и c, и b, то он будет делить и c, и a·c. Значит, НОД (c, b) делит и a·c и b, следовательно, делит и НОД (a·c, b).

Таким образом, НОД (a·c, b) и НОД (c, b) взаимно делят друг друга, значит, они являются равными.

Определение 6

Если числа из последовательности a1, a2, …, ak будут взаимно простыми по отношению к числам последовательности b1, b2, …, bm (при натуральных значениях k и m), то их произведения a1·a2·…·ak и b1·b2·…·bm также являются взаимно простыми, в частности, a1=a2=…=ak=a и b1=b2=…=bm=b, то ak и bm – взаимно простые.

Доказательство 3

Согласно предыдущему свойству, мы можем записать равенства следующего вида: НОД (a1·a2·…·ak, bm) =НОД (a2·…·ak, bm) =…=НОД (ak, bm) =1. Возможность последнего перехода обеспечивается тем, что ak и bm взаимно просты по условию. Значит, НОД (a1·a2·…·ak, bm) =1.

Обозначим a1·a2·…· ak=A и получим, что НОД (b1·b2·…· bm, a1·a2·…·ak) =НОД (b1·b2·…· bm, A)= НОД (b2·…·b·bm, A)=… =НОД (bm, A) =1. Это будет справедливым в силу последнего равенства из цепочки, построенной выше. Таким образом, у нас получилось равенство НОД (b1·b2·…·bm, a1·a2·…·ak) =1, с помощью которого можно доказать взаимную простоту произведений a1·a2·…·ak и b1·b2·…·bm 

Это все свойства взаимно простых чисел, о которых бы мы хотели вам рассказать.

Решето Эратосфена

Часто нужно не проверять на простоту одно число, а найти все простые числа до \(N\). В этом случае наивный алгоритм будет работать за \(O(N\sqrt N)\), так как нужно проверить на простоту каждое число от 1 до \(N\).

Но древний грек Эратосфен предложил делать так:

Запишем ряд чисел от 1 до \(N\) и будем вычеркивать числа: * делящиеся на 2, кроме самого числа 2 * затем деляющиеся на 3, кроме самого числа 3 * затем на 5, затем на 7, и так далее и все остальные простые до n. Таким образом, все незачеркнутые числа будут простыми — «решето» оставит только их.

Найдите этим способом на бумажке все простые числа до 50, потом проверьте с программой:

У этого алгоритма можно сразу заметить несколько ускорений.

Во-первых, число \(i\) имеет смысл перебирать только до корня из \(N\), потому что при зачеркивании составных чисел, делящихся на простое \(i > \sqrt N\), мы ничего не зачеркнем. Почему? Пусть существует составное \(M \leq N\), которое делится на %i%, и мы его не зачеркнули. Но тогда \(i > \sqrt N \geq \sqrt M\), а значит по ранее нами доказанному утверждению \(M\) должно делиться и на простое число, которое меньше корня. Но это значит, что мы его уже вычеркнули.

Во-вторых, по этой же самое причине \(j\) имеет смысл перебирать только начиная с \(i^2\). Зачем вычеркивать \(2i\), \(3i\), \(4i\), …, \((i-1)i\), если они все уже вычеркнуты, так как мы уже вычеркивали всё, что делится на \(2\), \(3\), \(4\), …, \((i-1)\).

Гармонический ряд

Научимся оценивать асимптотику величины \(1 + \frac{1}{2} + \ldots + \frac{1}{N}\), которая нередко встречается в задачах, где фигурирует делимость.

Возьмем \(N\) равное \(2^i — 1\) и запишем нашу сумму следующим образом: \

Каждое из этих слагаемых имеет вид \

Таким образом, наша сумма не превосходит \(1 + 1 + \ldots + 1 = i \le 2\log_2(2^i — 1)\). Тем самым, взяв любое \(N\) и дополнив до степени двойки, мы получили асимптотику \(O(\log N)\).

Оценку снизу можно получить аналогичным образом, оценив каждое такое слагаемое снизу значением \(\frac{1}{2}\).

Попытка объяснения асимптотики** (для старших классов)

Мы знаем, что гармонический ряд \(1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{N}\) это примерно \(\log N\), а значит \

А что такое асимптотика решета Эратосфена? Мы как раз ровно \(\frac{N}{p}\) раз зачеркиваем числа делящиеся на простое число \(p\). Если бы все числа были простыми, то мы бы как раз получили \(N \log N\) из формули выше. Но у нас будут не все слагаемые оттуда, только с простым \(p\), поэтому посмотрим чуть более точно.

Известно, что простых чисел до \(N\) примерно \(\frac{N}{\log N}\), а значит допустим, что k-ое простое число примерно равно \(k ln k\). Тогда

\

Но вообще-то решето можно сделать и линейным.

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

Взаимно простыми могут быть как два целых числа, так и их большее количество. Для начала введем определение для двух чисел, для чего нам понадобится понятие их наибольшего общего делителя. Если нужно, повторите материал, посвященный ему.

Взаимно простыми будут два таких числа a и b , наибольший общий делитель которых равен 1 , т.е. НОД ( a , b ) = 1 .

Из данного определения можно сделать вывод, что единственный положительный общий делитель у двух взаимно простых чисел будет равен 1 . Всего два таких числа имеют два общих делителя – единицу и минус единицу.

Какие можно привести примеры взаимно простых чисел? Например, такой парой будут 5 и 11 . Они имеют только один общий положительный делитель, равный 1 , что является подтверждением их взаимной простоты.

Если мы возьмем два простых числа, то по отношению друг к другу они будут взаимно простыми во всех случаях, однако такие взаимные отношения образуются также и между составными числами. Возможны случаи, когда одно число в паре взаимно простых является составным, а второе простым, или же составными являются они оба.

Это утверждение иллюстрирует следующий пример: составные числа — 9 и 8 образуют взаимно простую пару. Докажем это, вычислив их наибольший общий делитель. Для этого запишем все их делители (рекомендуем перечитать статью о нахождении делителей числа). У 8 это будут числа ± 1 , ± 2 , ± 4 , ± 8 , а у 9 – ± 1 , ± 3 , ± 9 . Выбираем из всех делителей тот, что будет общим и наибольшим – это единица. Следовательно, если НОД ( 8 , − 9 ) = 1 , то 8 и — 9 будут взаимно простыми по отношению друг к другу.

Взаимно простыми числами не являются 500 и 45 , поскольку у них есть еще один общий делитель – 5 (см. статью о признаках делимости на 5 ). Пять больше единицы и является положительным числом. Другой подобной парой могут быть — 201 и 3 , поскольку их оба можно разделить на 3 , на что указывает соответствующий признак делимости.

На практике довольно часто приходится определять взаимную простоту двух целых чисел. Выяснение этого можно свести к поиску наибольшего общего делителя и сравнению его с единицей. Также удобно пользоваться таблицей простых чисел, чтобы не производить лишних вычислений: если одно из заданных чисел есть в этой таблице, значит, оно делится только на единицу и само на себя. Разберем решение подобной задачи.

Условие: выясните, являются ли взаимно простыми числа 275 и 84 .

Решение

Оба числа явно имеют больше одного делителя, поэтому сразу назвать их взаимно простыми мы не можем.

Вычисляем наибольший общий делитель, используя алгоритм Евклида: 275 = 84 · 3 + 23 , 84 = 23 · 3 + 15 , 23 = 15 · 1 + 8 , 15 = 8 · 1 + 7 , 8 = 7 · 1 + 1 , 7 = 7 · 1 .

Ответ: поскольку НОД ( 84 , 275 ) = 1 , то данные числа будут взаимно простыми.

Как мы уже говорили раньше, определение таких чисел можно распространить и на случаи, когда у нас есть не два числа, а больше.

Взаимно простыми целые числа a 1 , a 2 , … , a k , k > 2 будут тогда, когда они имеют наибольший общий делитель, равный 1 .

Иными словами, если у нас есть набор некоторых чисел с наибольшим положительным делителем, большим 1 , то все эти числа не являются по отношению друг к другу взаимно обратными.

Возьмем несколько примеров. Так, целые числа − 99 , 17 и − 27 – взаимно простые. Любое количество простых чисел будет взаимно простым по отношению ко всем членам совокупности, как, например, в последовательности 2 , 3 , 11 , 19 , 151 , 293 и 667 . А вот числа 12 , − 9 , 900 и − 72 взаимно простыми не будут, потому что кроме единицы у них будет еще один положительный делитель, равный 3 . То же самое относится к числам 17 , 85 и 187 : кроме единицы, их все можно разделить на 17 .

Обычно взаимная простота чисел не является очевидной с первого взгляда, этот факт нуждается в доказательстве. Чтобы выяснить, будут ли некоторые числа взаимно простыми, нужно найти их наибольший общий делитель и сделать вывод на основании его сравнения с единицей.

Условие: определите, являются ли числа 331 , 463 и 733 взаимно простыми.

Решение

Сверимся с таблицей простых чисел и определим, что все три этих числа в ней есть. Тогда их общим делителем может быть только единица.

Ответ: все эти числа будут взаимно простыми по отношению друг к другу.

Условие: приведите доказательство того, что числа − 14 , 105 , − 2 107 и − 91 не являются взаимно простыми.

Решение

Начнем с выявления их наибольшего общего делителя, после чего убедимся, что он не равен 1 . Поскольку у отрицательных чисел те же делители, что и у соответствующих положительных, то НОД ( − 14 , 105 , 2 107 , − 91 ) = НОД ( 14 , 105 , 2 107 , 91 ) . Согласно правилам, которые мы привели в статье о нахождении наибольшего общего делителя, в данном случае НОД будет равен семи.

Ответ: семь больше единицы, значит, взаимно простыми эти числа не являются.

Об этой статье

wikiHow работает по принципу вики, а это значит, что многие наши статьи написаны несколькими авторами. При создании этой статьи над ее редактированием и улучшением работали, в том числе анонимно, 60 человек(а). Количество просмотров этой статьи: 143 341.

Категории: Математика

English:Check if a Number Is Prime

Español:saber si un número es primo

Italiano:Riconoscere un Numero Primo

Português:Determinar se um Número é Primo

Deutsch:Überprüfen ob eine Zahl eine Primzahl ist

Nederlands:Controleren of een getal een priemgetal is

Čeština:Jak zjistit, zda je číslo prvočíslem

Печать

Значение составных чисел — пример

ПРИМЕР. Предположим, вы хотите знать, будет ли понедельник 26 апреля благоприятным днем для выполнения некоторых дел. Например, стоит ли просить повышения зарплаты.

Возьмем числа, соответствующие каждой букве вашего имени, добавим к общей их сумме составное число (или его однозначную основу), полученное сложением однозначных чисел даты 26 апреля (2 плюс 6 равно 8); добавим эту восьмерку к сумме чисел вашего имени и сумме чисел вашего рождения.

Посмотрите на значение получившегося числа, и вы поймете, является ли 26 апреля благоприятным днем или нет.

Если вы видите, что счастливого числа не получается, выберите следующий день, или еще один следующий — пока не дойдете до благоприятной даты.

Назначьте свои действия на эту дату, и вы обнаружите, что день, вычисленный таким образом, действительно является для вас благоприятным.

Предположим, ваше имя RAJIV GANDHI, а родились вы 13 мая.

ПРИМЕР: Прибавляем 2 и 1, получаем 3. К 3 вы прибавляете 8 (полученное из даты 26 апреля). Это дает нам составное число 11 (3 + 8), если свести к однозначному числу — то 2. Прибавляем это число к числу вашего рождения 13. Получаем 15.

Теперь посмотрим значение составного числа 15: для добывания денег, даров и благосклонности со стороны вышестоящих — это благоприятное число.

Таким образом, оккультное влияние на человека по имени RAJIV GANDHI, родившегося 13 мая, таково, что 26 апреля ему подходит для поиска благосклонности со стороны вышестоящих лиц, а также для осуществления планов.

Если эта дата не показывает благоприятного отношения к нужной вам деятельности, проверьте следующую, потом следующую — пока, наконец, не найдете благоприятную.

Используя другой подход к значению имени и составляющих его чисел, мы можем получить еще одно значение имени RAJIV GANDHI.

Сумма вибраций части имени RAJIV- 11, а части имени GANDHI — 19. Это означает, что сумма вибраций полного имени равна 30, и нужно найти значение этого числа, а оно таково.

Число глубоких выводов, размышлений о прошлом, духовного превосходства над окружающими, но поскольку оно принадлежит, как видно, только духовному плану, люди, которых оно представляет, должны, вероятно, видеть только определенный аспект материальных вещей не потому что должны, а потому, что они так хотят.

Поэтому это число ни счастливое, ни несчастливое — все зависит от взгляда человека, которого оно представляет. Число может нести мощь и силу, но часто равнодушно по отношению к воле и желаниям человека.

Статьи журнала starfate » Нумерология » Что такое составные числа в Нумерологии

Понятие попарно простых чисел

Зная, что из себя представляют взаимно простые числа, мы можем сформулировать определение попарно простых чисел.

Определение 7

Попарно простые числа – это последовательность целых чисел a1, a2, …, ak, где каждое число будет взаимно простым по отношению к остальным.

Примером последовательности попарно простых чисел может быть 14, 9, 17, и −25. Здесь все пары (14 и 9, 14 и 17, 14 и −25, 9 и 17, 9 и −25, 17 и−25) взаимно просты. Отметим, что условие взаимной простоты является обязательным для попарно простых чисел, но взаимно простые числа будут попарно простыми далеко не во всех случаях. Например, в последовательности 8, 16, 5 и 15 числа не являются таковыми, поскольку 8 и 16 не будут взаимно простыми.

Также следует остановиться на понятии совокупности некоторого количества простых чисел. Они всегда будут и взаимно, и попарно простыми. Примером может быть последовательность 71, 443, 857, 991. В случае с простыми числами понятия взаимной и попарной простоты будут совпадать.

Общие сведения

В системе счисления и мер используется специальная система знаков, называемая цифрами. Слово «цифра» происходит от латинского cifra. Интересно, что на арабском термин пишется как صفر‎, что в дословном переводе на русский язык обозначает «пустой». С этих символов формируются числа. Чтобы разобраться в отличиях одних от других, нужно запомнить 3 утверждения:

1. Всего существует 10 цифр — 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
2. Из десяти символов формируют числа.
3. Цифры — это знаки, а числа — абстракции, обозначающие количество.

Нужно знать, что существует несколько систем счисления. В России принято использовать арабскую. В церковнославянском и древнегреческом применяли запись буквами. Её до сих пор используют в иврите. В программировании применяется смешанная запись. Так как она шестнадцатеричная, используют комбинации знаков: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Итак, «число» и «цифра» разные понятия по происхождению. Первое используют как единицу счёта. Им выражают количество. Второй же параметр применяют для обозначений значений. Для записи в международном формате принята арабская последовательность от 0 до 9, но в некоторых случаях ставят и римские символы — I, II, III, IV, V, V I, V II, V III, IX, X и так далее.

По своему виду числа бывают:

• натуральными — простыми целыми, использующимися при счёте,
• рациональными — конечными дробными отношениями,
• иррациональными — бесконечными непериодическими дробями,
• действительными — образующими множество, включающее рациональные и иррациональные значения.

Составление формулы простого числа

Чтобы увидеть всё своими глазами, а не полагаться только на слова, составим простую компьютерную программу, которая бы рисовала точку в центре, а вокруг нее по спирали располагала бы все числа натурального ряда. Программа будет отмечать черным цветом точки, соответствующие простым числам, а серыми — составные. Вот что мы получим:

У самого центра диаграммы одна такая закономерность пролегает сверху вниз и слева направо. Она состоит из последовательности чисел: 7, 23, 47, 79. Оказывается, эту последовательность можно описать квадратичной функцией р = 4х2 + 4х – 1.

С помощью этого графика можно задать формулой любую последовательность простых чисел. Рассмотрим, например, последовательность, берущую свое начало из точки 5 и идущую справа налево сверху вниз. Следующее число в этой последовательности 19, затем идут 41, 71… Попробуем описать ее рекуррентной формулой. Для этого сначала рассмотрим каждый квадрат, состоящий из точек. У любого такого квадрата на восемь точек больше, чем у вложенного в него, — это очень легко доказать. Значит, разность между любыми двумя точками, лежащими в соседних квадратах по одному правилу, будет увеличиваться на восемь по сравнению с предыдущими. Для определенности за отношение «лежать по одному правилу» примем точки, лежащие в соседних квадратах, причем из точки, лежащей в меньшем квадрате, можно перейти к точке из большего квадрата, если перейти в другой квадрат по кратчайшему расстоянию и затем сместиться на число t, где t целое, причем t — постоянное число для данного правила. В нашем случае t = 1.

Если разность между точками, лежащими в 1­м и 2­м квадратах от центра, равна 14, то разность между точками 2­го и 3­го квадратов возрастет на 8 и будет равна 22. Теперь можно составить формулу: следующий член последовательности будет отличаться от предыдущего на 14 + 8·n, где n — номер члена последовательности, то есть номер квадрата от центра. Если считать 5 нулевым членом и каждый член больше предыдущего на 8·(n – 1), где n — номер квадрата, то получим:

Это и есть формула данной последовательности.

И таким образом можно составить сколько угодно формул последовательностей простых чисел, но всегда на каком­то номере окажется, что число вовсе не простое. Примечательно, что если в качестве начальной точки взять число не 1, а 41, то мы увидим последовательность, состоящую из 41 простого числа!

Никакая целая рациональная функция от х с целыми коэффициентами не может для любого натурального значения х равняться простому числу (теорема Гольбаха).

Быстрое возведение в степень

Задача: > Даны натуральные числа \(a, b, c < 10^9\). Найдите \(a^b\) (mod \(c\)).

Мы хотим научиться возводить число в большую степень быстро, не просто умножая \(a\) на себя \(b\) раз. Требование на модуль здесь дано только для того, чтобы иметь возможность проверить правильность алгоритма для чисел, которые не влезают в int и long long.

Сам алгоритм довольно простой и рекурсивный, постарайтесь его придумать, решая вот такие примеры (прямо решать необязательно, но можно придумать, как посчитать значение этих чисел очень быстро):

• \(3^2\)
• \(3^4\)
• \(3^8\)
• \(3^{16}\)
• \(3^{32}\)
• \(3^{33}\)
• \(3^{66}\)
• \(3^{132}\)
• \(3^{133}\)
• \(3^{266}\)
• \(3^{532}\)
• \(3^{533}\)
• \(3^{1066}\)

Да, здесь специально приведена такая последовательность, в которой каждое следующее число легко считается через предыдущее: его либо нужно умножить на \(a=3\), либо возвести в квадрат. Так и получается рекурсивный алгоритм:

• \(a^0 = 1\)
• \(a^{2k}=(a^{k})^2\)
• \(a^{2k+1}=a^{2k}\times a\)

Нужно только после каждой операции делать mod: * \(a^0 \pmod c = 1\) * \(a^{2k} \pmod c = (a^{k} \pmod c)^2 \pmod c\) * \(a^{2k+1} \pmod c = ((a^{2k}\pmod c) \times a) \pmod c\)

Этот алгоритм называется быстрое возведение в степень. Он имеет много применений: * в криптографии очень часто надо возводить число в большую степень по модулю * используется для деления по простому модулю (см. далее) * можно быстро перемножать не только числа, но еще и матрицы (используется для динамики, например)

Асимптотика этого алгоритма, очевидно, \(O(\log c)\) — за каждые две итерации число уменьшается хотя бы в 2 раза.