Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2012_2013/8mat_1213/spec/09-euclid-v3.pdf Дата изменения: Sat Feb 9 20:08:24 2013 Дата индексирования: Mon Feb 25 14:25:41 2013 Кодировка: Windows-1251 Поисковые слова: meteor

Пусть k, n целые, прич?м n > 0. На множесте Zn остатков по модулю n рассмотрим операцию ?умножения на k? [x] [kx]. Для решения некоторых сравнений нам приходилось эту операцию проводить в обратном направлении: ?делить на k?. Возникают естественные вопросы: в каких случаях можно делить, как это эффективно (без длительного перебора) делать и для чего ещ? можно вс? это применять? 1) Докажите, что при помощи умножения на k можно получить любой остаток по модулю n тогда и только тогда, когда никакой остаток нельзя ?получить дважды? (т.е. из [ka] = [kb] следует [a] = [b]). 2) Докажите, что если при помощи умножения на k можно получить любой остаток по модулю n, то операция деления на k определена однозначно (для любого остатка [c] существует единственное ?частное? [x] такое, что c k x (mod n)). 3) Докажите, что если k и n взаимно просты, то из ka kb (mod n) следует a b (mod n). (Подсказка: вы это уже доказывали. Здесь утверждение находится лишь для целостности картины.) 4) Докажите, что деление на k однозначно определено тогда и только тогда, когда k и n взаимно просты. (Не забудьте про часть ?только тогда?!) 5) Пусть d НОД k и n. Докажите, что если d | a, то не существет такого b, что kb a (mod n).
Если k и n имеют НОД, равный d > 1, а делить на k хочется, то следует сократить вс? на d и делить на k /d по модулю n/d. Если делимое не делится на d (в арифметике ВСЕХ целых чисел), то поделить его на k (по модулю n) не получится (см. 5 задачу).
Следствие. Следствие.

Занятие 9: деление по модулю и алгоритм Евклида

Гимназия 1543, математический спецкурс, 8 В

Деление по модулю

Частное (по модулю

n) при делении числа a на число k определено тогда и только тогда,

когда

до слагаемого, кратного

d = НОД(k , n) делит a. При этом частное, если существует, определено однозначно с точностью n/d.

Мы полностью ответили на вопрос: когда можно делить на k? Осталось научиться делить на k быстро. Для этого достаточно уметь находить частное [1]/[k]. Этим и занимается алгоритм, названный в честь Евклида. 6) Докажите, что для любых целых чисел b и a (a = 0) существуют и единственны такие числа q и r, что b = aq + r и 0 r < |a|. (Напомним, что q называется частным, а r остатком при делении b на a. Для r мы будем использовать обозначение b mod a.) 7) Пусть 0 < a b, d = НОД(a, b). Докажите: а) d = НОД(a, b - a); б) d = НОД(a, b mod a). 8) Пусть 0 < a b. Рассматривается последовательность пар чисел (x0, y0), (x1, y1), . . ., где (x0 , y0 ) = (a, b); (xn+1 , yn+1 ) = (yn mod xn , xn ). Докажите, что эта последовательность конечна (в некоторый момент m окажется, что xm = 0, а ym = НОД(a, b)). 9) Вычислите при помощи алгоритма Евклида: а) НОД(91, 147); б) НОД(-144, -233); в) НОД(F100, F101), где Fi числа Фибоначчи. 10) Найдите: а) НОД(232 + 1, 216 + 1); б) НОД(291 - 1, 263 - 1); в) НОД na - 1, nb - 1 . 11) Пусть [a]/[k] = [x] и [b]/[k] = [y], прич?м 0 < a < b. Пусть b = aq + (b mod a). Выразите частное [b mod a]/[k ] через x, y и q . 12) Пусть 0 < k n, k и n взаимно просты. Заметим, что [k]/[k] = [1], [n]/[k] = [0]/[k] = [0]. Рассмотрим рекуррентное соотношение (т.н. расширенный алгоритм Евклида ) (x0 , y0 , a0 , b0 ) = (k , n, [1], [0]); (xn+1 , yn+1 ) = (yn mod xn , xn ), (an+1 , bn+1 ) = ([yn mod xn ]/[k ], an ). Пусть m номер последнего элемента в этой последовательности. Чему равно bm? 13) Найдите [1]/[666] по модулю 1543.

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