Исследовательская работа на тему «О представимости натуральных чисел в виде линейной комбинации с целыми коэффициентами».

Исследовательская работа на тему: «О представимости натуральных чисел в виде линейной комбинации с целыми коэффициентами».     Ученицы 9А класса     МОУ СОШ №36 Сидоренко Леры      Руководитель:       учитель математики      Жак А.М. 1 Оглавление  Ученицы 9А класса..........................................................................................................................1  МОУ СОШ №36..............................................................................................................................1  Сидоренко Леры..............................................................................................................................1 Введение............................................................................................................................................3 Алгоритм Евклида............................................................................................................................5 Решение основных задач..................................................................................................................7 Заключение......................................................................................................................................11 Литература:.....................................................................................................................................12 2 Введение В информационно­безопасной системе должны обеспечиваться  определенные свойства информации: 1. 2. 3. 4. 5. Конфиденциальность информации  Целостность информации  Авторство информации  Актуальность информации  Доступность информации. Одно из самых важных условий информационной безопасности — это  идентификация субъектов платежной системы. Во многих системах клиент  идентифицируется своим идентификатором — паролем, который он выбирает  при регистрации, или атрибутами карты в карточных системах. В системах, не  требующих в использовании специального программного обеспечения для  клиента, другого способа идентификации клиента не может существовать.  Такой способ идентификации используют многие карточные системы, крупные  магазины, электронные казино, биллинговые системы и др. Так же очень важен правильный выбор криптографических алгоритмов, их  корректное встраивание в систему, а также отслеживание событий и новых  тенденций в криптографии. Например, некоторые системы используют  слишком маленькие длины ключей в криптографических алгоритмах.  Очевидно, самым распространенным криптографическим алгоритмом  для цифровых подписей и шифрования несимметричными ключами является  RSA (авторы ­ Rivest, Shamir и Adleman). Отметим, что целый ряд российских  платежных систем используют именно этот алгоритм, среди них, например,  WebMoney и Яндекс.Деньги. Уже общепринято, что RSA — высоконадежный  алгоритм. Его безопасность основана на трудности представления натуральных чисел. Специалисты считают, что тотальный взлом этой системы эквивалентен  3 нахождению приватного ключа по публичному. Эту возможность можно легко  нейтрализовать, увеличив размер ключа.           Актуальность: Представимость натуральных чисел в виде линейной комбинации с  целыми коэффициентами используется в теории диофантовых приближений,   для решения уравнений с несколькими неизвестными.     Цель: Доказать возможность представимости натуральных чисел в виде  линейной комбинации с целыми коэффициентами. Задачи: 1. 2. Рассмотреть Алгоритм Евклида. Рассмотреть возможные случаи представимости натуральных чисел в виде линейной комбинации с целыми коэффициентами. 3. Доказать возможность представимости любого натурального числа  в виде  линейной комбинации с целыми коэффициентами.         4 Алгоритм Евклида. Алгоритм Евклида – это способ нахождения наибольшего общего  делителя двух целых чисел, а также наибольшей общей меры двух  соизмеримых отрезков. Чтобы найти наибольший общий делитель двух целых положительных  чисел, нужно сначала большее число разделить на меньшее, затем второе  число разделить на остаток от первого деления, потом первый остаток ­ на  второй и т.д. Последний ненулёвой положительный остаток в этом процессе и будет наибольшим общим делителем данных чисел. Приведём пример.  Пусть а=777, b=629. Тогда 777=629 1+148, 629=148 4+37, 148=37 4. Последний ненулевой остаток 37 есть наибольший общий делитель  чисел 777 и 629. Для нахождения наибольшей общей меры двух отрезков поступают  аналогично. Операцию деления с остатком заменяют его геометрическим  аналогом: меньше отрезок откладывают на большим столько раз, сколько  возможно: оставшуюся часть большего отрезка (принимаемую за остаток  отделения) откладывают на меньшем отрезке и т.д., если отрезки a и b  соизмеримы, то последний не нулевой остаток даст наибольшую общую меру  этих отрезков. В случае несоизмеримых отрезков получаемая  последовательность не нулевых остатков будет бесконечной. Алгоритм Евклида известен издавна. Ему уже более 2000 лет. Этот  алгоритм сформулирован в “Началах” Евклида, где из него выводятся  свойства простых чисел, наименьшего общего кратного и т.д. Как способ  нахождения наибольшей общей меры двух отрезков алгоритм Евклида  (иногда называемый методом попеременного вычитания) был известен ещё  пифагорейцам. К середине XVI в. алгоритм Евклида был распространён на  5 многочлены, от одного переменного в дальнейшем удалось определить  алгоритм Евклида и для некоторых других алгебраических объектах. Алгоритм Евклида имеет много применений.  Алгоритм Евклида является средством для представления  рационального числа в виде цепной дроби. Он часто используется в  программах для электронных вычислительных машин.  Для “ручного” счета алгоритм Евклида выглядит так:     1) если числа равны, то взять любое из них в качестве ответа, в противном  случае продолжить выполнение алгоритма;     2) заменить большее число разностью большего и меньшего чисел;     3) вернуться к выполнению п. 1. Рассмотрим этот алгоритм на примере:                                  НОД(32,24)=НОД(8,24)=НОД(8,16)=НОД(8,8)=8 6 Решение основных задач Задача № 1: какие целые числа могут быть выражены линейной комбинацией  натуральных чисел a и b с целыми коэффициентами x и y?    Определение. a +  b    называется линейной комбинацией чисел a и b с коэффициентами       Очевидно, что если мы выразим линейной комбинацией чисел a и b число 1,  то мы сможем выразить и любое целое число. Далее будем обозначать x и y  коэффициенты при a и b, требующиеся для выражения единицы.    Поскольку мы рассматриваем взаимно простые a и b, то НОД(a,b)=1. НОД  двух чисел можно вычислить, применив алгоритм Евклида.    Например, вычислим НОД(a, b) (мы знаем, что он равен 1) для a=11, b=7 по  алгоритму Евклида: НОД(11,7)=НОД(4,7)=НОД(4,3)=1 11=7 1+4 7=4 1+3 4=3 1+1              Отсюда выразим единицу: 1=4 1+3 (­1)=                          3=7 1+4  (­1) =4 1+7 (­1)+4 1= =4 2+7 (­1)=                            4=11 1+7  (­1) =11 2+7 (­2)+7 (­1)= =11 2+7 (­3)   1= 11 2+7 (­3)                      Т. е. x=2, y=(­3). Аналогично с помощью алгоритма Евклида можно  выразить число 1 линейной комбинацией взаимно простых чисел a и b, т.е. любые  7 числа могут быть выражены линейной комбинацией взаимно простых чисел a и b с  целыми коэффициентами x и y. Можно описать алгоритм действий:        1.  Выражаем единицу из последнего равенства.        2.  Выражаем остаток из предпоследнего равенства.        3.  Подставляем это выражение в выражение для единицы, полученное на  предыдущем шаге.        4.  Выражаем остаток из предпоследнего равенства.        5.  Подставляем это выражение  в выражение для единицы.        6.  Повторяем эти действия, пока не получим выражение единицы линейной комбинацией чисел a и b.    Пример:  Представим в виде линейной комбинации число 15. 15 1=15 (11 2+7(­3))= =11 30+7  (­45),    т.е. x=30           y=­45                                                                                   Задача №2 :  какие числа могут быть выражены линейной комбинацией 3  взаимно простых чисел с целыми коэффициентами (как выразить единицу в виде  a1x1 + a2x2 +a3x3 = 1) ?            Будем рассматривать коэффициенты, ни один из которых не равен 0, так как  иначе задачу легко свести к задаче с меньшим количеством чисел. Существует два случая: 1. Среди чисел существует взаимно простая пара чисел. 2. Среди чисел не существует взаимно простая пара чисел. Случай 1: a1x1 + a2x2 + a3x3 = 1, a1x1 + a2x2 = 1­ a3x3 причем a1 и a2 – взаимно простые, а x3 может быть любым целым числом.  Поскольку мы           можем выразить число 1 линейной комбинацией чисел a1 и a2(по способу, описанному в решении задачи № 1), мы можем выразить число (1­  a3x3)  8 линейной комбинацией чисел a1 и a2. Отсюда мы можем выразить число 1, перенеся   (a3x3) в левую часть. Пример:  НОД(10;33)=НОД(10;23)=НОД(10;13)=НОД(10;3)=НОД(7;3)=НОД(4;3)=НОД(1;3)= НОД(1;2)= НОД(1;1)=1  33=23 1+10 23=13 1+10 13=10 1+3 10=3 3+1 1=10 1­3 3=10 1­3(13 1­10 1)=10 1­13 3+10 3=10 4­13 3=10 4­3(23 1­10 1)= =10 4­23 3+10 3=10 7­23 3=10 7­3(33 1­10 1)=10 7­33 3+10 3=10 10­33 3 a=10      b=33                        1=10 10­33 3 x=10      y=­3 Представим число 7. 7 1=7(10 10­33 3)=10 70­33 21 7=10 70­33 21 a=10      b=33 x=70      y=­21 1+6=10 70­33 21 1+2 3=10 70­33 3 1=10 70­33 21­2 3 a1=10    a2=33   a3=2 x1=70    x2=­21   x3=­3 Причем 10 и 33 взаимно простые числа. Например, представим число 12. 12 1=12(10 70­33 21­2 3)=10 840­33 252­2 36 12=10 840­33 252­2 36 a1=10   a2=33   a3=2 x1=840   x2=­252   x3=­36    Случай 2: 9 1)   Находим НОД от двух не взаимно простых чисел с помощью алгоритма  Евклида.  2)   От найденного ранее НОДа и третьего числа находим НОД (он равен  единице) с помощью алгоритма Евклида.  3)   Выражаем единицу с помощью  второй группы равенств.  4)   Выражаем НОД первых двух чисел с помощью первой группы равенств,  подставляем  это выражение в выражение единицы. Например: Даны числа 10, 15 и 18 1)    НОД(18;15)=НОД(3;15)=НОД(3;12)=НОД(3;9)=НОД(3;6)=НОД(3;3)=3 18=15 1+3 2)    НОД(3;10)=НОД(3;7)=НОД(3;4)=НОД(3;1)=НОД(2;1)=НОД(1;1)=1 10=3 3+1 3)    1=10 1­3 3 4)    1=10 1­3(18 1­15 1)=10 1­18 3+15 3               1=10 1­18 3+15 3 Пример: Число 8. 8 1=8(10 1­18 3+15 3)=10 8­18 24+15 24 8=10 8­18 24+15 24    x1=8      x2=24       x3=24  a1=10    a2=­18      a3=15 Существуют тройки чисел, среди которых есть и взаимно простые, и не  взаимно простые пары. Для них подходят оба способа нахождения  коэффициентов. 10 Заключение. Результаты, полученные при выполнении работы, помогают решать уравнения в целых числах типа D = a +  b ,  где даны D, a и b, и  требуется найти   и  , причём в правой части слагаемых может быть сколь  угодно много. В ходе работы было доказано, что: 1.Любое целое число z можно выразить бесконечным числом способов в  виде x a +y b, где a и b – целые взаимно простые неотрицательные числа, а x и y ­ целые коэффициенты.  2. Доказано, что любое целое число может быть выражено линейной  комбинацией m взаимно простых чисел с целыми коэффициентами. Найдены  способы нахождения этих коэффициентов. 3. Найдены формулы, выражающие число, после которого все числа  выражаются линейной комбинацией m взаимно простых чисел с целыми  положительными коэффициентами. 11 Литература: 1. Энциклопедический словарь юного математика.  2. Курс лекций И.М.Гельфанда по линейной алгебре. 12