Шамутдинов Айдар Харисович : другие произведения.

Числовой инвариант и простые числа

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:


 Ваша оценка:

  Шамутдинов Айдар Харисович, старший преподаватель ОмГТУ каф. 'ГМ и ТМ', 15 июля 2011 г.
  
  ЧИСЛОВОЙ ИНВАРИАНТ И ПРОСТЫЕ ЧИСЛА
  
  Теорема 1
  Любое число, не кратное 9, можно представить в виде N=9K+i, где i-инвариант числа, а К=[N/9]
  То есть:
  N=9[N/9]+i (1), где
  [ ]-целая часть числа.
  Отсюда видно, что N=i(mod9)
  
  
  Доказательство :
  Пусть N=a1a2a3...an =10^(n-1)a1+10^(n-2)a2+...+an. Преобразуем это выражение:
  N=a1a2a3...an=10^(n-1)a1+10^(n-2)a2+...+an=(99...9((n-1)раз 9)a1+99...9
  ((n-1)раз 9) a2+...+9a(n-1))+(a1+a2+a3+...+an)
  Рассмотрим два случая: 1) a1+a2+a3+...+an
  <9:
  10^(n-1)a1+10^(n-2)a2+...+an=(99...9((n-1)раз 9)a1+99...9 ((n-2)раз 9) a2+...+9a(n-1))+( a1+a2+a3+...+an )=
  =(99...9((n-1)раз 9)a1+99...9 ((n-2)раз 9) a2+...+9a(n-1))+i
  
  Тогда [N/9]= (11...1((n-1)раз 1)a1+11...1((n-2)раз 1) a2+...+a(n-1))+[i/9], т.к. по определению инварианта i<9, то [i/9]=0. Поэтому
  [N/9]=(11...1((n-1)раз 1)a1+11...1((n-2)раз 1) a2+...+a(n-1)).
  
  
  2)a1+a2+a3+...+an>9:
  Тогда
  10^(n-1)a1+10^(n-2)a2+...+an=(99...9((n-1)раз 9)a1+99...9 ((n-2)раз 9) a2+...+9a(n-1))
  + ( a1+a2+a3+...+an )
  Тогда [N/9]=(11...1((n-1)раз 1)a1+11...1((n-2)раз 1) a2+...+a(n-1))+[(a1+a2+...+an)/9](2)
  
  Таким образом, приходим к формуле (1): N=9[N/9]+i
  Причем, если N=9M, т.е. N кратно девяти, то
  
  N=9[(N-9)/9]+i (3)или N=9[(9M-9)/9]+9=9(M-1)+9=9M
  
  Как следствие из формулы (1) вытекает и формула для вычисления инварианта числа:
  
  i(N)=N-9[N/9] (4),
  где N-некратно девяти.
  Если N=9M, то
  i(N)=N-9[(N-1)/9] (5)
  
  Используя выражение (2) можно записать и другую формулу для вычисления инварианта:
  
   i(a1a2...an)=(a1+a2+...+an), если
  (a1+a2+...+an)<9
  
   i(a1a2...an)=9, если
  (a1+a2+...+an)=9k
  
   i(a1a2...an)=(a1+a2+...+an)-9[(a1+a2+...+an)/9], если
  (a1+a2+...+an)>9
  
   Пример 1
  Найти инвариант числа 6678548311358024717
  Решение:
  i(6678548311358024717)= 6678548311358024717-9[6678548311358024717/9]= 6678548311358024717-9(742060923484224968)=5.
  Проверка: i(6678548311358024717)=i(6+6+7+8+5+4+8+3+1+1+3+5+8+0+2+4+7+1+7)=i(86)=i(8+6)=i(14)=i(1+4)=5
  
  Пример 2.
  Найти инвариант числа 18234612
  Решение:
  i(18234612)=18234612-9[(18234612-1)/9]= 18234612-9(2026067)=9
  Проверка:
  i(18234612)=i(1+8+2+3+4+6+1+2)=i(27)=i(2+7)=9
  
  Видно, что формулы (4) и (5) очень удобны при вычислении инварианта очень большого числа, т.е. десятичная запись которого состоит из большого количества цифр. Кроме того формула (3) очень удобна для определения кратности числа N девяти. Как мы знаем по признаку делимости: число делится(кратно) девяти тогда, когда делится(кратна) сумма цифр данного числа. Но если число состоит из очень большого количества цифр, то операция сложения цифр числа довольно затруднительна. Поэтому считаем(естественно на калькуляторе) по формуле (3) инвариант данного числа: если в результате получился 0, то данное число делится(кратно) на 9(если по формуле (4), то будет 9).
  
  Теорема 2 (необходимое условие простоты числа)
  Если число простое, то его инвариант принадлежит множеству: {1, 2, 4, 5, 7, 8} и окончание числа принадлежит множеству: {1, 3, 7, 9},
  где i-инвариант числа;
  e-окончание числа.Исключение: числа 2, 3 и 5
  
  Доказательство :
  1)По теореме 1 имеем:N=9К+i или:
  N=a1a2...an=9(11...1((n-1)раз 1)a1+11...1((n-2)раз 1) a2+...+a(n-1))+i,
  если a1+a2+a3+...+an<9;
  N= a1a2...an= 9(11...1((n-1)раз 1)a1+11...1((n-2)раз 1) a2+...+a(n-1)+[(a1+a2+...+an)/9])+i,
  если a1+a2+a3+...+an>9,
  
  Если i=3, 6 или 9, то видно, что N=3(K+1), 3(K+2) или 3(K+3). Видно, что число будет обязательно делиться на 3, т.е. составное.
  2) Любое число представимо в виде:N=10M+е. Если е=2, 4, 6 или 8, то: N=2(5к+1), 2(5к+2), 2(5к+3) или 2(5к+4). Видно, что число будет обязательно делиться на 2, т.е. составное.
  Таким образом, все простые числа(p>7) имеют инвариант, равным 1, 2, 4, 5, 7 или 8 и оканчиваются на 1, 3, 7 или 9.
  
  Пример 3
  Даны простые числа p1=113, p2=127, p3=137, p4=139, p5=151, p6=179. Находим их инварианты: i(113)=1+1+3=5, i(127)=i(1+2+7)=i(10)=1+0=1,
  i(1+3+7)=i(11)=1+1=2, i(139)=i(1+3+9)=i(13)=1+3=4, i151)=1+5+1=7,
  i(179)=i(1+7+9)=i(17)=1+7=8. Кроме того окончания этих чисел принадлежат
  множеству {1, 3, 7, 9}
  
  Пример 4
  Даны числа: 127, 129, 591, 133. Определить их на простоту.
  Решение:
  Находим их инварианты: i(127)=1, i(129)=3,
  i(591)=6, i(133)=7. Видим, что
  инварианты у чисел 129 и 591 не принадлежат множеству {1, 2, 4, 5, 7, 8}, хотя
  и окончания у них принадлежат множеству простых чисел {1, 3, 7, 9}. Поэтому
  можно сразу сказать, что числа 129 и 591 не являются простыми числами. По
  таблице простых чисел убеждаемся, что число 127-простое, а число 133=7×19-составное.
  Таким образом, знание теоремы о необходимых условиях простоты числа экономит
  время на вычисления, а в некоторых случаях сразу можно определить составное
  число.
  
   См. http://aidar-shamutdinov.narod2.ru/
 Ваша оценка:

Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"