вычеты это в математике

GOUSPO студенческий портал!

форум, учебники, лекции, и многое другое

Основы алгебры вычетов.

Тема 9. Основы алгебры вычетов.

План:

2.Сравнение по модулю.

3. Свойства сравнимости

Цель. Знакомство с понятиями класса вычетов, отношением сравнимости и его свойствами.

Теоретические сведения

1. Понятие вычета.

Вычетом числа a по модулю m называется остаток от деления a на m

Из определения видно, что вычеты связаны с делением с остатком.

Разделить натуральное число a на нату­ральное число b с остатком означает yнайти неотрицательные числа два числа q и г, причем г (а ± с) º (b ± d)(mod p).

Слагаемые можно переносить из одной части сравне­ния в другую с противоположным знаком.

3. Сравнения можно перемножать:

4. Обе части сравнения можно умножить на одно и то же целое число k:

5. Обе части сравнения и модуль можно умножить на одно и то же число:

6. Обе части сравнения можно возвести в степень (следствие свойства 3):

Понятие сравнения ввел К.Ф.Гаусс в работе Ариф­метические исследования (1802). Алгебра вычетов возникает в тех случаях, когда рассматриваются некоторые циклически повторя­ющиеся события, например время в течение дня, повторяющееся каждые 24 часа, углы по окружности, повторяющиеся через пе­риод 2к, и т.д.

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

Задание 9-2. Для степени y=2 n (n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.

Решение и комментарии.

Как известно, натуральные степени числа 2 оканчиваются циф­рами <2, 4, 8, 6>. См. таблицу нескольких степеней числа 2.

Опреде­лим функцию, которая ставит в соответствие каждому натуральному числу п последнюю цифру числа 2 я :

цифра 2 т1222443884166532266447128882566

Эта функция f(n) периодична с периодом 4. Это значит, что для целого числа k: f(n)=f(n+4)= f(n+4k),.

Причем справедливы так же равенства: f(n)=f(n-4)= f(n-4k)

Но это задача на делении с остатком числа n на 4:

n=4k+m, k- частное, т остаток.

Очевидно, последняя цифра числа 2 зависит от остатка, полученного при делении показателя n степени 2 n на 4.

Отразим этот факт в записи функции: f(n)= f(n mod 4)

Из этой формулы можно установить, если f(n mod 4)=0, то

При делении чисел на 4 nÎN, останки могут быть: 0,1,2,3. Таким образом, в частности, множество всех возможных показателей степени 2 n для любого n состоит из четырех подмножеств: 4k, 4k+ 1, 4k+ 2, 4k+3.

Задание 9-3. Установить последнюю цифру степени y=2 2007

Решение. Имеем 2007=501·4+3, значит f (2007)=f (3)=2 3 =8. Ответ 8.

Требования к знаниям умениям и навыкам

Студенты должны знать определения вычета. Иметь представление о выполнении операций над вычетами. Иметь представление о числовом и цифровом кодировании.

Источник

Значение слова «вычет»

2. Сумма, удержанная, вычтенная из денег, предназначенных к выдаче.

Источник (печатная версия): Словарь русского языка: В 4-х т. / РАН, Ин-т лингвистич. исследований; Под ред. А. П. Евгеньевой. — 4-е изд., стер. — М.: Рус. яз.; Полиграфресурсы, 1999; (электронная версия): Фундаментальная электронная библиотека

Вычет в теории чисел — элемент кольца вычетов.

Вычет функции в комплексном анализе — коэффициент при степени

в ряде Лорана для данной функции.

Вычет в финансовых расчётах — удержание из денежной суммы, например: налоговый вычет.

ВЫ’ЧЕТ, а, м. 1. Действие по глаг. вычесть-вычитать во 2 знач. Произвести в. из зарплаты. 2. Вычтенная, удержанная при вычете сумма денег. В. составляет двадцать рублей. Большой в.

Источник: «Толковый словарь русского языка» под редакцией Д. Н. Ушакова (1935-1940); (электронная версия): Фундаментальная электронная библиотека

вы́чет

1. отторжение какой-либо части чего-либо, предназначенного, выделенного, отведённого для чего-либо ◆ Допустимой областью (пространством, в котором могут располагаться элементы) является подкапотное пространство, за вычетом запрещённых областей. В. А. Овчинников, «Применение генетических алгоритмов в задачах синтеза кузова автомобиля», 2004 г. // «Информационные технологии» (цитата из НКРЯ) ◆ КОЛИЧЕСТВО НОРМОЧАСОВ ― определяется как затраченное специалистом на работу время за вычетом непроизводственных затрат времени (обед, оформление документов, исправление своих ошибок, изучение нестандартных конфигураций, дорога к месту работы, телефонные разговоры и др., перечисленные в приложении) Вынужденные простои в работе специалиста от исполнителя вызванные действиями заказчика оцениваются и оплачивается, как время затраченное на работу по стандартным почасовым расценкам (20 у. е. в час, включая НДС) «Договор об оказании сервисных услуг», 2003 г. (цитата из НКРЯ)

2. то, что отторгается при вычете [1]

3. фин. удержание, зачёт, вычет какой-либо оговоренной части из денег, предназначенных к выдаче, начислению, зачёту, учёту и тому подобному ◆ В качестве примера можно привести спор о порядке применения вычета НДС при строительстве «для собственного потребления», когда организации строят промышленные объекты собственными силами («хозяйственным способом»). Недостроенное жилье и земельный налог, «2004» // «Бухгалтерский учёт» (цитата из НКРЯ)

4. фин. то, что удерживается, засчитывается при вычете [3] ◆ Как известно, с ипотеки можно вернуть налоговый вычет, но максимум с 2 млн руб. «Возврат налогового вычета», 2010–2012 г. (цитата из НКРЯ)

5. матем. комплексное число, пропорциональное контурному интегралу от данной комплексной функции по замкнутому контуру, охватывающему особую точку функции ◆ Теория вычетов одного комплексного переменного была в основном разработана Огюстеном Коши.

Источник

Модульная арифметика

2.2. Модульная арифметика

Операции по модулю

Как показано на рис. 2.9, оператор по модулю ( mod ) выбирает целое число ( a ) из множества Z и положительный модуль ( n ). Оператор определяет неотрицательный остаток ( r ).

Мы можем сказать, что

Найти результат следующих операций:

Система вычетов: Zn

Сравнения

Рисунок 2.11 показывает принцип сравнения. Мы должны объяснить несколько положений.

Система вычетов

Круговая система обозначений

Операции в Zn

Выполните следующие операторы (поступающие от Z_n ):

а. Сложение 7 и 14 в Z₁₅

б. Вычитание 11 из 7 в Z₁₃

в. Умножение 11 на 7 в Z₂₀

Ниже показаны два шага для каждой операции:

Выполните следующие операции (поступающие от Z_n ):

a. Сложение 17 и 27 в Z₁₄

b. Вычитание 43 из 12 в Z₁₃

Ниже показаны два шага для каждой операции:

Свойства

Первое свойство: (a + b) mod n = [(a mod n) + (b mod n)] mod n

Третье свойство: (a x b) mod n = [(a mod n) x (b mod n)] mod n

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

Следующие примеры показывают приложение вышеупомянутых свойств.

Источник

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

Классы вычетов. Системы вычетов

Краткие сведения из теории

Применяя теорему о делении с остатком можно множество целых чисел разбить на ряд классов. Рассмотрим пример. Пусть m= 6. Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:

r = 0;

r = 1;

r = 2;

r = 3;

r = 4;

r = 5;

где через rобозначен остаток от деления целого числа на 6.

Напомним теорему о делении с остатком:

Теорема: Разделить число на число , , с остатком, значит, найти пару целых чисел q и r, таких, что выполняются следующие условия: .

Легко доказывается, что для любых целых чисел а и деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество <0, 1, 2, 3, 4, 5>; полная система наименьших положительных вычетов – множество <0, 1, 2, 3, 4, 5>; полная система наименьших по абсолютной величине вычетов – множество <-2,-1, 0, 1, 2, 3>; приведённая система вычетов – множество <1,5>, так как ; фактор-множество

Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные простые числа – модули .

Чаще всего числа выбирают из множества простых чисел.

Пусть …, .

Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. где , то кольцо Z, по определению, является евклидовым.

Таким образом, в качестве чисел можно выбрать остатки от деления числа А на р_i соответственно.

Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Полная система вычетов по модулю n ― любой набор из n попарно несравнимых по модулю n целых чисел. Обычно в качестве полной системы вычетов по модулю n берутся наименьшие неотрицательные вычеты

Делении целых чисел a и m получается частное q и остаток r, такие что

a = m q + r, 0 r m-1. Остаток r называют ВЫЧЕТом по модулю m.

Например, для m = 3 и для m =5 получим:

a = m q + r, m = 3	a = m q + r, m = 5
0 = 3 + 0	0 = 5 + 0
1 = 3 + 1	1 = 5 + 1
2 = 3 + 2	2 = 5 + 2
3 = 3 + 0	3 = 5 + 3
4 = 3 + 1	4 = 5 + 4
5 = 3 + 2	5 = 5 + 0
6 = 3 + 0	6 = 5 + 1
7 = 3 + 1	7 = 5 + 2

Если остаток равен нулю (r=0), то говорят, что m делит a нацело ( или m кратно a), что обозначают m a , а числа q и m называют делителями a. Очевидно 1 a и a a. Если a не имеет других делителей, кроме 1 и а, то а – простое число, иначе а называют составным числом. Самый большой положительный делитель d двух чисел a и m называют наибольшим общим делителем (НОД) и обозначают d = (a,m). Если НОД (a,m)= 1, то a и m не имеют общих делителей, кроме 1, и называются взаимно простыми относительно друг друга.

Например, при m = 3:

Например, при m = 5:

Числа а тоже называют ВЫЧЕТамипо модулю m. НеотрицательныеВЫЧЕТы а = r (при q=0), принимающие значения из интервала [0, 1. m – 1], образуют полную систему наименьших вычетов по модулю m.

ВЫЧЕТы а, принимающие значения из интервала [-( ,…,( ], при нечетном m или из интервала [- при четном m образуют полную систему абсолютно наименьших ВЫЧЕТов по модулю m.

Например, при m = 5 классы наименьших вычетов образуют

Класс ВЫЧЕТов, элементы которого взаимно просты с модулем m

называют приведенным. Функция Эйлера определяет сколько ВЫЧЕТов из полной системы наименьших вычетов по модулю m взаимно просты с m. При простом m=p имеем = p-1.

Определение. Максимальный набор попарно несравнимых по модулю m чисел, взаимно простых с m, называется приведённой системой вычетов по модулю m. Всякая приведённая система вычетов по модулю m содержит элементов, где — функция Эйлера.

Решение: По определению числа образуют полную систему вычетов по модулю m, если их ровно m и они попарно несравнимы по модулюm.

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

Применим теорему о делении с остатком: a = m q + r.

13 = 6 2 + 1 13 1(mod 6); 8 = 6 1 + 2 8 2(mod 6);

-3 = 6 (-1) + 3 -3 3(mod 6); 10 = 6 1 + 4 10 4(mod 6);

35 = 6 5 + 5 35 5(mod 6); 60 = 6 10 + 0 60 0(mod 6).

Получили последовательность чисел: 1, 2, 3, 4, 5, 0, их ровно 6, повторений нет и они попарно несравнимы. То есть, они образуют полную систему вычетов по модулю m = 6.

Пример. Заменить наименьшим по абсолютной величине, а также наименьшим положительным вычетом 185 по модулю 16.

Решение. Применим теорему о делении с остатком:

185 = 16 11 + 9 185 9(mod 16).

Решение: Всякая приведённая система вычетов по модулю m содержит элементов, где — функция Эйлера. В нашем случае =4, ибо среди натуральных чисел только 1, 3, 7, 9 взаимно просты с 10 и не превосходят его. То есть, возможно, что эти четыре числа составляют искомую систему. Проверим эти числа на их попарную несравнимость:

Все числа попарно несравнимы, среди них нет повторений, их ровно 4 и они не превосходят модуль. Следовательно, они образуют приведенную систему вычетов.

Решение: В нашем случае =4, ибо среди натуральных чисел только 1, 3, 7, 9 взаимно просты с 10 и не превосходят его. То есть, возможно, что эти четыре числа составляют искомую систему. Проверим эти числа на их попарную несравнимость:

-349 = 12 (-30) + 11; -349 11(mod 12);

— 193 = 12 (-17) + 11; -193 11(mod 12);

231 = 12 19 + 3; 231 3(mod 12);

401 = 12 33 + 5; 401 5(mod 12).

КОНТРОЛЬНОЕ ЗАДАНИЕ

Задание 1. Заменить число а наименьшим по абсолютной величине, а также наименьшим положительным вычетом по модулю m.

Вариант 1. a = 185, m = 12; Вариант 2. a = 84, m = 9;

Вариант 3. a = 180, m = 10; Вариант 4. a = 82, m = 9;

Вариант 5. a = 85, m = 11; Вариант 6. a = 84, m = 8;

Вариант 7. a = 103, m = 87; Вариант 8. a = 84, m = 16;

Вариант 9. a = 15, m = 10; Вариант 10. a = 81, m = 9;

Вариант 11. a = 85, m = 15; Вариант 12. a = 74, m = 13;

Вариант 13. a = 185, m = 16; Вариант 14. a = 14, m = 9;

Вариант 15. a = 100, m = 11; Вариант 16. a = 484, m = 15;

Вариант 17. a = 153, m = 61; Вариант 18. a = 217, m = 19;

Вариант 19. a = 625, m = 25; Вариант 20. a = 624, m = 25;

Задание 3. Записать полную и приведенную систему наименьших

Источник