Закрыть

ЧИСЛОВОЙ ИНВАРИАНТ И ПРОСТЫЕ ЧИСЛА

Автор: Шамутдинов Айдар Харисович
Опубликовано 19.07.2011 в 08:21
Раздел: Теория чисел
Теги:

 

Шамутдинов Айдар Харисович, старший преподаватель ОмГТУ каф. «ГМ и ТМ», 15 июля 2011 г.

ЧИСЛОВОЙ ИНВАРИАНТ И ПРОСТЫЕ ЧИСЛА

Теорема 1

Любое число, не кратное 9, можно представить в виде N=9K+i, где i-инвариант числа, а К=[N/9]

То есть: 

N=9[N/9]+i         (1), где 

[ ]-целая часть числа.

Отсюда видно, что i=N(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}

См. http://aidar-shamutdinov.narod2.ru/

 

Комментарии (2)

  • Васин Алексей 2011-09-21  [ ответить ]

    Если число простое, то его инвариант принадлежит множеству: {1, 2, 4, 5, 7,  8} и окончание числа принадлежит множеству: {1, 3, 7, 9}.Вы уверены что это утверждение стоит наывать теоремой? Первая часть следует из определения инварианта, а вторая известни и раньше. Или я что-то не догоняю?

  • Васин Алексей 2011-09-21  [ ответить ]

    Извиняюсь не по определению, а по свойству 1.

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
  • 2017-07-09 14:11:58 Robertfoere » трейдинг

    Я получил бесплатно $100 для обу...

  • 2017-07-09 13:54:28 Robertfoere » forex

    Я получил бесплатно $100 для ...

  • 2017-07-09 07:21:33 Robertfoere » trader

    Я получил бесплатно $100 для обу...

  • 2017-07-09 07:03:20 Robertfoere » broker

    Я получил бесплатно $100 для обу...

  • 2017-07-06 14:45:03 Robertfoere » stock exchange

    Я получил бесплатно $100 для обу...

Aрхив статей