Решить систему сравнений. Системы сравнений
Live Journal
Facebook
TwitterДва целых числа а и в сравнимы по модулю натурального числа m є N, если при делении на m они дают одинаковый остаток. .
Теорема (критерий сравнимости): . Следствие 1 : каждое число сравнимо по модулю m со своим остатком от деления на m: . Следствие 2: число сравнимо по модулю m, т. и т. т., к. оно делится на этот mod.
Основные свойства сравнения: 1). Относительные сравнения являются относительно эквивалентными. 2). Сравнения по одному и тому же модулю можно почленно вычитать: . Слагаемое можно переносить из одной части в другую, при этом знак меняем на противоположный. 3). В каждой части сравнения можно прибавлять любое число, кратное модулю: сравнения по одному и тому же модулю можно почленно умножать. Следствия: 1. Обе части сравнения можно возводить в любую натуральную степень. 2. Обе части сравнения можно умножать на любое натуральное число. 4). Обе части сравнения и модуль можно умножить на одно и то же число или сократить на любой их общий делитель. 5). Если сравнение имеет место по нескольким модулям то оно имеет место и по модулю, который равен их наибольшему кратному или наибольшему общему делителю
6). Если сравнение имеет место по модулю m, то оно имеет место и по любому
делителю числа m. 7). Общий делитель одной части сравнения и модуль является делителем другой части сравнения: , .
Малая теорема Ферма: если a и m – взаимнопростые числа, тогда . Функция Эйлера – это число положительных чисел, не превосходящие n и взаимнопростые с n. Если целое число a взаимнопростое с m, то . Теорема Эйлера : если целое число a взаимнопростое с m, то . Теорема Ферма: 1. Если целое число a не делит p, где р – простое, то . 2. Если р – простое и а –любое целое число, тогда . Отношение сравнимости – это классы эквивалентности. Классы эквивалентности также называются классами вычетов, а их эквивалентности называют вычетами.
Решение сравнений: Пусть , , mєN. Тогда называется сравнением к – степени с одним неизвестным и имеет не более, чем m классов решений. Решениями данного сравнения будут являться классы вычетов по модулю m. Сравнения первой степени с одной неизвестной можно записать в виде: если: 1). это сравнение не имеет решения (например 5x ). 2). Если решение этого сравнения. 3). .
Теорема: Пусть , , то , d – класов решений mod m. Методы решения сравнений: 1). Метод испытания полной системы вычетов. 2). Метод преобразования коэффициентов. Прибавляется или вычитается из правой части любое число, кратное модулю, заменяя коэффициенты в левой части на число сравнений с модулем. Можно преобразовать сравнения так, что его можно будет сократить на а и получить решение.
Определение 1. Если два числа 1) a и b при делении на p дают один и тот же остаток r , то такие числа называются равноостаточными или сравнимыми по модулю p .
Утверждение 1. Пусть p какое нибудь положительное число. Тогда всякое число a всегда и притом единственным способом может быть представлено в виде
Но эти числа можно получить задав r равным 0, 1, 2,..., p −1. Следовательно sp+r=a получит всевозможные целые значения.
Покажем, что это представление единственно. Предположим, что p можно представить двумя способами a=sp+r и a=s 1 p +r 1 . Тогда
|
 | (2) |
Так как r 1 принимает один из чисел 0,1, ..., p −1, то абсолютное значение r 1 −r меньше p . Но из (2) следует, что r 1 −r кратно p . Следовательно r 1 =r и s 1 =s .
Число r называется вычетом числа a по модулю p (другими словами, число r называется остатком от деления числа a на p ).
Утверждение 2. Если два числа a и b сравнимы по модулю p , то a−b делится на p .
Действительно. Если два числа a и b сравнимы по модулю p , то они при делении на p имеют один и тот же остаток p . Тогда
делится на p , т.к. правая часть уравнения (3) делится на p .
Утверждение 3. Если разность двух чисел делится на p , то эти числа сравнимы по модулю p .
Доказательство. Обозначим через r и r 1 остатки от деления a и b на p . Тогда
 |
Примеры 25≡39 (mod 7), −18≡14 (mod 4).
Из первого примера следует, что 25 при делении на 7 дает тот же остаток, что и 39. Действительно 25=3·7+4 (остаток 4). 39=3·7+4 (остаток 4). При рассмотрении второго примера нужно учитывать, что остаток должен быть неотрицательным числом, меньшим, чем модуль (т.е. 4). Тогда можно записать: −18=−5·4+2 (остаток 2), 14=3·4+2 (остаток 2). Следовательно −18 при делении на 4 дает остаток 2, и 14 при делении на 4 дает остаток 2.
Свойства сравнений по модулю
Свойство 1. Для любого a и p всегда
не всегда следует сравнение
где λ это наибольший общий делитель чисел m и p .
Доказательство. Пусть λ наибольший общий делитель чисел m и p . Тогда
Так как m(a−b) делится на k , то
Следовательно
и m является один из делителей числа p , то
где h=pqs.
Заметим, что можно допустить сравнения по отрицательным модулям, т.е. сравнение a≡b mod (p ) означает и в этом случае, что разность a−b делится на p . Все свойства сравнений остаются в силе и для отрицательных модулей.
Рассмотрим систему сравнений
Где f1(x), f2(x), …. , fs(x)€Z[x].
Теорема 1. Пусть M = - наименьшее общее кратное чисел m1,m2,…,ms . Если а удовлетворяет системе (2), то и любое число из класса а по модулю М удовлетворяет этой системе.
Доказательство. Пусть b€ классу а. Так как а ≡ b(mod M), то а ≡b(mod m), i= 1,2,...,s (свойство сравнений 16). Следовательно, b, как и а, удовлетворяет каждому сравнению системы, что и доказывает теорему. Поэтому естественно считать решением системы (2) класс по модулю М.
Определение. Решением системы сравнений (2) называется класс чисел по модулю М = , удовлетворяющих каждому сравнению системы.
12. Сразу заметим, что нечётные числа не удовлетворяют второму сравнению. Взяв чётные числа из полной системы вычетов по модулю 12, непосредственной проверкой убеждаемся, что 2-му сравнению удовлетворяют числа 2, -2, 6, а система имеет два решения: х ≡ 2(mod l2), х ≡ -2(mod 12).
Рассмотрим систему сравнений 1-ой степени (3)
Теорема2. Пусть d=(m1,m2), М = .
Если с1 - с2 не делится на d, то система (3) не имеет решений.
Если (c1 -c2):d, то система (3) имеет одно решение - класс по модулю М.
Доказательство. Из 1-го сравнения x = c1+m1t, t€Z. Подставляем во 2-е сравнение: с1+ m1t ≡ c2(mod m2) или
m1t ≡ c2-cl (mod m2). Это сравнение имеет решение только если (с2 – с1): d.
И решение представляет собой класс по модулю (теорема 4 из §2).
Пусть решение , то есть , где k€Z.
M== , то есть x≡c1+m1t0(mod M) - решение
Примеры.
1. :2, система имеет одно решение класс по модулю 24. Из 1-го сравнения х =2+6t. Подставив вместо х во 2-е сравнение, имеем: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1(mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, то есть x≡-4(mod 24).
2. 7-3 не делится на 3, система не имеет решений.
Следствие 1. Система сравнений (4)
Либо не имеет решений, либо имеет одно решение – класс по модулю M=.
Доказательство. Если система первых двух сравнений не имеет решений, то и (4) ие имеет решений. Если она имеет решение х ≡ a(mod), то, добавив к этому сравнению третье сравнение системы, получим снова систему вида (3), которая либо имеет одно решение, либо не имеет решений. Если имеет решение, то будем так продолжить, пока не исчерпаем все сравнения системы (4). Если решение есть, то это класс по модулю М.
Замечание. Здесь использовано свойство НОК: =.
Следствие 2 . Если m1,m2,…,ms попарно взаимно простые, то система (4) имеет одно решение - класс по модулю M=m1m2…ms.
Пример:
Так как модули попарно взаимно простые, система имеет одно решение - класс по модулю 105 = 5*3*7. Из первого сравнения
Подставляем во второе сравнение: 2 +5t≡ 0(mod 3) или 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k. Подставим в третье сравнение:
3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. тогда x=-3+15(1+7l); x=12+105l; x≡12(mod 105).
Познакомимся с другим способом решения этой системы, (Используем то, что система имеет одно решение.) Умножим обе части и модуль первого сравнения на 21, второго-на 35б третьего – на 15: из суммы первого и третьего вычтем второе:
(36 -35)х ≡ 75 + 42(modl05); x≡117(mod105); x≡12(mod105).
Рассмотрим теперь систему сравнений первой степени общего вида
Если некоторое сравнение этой системы не имеет решений, то и система не имеет решений. Если же каждое сравнение системы (5) разрешимо, то решим его относительно х и получим равносильную систему вида (4):
Где (теорема 4, §2).
По следствию 1 система либо не имеет решений, либо имеет одно решение.
Пример:
Решив каждое сравнение системы, получим равносильную систему
Эта система имеет одно решение - класс по модулю 105. Умножив первое сравнение и модуль на 3, а второе на 35, получим
Вычитая из второго сравнения первое, умноженное на 11, получаем 2х ≡-62(modl05), откуда х ≡ -31(modl05).
Задачи, сводящиеся к рассмотрению системы сравнений 1-ой степени, рассматривались в арифметике китайского математика Сун Тзу, жившего примерно в начале нашей эры. У него вопрос ставился в следующей форме- найти число, дающее заданные остатки при делении на заданные числа. Он даёт и способ решения, эквивалентный следующей теореме.
Теорема (китайская теорема об остатках). Пусть m1,m2,…,ms- попарно взаимно простые числа, М = mlm2...ms, β1, β2,…, βs подобраны так, что
Тогда решение системы
Будет иметь вид x≡x0(mod M).
Доказательство. Поскольку получим x0≡
Аналогичным образом проверяем, что x0≡c2(mod m2),…, x0≡cs(mod ms), то есть x0 удовлетворяет всем
сравнениям системы.
10. Сравнения 1-й степени. Неопределённые уравнения
§ 2. Сравнения 1-й степени. Неопределённые уравнения
Сравнение 1-ой степени может быть приведено к виду ax≡b(mod m).
Теорема 4. Если (a,m) = 1, то сравнение ах ≡b(mod m) (2) имеет единственное решение.
Доказательство. Возьмём 0,1,2,...,m-1 - полную систему вычетов по модулю m. Так как (а,m) = 1, то 0,а,2а,...,(m-1)а - тоже полная система вычетов (теорема 3, §2, гл 2.). В ней найдётся одно и только одно число, сравнимое с b по модулю m (принадлежащее тому же классу, что и b). Пусть это ах 0 , то есть ax 0 € классу b или ax 0 ≡b(mod m). x ≡x 0 (mod m) - единственное решение (2). Теорема доказана.
Теорема 5. Если (а, m)= 1, то решением сравнения ах≡b(mod m) является класс х 0 ≡a φ (m)-1 b(mod m).
Доказательство. Так как (a,m) = 1, то по т. Эйлерa а φ(m) ≡1(mod m). Легко видно, что x 0 ≡a φ (m)-1 b (mod m)- решение сравнения (2). Действительно,a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Из теоремы 4 следует, что это решение единственное.
Рассмотрим методы решений сравнения ах ≡b(mod m).
1. Метод подбора. Взяв полную систему вычетов по модулю m, выбираем числа, удовлетворяющие сравнению.
2. Использование теоремы Эйлера (теорема 5).
3. Метод преобразования коэффициентов. Надо попытаться преобразовать коэффициенты так, чтобы правую часть можно было бы разделить на коэффициент при х. Преобразования, о которых идёт речь, следующие: замена коэффициентов абсолютно наименьшими вычетами, замена числа b сравнимым по модулю числом (прибавлением числа, кратного модулю) с тем, чтобы последнее делилось на а, переход от а и b к другим, сравнимым с ними числам, у которых оказался бы общий делитель и т.п. При этом пользуемся свойствами сравнений и основанными на них теоремами о равносильных сравнениях.
1) 223x ≡ 115(mod ll).
Сначала заменим коэффициенты наименьшими по абсолютной величине вычетами: Зх ≡ 5(mod 11). Если воспользоваться теоремой
Эйлера, то
х≡3 φ(11)-1 *5=3 9 *5≡(3 3) 3 *5≡(27) 3 *5≡5 3 *5≡125*5≡4*5≡9(modll).
Однако проще преобразовать коэффициенты. Заменим сравнение равносильным, прибавив к правой части число, кратное модулю:
3x ≡ 5 + 22(mod 11). Разделив обе части на число 3, взаимно простое с модулем, получим х ≡ 9(mod l1).
2) 111x≡ 8(mod 34).
Используем метод преобразования коэффициентов.
(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16(mod 34).
Теорема 6. Если (a, m) = d и b не делится на d, то сравнение (1) не имеет решений.
Доказательство (от противного). Пусть класс x 0 - решение, то есть ax 0 ≡b (mod m) или (ax 0 -b):m, а, следовательно, (ax 0 -b):d. Но a:d, тогда иb:d - противоречие. Следовательно, сравнение не имеет решений.
Теорема 7. Если (a,m)= d, d>1, b:d, то сравнение(1) имеет d
решений, которые составляют один класс вычетов по модулю и находится по формулам
Где с удовлетворяет вспомогательному сравнению
Замечание. Согласно теореме сравнение (1) решается следующим образом.
1) Убедившись, что (a,m) = d, d> 1 и b:d, делим обе части в сравнения (2) на d и получаем вспомогательное сравнение a 1 x≡b 1 (mod m 1) , где . Сравнение имеет единственное решение. Пусть класс с – это решение.
2) Записываем ответ x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1)m 1 (mod m).
Доказательство. Вспомогательное сравнение по теореме 2(3) равносильно исходному сравнению (2). Так как ( 1, То вспомогательное сравнение имеет единственное решение – класс по модулю m 1 = . Пусть x≡c(mod m 1) – это решение. Класс чисел с по модулю m 1 распадается на d классов по модулю m: .
Действительно, любое число из класса х0 по модулю m 1 имеет вид x 0 +m 1 t. Разделим t с остатком на d: t = dq +r, где 0≤r Итак, сравнение (1) имеет d решений по модулю m: х0 , x0+m1,..., х0 +(d-1)m1.(сверху черточки горизонтальные) Примеры.
1) 20x≡ 15(mod 108). Так как (20,108) = 4 и 15 не делится на 4, то решений нет. 2) 20x≡ 44(mod 108). (20,108) = 4 и 44:4, следовательно, сравнение имеет четыре решения. Разделив обе части и модуль на 4,получим: 5х≡11(mod 27); 5 x≡11-81 ≡ -70(mod27), х ≡ -14 ≡ 13(mod 27). Тогда х≡13 + 27r(mod 108), где г= 0,1,2,3. I jj Ответ: x≡13(modl08); х ≡ 40(modl08); х ≡ 67(modl08); x≡94(modl08). Применение теории сравнений к решению неопределённых уравнении
Рассмотрим неопределённое или, как его иначе называют, Диофантово уравнение первой степени с двумя неизвестными ах + by = с, где a,b,c€Z. Требуется решить это уравнение в целых числах. Если (a,b)=d и с не делится на d, то очевидно, чТО сравнение не имеет решений в целых числах. Если же с делится на d, ТО поделим обе части уравнения на d. Поэтому достаточно рассмотреть случай, когда (а, b) =1. Так как ах отличается от с на число, кратное b, то ах ≡ c(mod b) (без ограничения общности можно считать, что b > 0). Решая это сравнение, получим х ≡x1 (mod b) или x=x1+bt, где t€Z. Для определения Соответствующих значений у имеем уравнение а(х1 + bt) + by = с, откуда Причём -целое число, оно является частным значением неизвестного y, соответствующим x1(получается, как и x1, при t=0). А общее решение уравнения примет вид систему уравнений x=x1+bt, y=y1-at, где t- любое целое число. Заметим
, что 1) уравнение ах + by = с можно было решать, начав со сравнения by ≡ c(mod а), так как by отличается от с на число, кратное а; 2)в качестве модуля удобнее выбирать наименьший из модулей
а и b. Пример
, 50x – 42y= 34. Разделим обе части уравнения на 2. 25х ≡ 17(mod2l); 4х ≡ 17 (mod 21) или 4х ≡ 17-21 ≡ -4(mod21). х ≡ -1 (mod 21), то есть x=-1+21t, t€Z. Подставим найденное х в уравнение. 25(-1 + 21t)- 21y= 17; 21у =-42 + 25* 21t и у =-2 + 25t. Введение
§1. Сравнение по модулю
§2. Свойства сравнений
§3. Система вычетов
§4. Теорема Эйлера и Ферма
Глава2. Теория сравнений с переменной
§1. Основные понятия, связанные с решением сравнений
§2. Сравнения первой степени и их решения
§3. Системы сравнений 1-ой степени с одним неизвестным
§4. Деление сравнений высших степеней
§5. Первообразные корни и индексы
Глава3. Приложение теории сравнений
§1. Признаки делимости
§2. Проверка результатов арифметических действий
§3. Обращение обыкновенной дроби в конечную
десятичную систематическую дробь
Заключение
Литература
Введение
В нашей жизни часто приходится сталкиваться с целыми числами и задачами связанными с ними. В данной дипломной работе я рассматриваю теорию сравнения целых чисел.
Два целых числа, разность которых кратна данному натуральному числу
m
называются сравнимыми по модулю
m.
Слово «модуль» происходит от латинского modulus, что по–русски означает «мера», «величина».
Утверждение «а сравнимо с b по модулю m» обычно записывают в виде a
b (mod m) и называют сравнением.
Определение сравнения было сформулировано в книге К. Гаусса «Арифметические исследования». Эту работу, написанную на латинском языке начали печатать в 1797 году, но книга вышла в свет лишь 1801 году из-за того, что процесс книгопечатания в то время был чрезвычайно трудоёмким и длительным. Первый раздел книги Гаусса так и называется: «О сравнении чисел вообще».
Сравнениями очень удобно пользоваться в тех случаях, когда достаточно знать в каких – либо исследованиях числа с точностью до кратных некоторого числа.
Например, если нас интересует, на какую цифру оканчивается куб целого числа a, то нам достаточно знать a лишь с точностью до кратных чисел 10 и можно пользоваться сравнениями по модулю 10.
Целью данной работы является рассмотрение теории сравнений и исследование основных методов решения сравнений с неизвестными, а также изучение применения теории сравнений к школьной математике.
Дипломная работа состоит из трёх глав, причём каждая глава разбита на параграфы, а параграфы на пункты.
В первой главе изложены общие вопросы теории сравнений. Здесь рассматриваются понятие сравнения по модулю, свойства сравнений, полная и приведённая система вычетов, функция Эйлера, теорема Эйлера и Ферма.
Вторая глава посвящена теории сравнений с неизвестной. В ней излагаются основные понятия, связанные с решением сравнений, рассматриваются способы решения сравнений первой степени (метод подбора, способ Эйлера, метод алгоритма Евклида, метод цепных дробей, с помощью индексов), систем сравнений первой степени с одной неизвестной, сравнений высших степеней и др.
Третья глава содержит некоторые приложения теории чисел к школьной математике. Рассмотрены признаки делимости, проверка результатов действий, обращение обыкновенных дробей в систематические десятичные дроби.
Изложение теоретического материала сопровождается большим количеством примеров, раскрывающих суть вводимых понятий и определений.
Глава1. Общие вопросы теории сравнений
§1. Сравнение по модулю
Пусть z-кольцо целых чисел, m-фиксированное целое число и m·z-множество всех целых чисел, кратных m.
Определение 1.
Два целых числа a и b называют сравнимыми по модулю m, если m делит a-b.
Если числа a и b сравнимы по модулю m, то пишут a
b (mod m).
Условие a
b (mod m) означает, что a-b делится на m.
a
b (mod m)↔(a-b)
m
Определим, что отношение сравнимости по модулю m совпадает с отношением сравнимости по модулю (-m) (делимость на m равносильно делимости на –m). Поэтому, не теряя общности, можно считать, что m>0.
Примеры.
Теорема.
(признак сравнимости дух чисел по модулю m): Два целых числа a и b сравнимы по модулю m тогда и только тогда, когда a и b имеют одинаковые остатки при делении на m.
Доказательство.
Пусть остатки при делении a и b на m равны, то есть a=mq₁+r,
(1)
B=mq₂+r,
(2)
Где 0≤r≥m.
Вычтем (2) из (1), получим a-b= m(q₁- q₂), то есть a-b
m или a
b (mod m).
Обратно, пусть a
b (mod m). Это означает, что a-b
m или a-b=mt, t
z
(3)
Разделим b на m; получим b=mq+r в (3), будем иметь a=m(q+t)+r, то есть при делении a на m получается тот же остаток, что и при делении b на m.
Примеры.
5=4·(-2)+3
23=4·5+3
24=3·8+0
10=3·3+1
Определение 2.
Два или несколько чисел, дающие при делении на m одинаковые остатки, называются равноостаточным или сравнимыми по модулю m.
Примеры.
Имеем: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², а (- m²) делится на m => наше сравнение верно.
Если числа сравнимы по модулю m, то они имеют с ним один и тот же НОД.
Имеем: 4=2·2, 10=2·5, 25=5·5
НОД(4,10) = 2, НОД(25,10) = 5, следовательно наше сравнение неверно.
§2. Свойства сравнений
Многие свойства сравнений аналогичны свойствам равенств.
а) рефлексивности: a
a (mod m) (всякое целое число
a
сравнимо с самим собой по модулю m);
В) симметричности: если a
b (mod m), то и b
a (mod m);
С) транзитивности: если a
b (mod m), а b
с (mod m), то a
с (mod m).
Доказательство.
По условию m/(a-b) и m/ (c-d). Следовательно, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c
b+d (mod m).
Примеры.
Найти остаток при делении
на 13.
Решение:
-1 (mod 13) и
1 (mod 13), тогда
(-1)+1
0 (mod 13), то есть остаток от деления
на 13 равен 0.
a-c
b-d (mod m).
Доказательство.
По условию m/(a-b) и m/(c-d). Следовательно, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c)
b-d (mod m).
Доказательство.
Пусть
a
b (mod m) и k –любое целое число. По свойству рефлексиности
k=k (mod m), а согласно свойствам 2 и 3 имеем a+k
b+k (mod m).
a·c
·d (mod m).
Доказательство.
По условию, a-b є mz, c-d є mz. Следовательно a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) є mz, то есть a·c
·d (mod m).
Следствие.
Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если а
b (mod т) и s - целое неотрицательное число, то a
s
b
s
(mod m).
Примеры.
Решение:
очевидно 13
1 (mod 3)
2
-1 (mod 3)
5
-1 (mod 3), тогда
-
·
1-1
0 (mod 13)
Ответ:
искомый остаток равен нулю, и А делится на 3.
Решение:
Докажем, что
1+
0(mod13) или 1+
0(mod 13)
1+
=1+
1+
=
Так как 27
1 (mod 13), то
1+
1+1·3+1·9
(mod 13).
ч.т.д.
3. Найдём остаток при делении с остатком числа
на 24.
Имеем:
1 (mod 24), поэтому
1 (mod 24)
Прибавляя к обеим частям сравнения по 55, получаем:
(mod 24).
Имеем:
(mod 24), поэтому
(mod 24) при любом k
є N.
Следовательно
(mod 24). Поскольку (-8)
16(mod 24), искомым остатком является 16.
2.Свойства сравнений, зависящие от модуля.
Доказательство.
Так как
a
b
(mod
т)
, то
(а - b)
т.
А так как
т
n
, то в силу транзитивности отношения делимости
(а - b
n)
, то есть
а
b
(mod n).
Пример.
Найти остаток от деления 196 на 7.
Решение:
Зная, что 196=
, можно записать 196
(mod 14). Воспользуемся предыдущим свойством, 14
7, получим
196
(mod 7), то есть 196
7.
Доказательство.
Пусть
a
b
(mod
т
) и с-целое положительное число. Тогда a-b = mt и ac-bc=mtc, или ac
bc (mod mc).
Пример.
Выяснить, является ли значение выражения
целым числом.
Решение:
Представим дроби в виде сравнений: 4
(mod 3)
1 (mod 9)
31
(mod 27)
Сложим почленно эти сравнения (свойство 2), получим 124
(mod 27) Мы видим, что 124 не делится целочисленно на 27, следовательно значение выражения
тоже не является целым числом.
Доказательство.
Если cа
cb (mod m), то есть m/c(a-b) и число
с
взаимно простое с m, (с,m)=1, то m делит a-b. Следовательно,
a
b
(mod
т
).
Пример.
60
9 (mod 17), после деления обеих частей сравнения на 3 получим:
20
(mod 17).
Делить обе части сравнения на число, не взаимно простое с модулем, вообще говоря, нельзя, так как после деления могут получиться числа, несравнимые по данному модулю.
Пример.
8
(mod 4), но 2
(mod 4).
Доказательство.
Если ka
kb
(mod km), то k (a-b) делится на km. Следовательно, a-b делится на m, то есть
a
b
(mod
т
).
Доказательство.
Пусть Р (х) = с
0
х
п
+ с
1
х
n-1
+ ... + c
n-1
x+ с
n
. По условию
a
b
(mod
т
), тогда
a
k
b
k
(mod m) при k = 0, 1, 2, …,n. Умножая обе части каждого из полученных n + 1 сравнений на c
n-k
, получим:
c
n-k
a
k
с
n-k
b
k
(mod m), где k = 0, 1, 2, …,n.
Складывая последние сравнения, получим: Р (а)
Р (b) (mod m). Если а
(mod m) и c
i
d
i
(mod m), 0 ≤ i ≤n, то
(mod m). Таким образом, в сравнении по модулю m отдельные слагаемые и множители можно заменять числами, сравнимыми по тому же модулю m.
Вместе с тем следует обратить внимание на то, что встречающиеся в сравнениях показатели степеней заменять таким образом нельзя: из
a
n
c(mod m) и n
k(mod m) не следует, что а
k
с (mod m).
Свойство 11 имеет ряд важных применений. В частности, c его помощью можно дать теоретическое обоснование признаков делимости. Для иллюстрации в качестве примера дадим вывод признака делимости на 3.
Пример.
Всякое натуральное число N можно представить в виде систематического числа: N = а
0
10
n
+ а
1
10
n-1
+ ... + а
n-1
10 + а
n
.
Рассмотрим многочлен f (х) = а
0
х
n
+ a
1
x
n-1
+ ... + а
n-1
х+а
n
. Так как
10
1 (mod 3), то по свойству 10 f (10)
f(1) (mod 3) или
N = а
0
10
n
+ а
1
10
n-1
+ ... + а
n-1
10 + а
n
а
1
+ а
2
+…+ а
n-1
+ а
n
(mod 3), т. е. для делимости N на 3 необходимо и достаточно, чтобы сумма цифр этого числа делилась на 3.
§3. Системы вычетов
Числа равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m.
Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq+r заставим q пробегать все целые числа.
Соответственно m различным значением r имеем m классов чисел по модулю m.
Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Вычет, получаемый при q=0, равный остатку r, называется наименьшим неотрицательным вычетом.
Вычет ρ, самый малый по абсолютной величине, называется абсолютно наименьшим вычетом.
Очевидно, при r имеем ρ=r; при r>
имеем ρ=r-m; наконец, если m четное и r=
, то за ρ можно принять любое из двух чисел
и
-m= -
.
Выберем из каждого класса вычетов по модулю
т
по одному числу. Получим
т
целых чисел: х
1 ,…,
х
m
.
Множество {х
1
,…, х
т
}
называют
полной системой вычетов по модулю m
.
Так как каждый класс содержит бесчисленное множество вычетов, то можно составить бесчисленное множество различных полных систем вычетов по данному модулю т, каждая из которых содержит
т
вычетов.
Пример.
Составить несколько полных систем вычетов по модулю
т
= 5. Имеем классы: 0, 1, 2, 3, 4.
0 = {... -10, -5,0, 5, 10,…}
1= {... -9, -4, 1, 6, 11,…}
Составим несколько полных систем вычетов, взяв по одному вычету из каждого класса:
0, 1, 2, 3, 4
5, 6, 2, 8, 9
10, -9, -8, -7, -6
5, -4, -3, -2, -1
и т. д.
Наиболее употребительны:
1, 2, …,m. В нашем примере: 1, 2, 3, 4, 5.
-
,…, -1, 0, 1,…,
,
а в случае четного m каким – либо из двух рядов
1, …, -1, 0, 1,…,
,
, …, -1, 0, 1, …,
.
В приведенном примере:-2, -1, 0, 1, 2.
Рассмотрим теперь основные свойства полной системы вычетов.
Теорема 1
. Любая совокупность m целых чисел:
x
l
,x
2
,…,х
m
(1)
попарно не сравнимых по модулю m, образует полную систему вычетов по модулю m.
Доказательство.
х
1
,х
2
,…,х
т
- полная система вычетов по модулю m.
Теорема 2
.
Пусть
(а,
т)
= 1, b
-
произвольное целое число; тогда если
х
1
,х
2
,…,х
т
-полная система вычетов по модулю m, то и совокупность чисел ах
1
+ b, ах
2
+ b,…, ах
m
+ b тоже полная система вычетов по модулю m.
Доказательство.
Рассмотрим
Ах
1
+ b, ах
2
+ b,…, ах
m
+ b
(2)
Действительно, если бы в (2) имелись такие два числа, что
ax
i
+b
ax
j
+ b
(mod m), (i = j), то получили бы
ax
i
ax
j
(mod т).
Так как (а,
т)
= 1, то свойству сравнений можно сократить обе части сравнения на
а
. Получаем
x
i
x
j
(mod m).
По условию же
x
i
x
j
(mod
т)
при (i = j) , так как х
1
,х
2
, ..., х
m
- полная система вычетов.
Итак, ах
1
+ b, ах
2
+ b,…, ах
m
+ b - полная система вычетов по модулю m.
Пример
.
Пусть
т
= 10,
а
= 3,
b
= 4.
Возьмем какую-нибудь полную систему вычетов по модулю 10, например: 0, 1, 2,…, 9. Составим числа вида
ах + b.
Получим: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Полученная совокупность чисел - полная система вычетов по модулю 10.
Докажем следующую теорему.
Теорема 1
.
Числа одного и того же класса вычетов по модулю m имеют с m один и тот же наибольший общий делитель: если
a
b
(mod m), то (а, m) = (b, m).
Доказательство.
Пусть
a
b
(mod m). Тогда а = b
+mt,
где t є z. Из этого равенства следует, что (а,
т)
= (b,
т).
Действительно, пусть δ-общий делитель a и m, тогда a
δ, m
δ. Так как а = b
+mt,
то b=a-mt, следовательно b
δ. Поэтому любой общий делитель чисел a и m является общим делителем m и b.
Обратно, если m
δ и b
δ, то а = b
+mt
делится на δ, a потому любой общий делитель m и b является общим делителем a и m. Теорема доказана.
Определение 1.
Наибольший общий делитель модуля
т
и любого числа
а
из данного класса вычетов по
т
называется наибольшим общим делителем
т
и этого класса вычетов.
Определение 2.
Класс вычетов
а
по модулю
т
называется взаимно простым с модулем
m
, если наибольший общий делитель
а
и
т
равен 1 (то есть если
т
и любое число из
а
взаимно просты).
Пример.
Пусть
т
= 6. Класс вычетов 2 состоит из чисел {..., -10,-4, 2, 8, 14, ...}. Наибольший общий делитель любого из этих чисел и модуля 6 равен 2. Значит, (2, 6) = 2. Наибольший общий делитель любого числа из класса 5 и модуля 6 равен 1. Значит, класс 5 взаимно прост с модулем 6.
Выберем из каждого класса вычетов, взаимно простого с модулем m, по одному числу. Получим систему вычетов, составляющую часть полной системы вычетов. Ее называют
приведенной системой вычетов по модулю m
.
Определение 3.
Совокупность вычетов по модулю m, взятых по одному из каждого взаимно простого с
т
класса вычетов по этому модулю, называется приведенной системой вычетов.
Из определения 3 следует способ получения приведенной системы вычетов по модулю
т:
надо выписать какую-либо полную систему вычетов и удалить из нее все вычеты, не взаимно простые с m. Оставшаяся совокупность вычетов - приведенная система вычетов. Приведенных систем вычетов по модулю m, очевидно, можно составить бесчисленное множество.
Если в качестве исходной взять полную систему наименьших неотрицательных или абсолютно наименьших вычетов, то указанным способом получим соответственно приведенную систему наименьших неотрицательных или абсолютно наименьших вычетов по модулю m.
Пример.
Если
т
= 8, то 1, 3, 5, 7 - приведенная система наименьших неотрицательных вычетов, 1, 3, -3,-1
- приведенная система абсолютно наименьших вычетов.
Теорема 2.
Пусть
число классов, взаимно простых с m, равно k.
Тогда любая совокупность k целых чисел
попарно несравнимых по модулю m и взаимно простых с m, представляет собой приведенную систему вычетов по модулю m.
Доказательство
А) Каждое число совокупности (1) принадлежит некоторому классу.
Следовательно, совокупность чисел
(1)
- приведенная система вычетов по модулю
т.
§4. Функция Эйлера.
Теоремы Эйлера и Ферма.
Обозначим через φ
(т)
число классов вычетов по модулю m, взаимно простых с m, то есть число элементов приведенной системы вычетов по модулю
т.
Функция φ
(т)
является числовой. Ее называют
функцией Эйлера.
Выберем в качестве представителей классов вычетов по модулю
т
числа 1, ... ,
т -
1,
т.
Тогда φ
(т)
- количество таких чисел, взаимно простых с
т.
Иными словами, φ
(т) -
количество положительных чисел, не превосходящих m и взаимно простых с m.
Примеры.
φ(12) = 4.
При
т
= 1 полная система вычетов состоит из одного класса 1. Общим натуральным делителем чисел 1 и 1 является 1, (1, 1) = 1. На этом основании полагают φ(1) = 1.
Перейдем к вычислению функции Эйлера.
1)
Если
т = р
- простое число, то φ
(р) = р-
1.
Доказательство.
Вычеты
1, 2, ... ,
р-
1
и только они взаимно просты с простым числом
р.
Поэтому φ
(р) = р -
1
.
2)
Если
т = р
к
- степень простого числа
р,
то
φ(т) =
(р -
1)
. (1)
Доказательство.
Полная система вычетов по модулю
т = р
к
состоит из чисел 1,...,
p
k
-
1,
р
к
Натуральные делители
т
являются степенями
р.
Поэтому число
а
может иметь общий делитель с m, отличный от 1
,
лишь в случае, когда
а
делится на
р.
Но среди чисел 1
, ... ,
p
k
-1
на
р
делятся лишь числа
р, 2р, ... , р
2
, ... р
к
,
количество которых равно
р
к
: р = р
к-1
.
Значит, взаимно просты с
т = р
к
остальные
р
к
- р
к-1
= p
k-l
(p-1)
чисел. Тем самым доказано, что
φ
(р
к
) = р
к-1
(р-1).
Теорема
1.
Функция Эйлера мультипликативна, то есть для взаимно простых чисел m иn имеем φ (mn) = φ(m) φ (n).
Доказательство.
Первое требование в определении мультипликативной функции выполняется тривиальным образом: функция Эйлера определена для всех натуральных чисел, причем φ
(1) = 1.
Нам надо лишь показать, что если
тип
взаимно простые числа, то
φ
(тп)
= φ
(т)
φ
(п).
(2)
Расположим полную систему вычетов по модулю
тп
в виде
п
х
т -
матрицы
1 2
т
т +
1
т +
2
2т
………………………………
(п -
1)
т+
1
(п -
1)
m +
2
пт
Поскольку
т
и
п
взаимно просты, то число
х
взаимно просто с
тп
тогда и только тогда, когда
х
взаимно просто с
т
и
х
взаимно просто с
п
. Но число
km + t
взаимно просто с
т
в том и только том случае, когда
t
взаимно просто с
т.
Поэтому числа, взаимно простые с m, располагаются в тех столбцах, для которых
t
пробегает приведенную систему вычетов по модулю
т.
Число таких столбцов равно φ
(т).
В каждом столбце представлена полная система вычетов по модулю
п.
Из этих вычетов φ
(п)
взаимно просты с
п.
Значит, общее количество чисел, взаимно простых и с
т
и с n, равно φ
(т)
φ (n
)
(φ
(т)
столбцов, в каждом из которых берется φ
(п)
чисел). Эти числа, и только они, взаимно просты с
тп.
Тем самым доказано, что
φ
(тп)
= φ
(т)
φ
(п).
Примеры.
№1
. Доказать справедливость следующих равенств
φ(4n) =
Доказательство.
№2
. Решить уравнение
Решение:
так как
(m)=
, то
=
, то есть
=600,
=75,
=3·
, тогда х-1=1, х=2,
y-1=2, y=3
Ответ: х=2, y=3
Мы можем вычислить значение функции Эйлера
(m), зная каноническое представление числа m:
m=
.
В силу мультипликативности
(m) имеем:
(m)=
.
Но по формуле (1) получаем, что
-1), и поэтому
(3)
Равенство (3) можно переписать в виде:
Поскольку
=m, то
(4)
Формула (3) или, что то же самое, (4) и является искомой.
Примеры.
№1
. Чему равна сумма
Решение:
,
,
=18
(1-
)
(1-
=18
, тогда
= 1+1+2+2+6+6=18.
№2
. На основании свойств числовой функции Эйлера доказать, что в последовательности натуральных чисел существует бесконечное множество простых чисел.
Решение:
Пологая количество простых чисел конечным множеством, допустим, что
- наибольшее простое число и пусть a=
есть произведение всех простых чисел, на основании одного из свойств числовой функции Эйлера
Так как a≥
, то a – составное число, но так как его каноническое представление содержит все простые числа, то
=1. Имеем:
=1 ,
что невозможно, и таким образом доказано, что множество простых чисел бесконечно.
№3
.Решить уравнение
, где х=
и
=2.
Решение:
Используем свойство числовой функции Эйлера,
,
и по условию
=2.
Выразим из
=2
, получим
, подставим в
:
(1+
-1=120,
=11 =>
Тогда х=
, х=11·13=143.
Ответ:
х= 143
В теории сравнений важную роль играет теорема Эйлера.
Теорема Эйлера.
Если целое число a взаимно простое с m, то
(1)
Доказательство.
Пусть
(2)
есть приведённая система вычетов по модулю m.
Если
a
-целое число, взаимно простое с m, то
(3)
Сравнение чисел по модулю
Подготовила проект: Зутикова Ирина
МАОУ «Лицей №6»
Класс: 10«а»
Научный руководитель: Желтова Ольга Николаевна
Тамбов
2016
Проблема:
Большинство учеников редко используют сравнение чисел по модулю для решений нестандартных и олимпиадных заданий.
Цель проекта:
Показать, как с помощью сравнения чисел по модулю можно решать нестандартные и олимпиадные задания.
Гипотеза:
Более глубокое изучение темы «Сравнение чисел по модулю» поможет ученикам решать некоторые нестандартные и олимпиадные задания.
Задачи проекта и план их достижения:
1.Подробно изучить тему «Сравнение чисел по модулю».
2.Решить несколько нестандартных и олимпиадных заданий, используя сравнение чисел по модулю.
3.Создать памятку для учеников на тему «Сравнение чисел по модулю».
4.Провести урок по теме «Сравнение чисел по модулю» в 10«а» классе.
5.Дать классу домашнее задание по теме «Сравнение по модулю».
6.Сравнить время выполнения задания до и после изучения темы «Сравнение по модулю».
7.Сделать выводы.
Прежде чем начать подробно изучать тему «Сравнение чисел по модулю», я решила сравнить, как она представлена в различных учебниках.
Как я выяснила, в некоторых учебниках эта тема даже не затрагивается, не смотря на углубленный уровень. А наиболее понятно и доступно тема представлена в учебнике Л.Г.Петерсона (Глава: Введение в теорию делимости), поэтому попробуем разобраться в «Сравнении чисел по модулю», опираясь на теорию из этого учебника.
Сравнения и их свойства.
Определение:
Если два целых числа a и b имеют одинаковые остатки при делении на некоторое целое число m (m>0), то говорят, что
a и b сравнимы по модулю m
, и пишут:
Теорема:
тогда и только тогда, когда разность aи bделится на m.
Свойства:
Примеры задач и их решения.
1.Найти последнюю цифру числа 3
999
.
Решение:
Т.к. последняя цифра числа - это остаток от деления на 10, то
3
999
=3
3
*3
996
=3
3
*(3
4
)
249
=7*81
249
7(mod 10)
(Т.к. 34=81 1(mod 10);81
n
1(mod10) (по свойству))
Ответ:7.
2.Доказать,что 2
4n
-1 делится на 15 без остатка. (Физтех2012)
Решение:
Т.к. 16
1(mod 15), то
16
n
-1
0(mod 15) (по свойству); 16n= (2
4
)
n
2
4n
-1
0(mod 15)
3.Доказать, что 12
2n+1
+11
n+2
делится без остатка на 133.
Решение:
12
2n+1
=12*144
n
12*11
n
(mod 133) (по свойству)
12
2n+1
+11
n+2
=12*11
n
+11
n
*121=11
n
*(12+121) =11
n
*133
Число (11
n
*133)без остатка делится на 133. Следовательно,(12
2n+1
+11
n+2
)делится без остатка на 133.
4.Найти остаток от деления на 15 числа 2
2015
.
Решение:
Т.к.16
1(mod 15), то
2
2015
8(mod 15)
Ответ:8.
5.Найти остаток от деления на 17 числа 2
2015
. (Физтех2015)
Решение:
2
2015
=2
3
*2
2012
=8*16
503
Т.к.16
-1(mod 17), то
2
2015
-8(mod 15)
8
9(mod 17)
Ответ:9.
6.Доказать, что число 11
100
-1 делится на 100 без остатка. (Физтех2015)
Решение:
11
100
=121
50
121
50
21
50
(mod 100) (по свойству)
21
50
=441
25
441
25
41
25
(mod 100) (по свойству)
41
25
=41*1681
12
1681
12
(-19)
12
(mod 100) (по свойству)
41*(-19)
12
=41*361
6
361
6
(-39)
6
(mod 100)(по свойству)
41*(-39)
6
=41*1521
3
1521
3
21
3
(mod100) (по свойству)
41*21
3
=41*21*441
441
41(mod 100) (по свойству)
21*41
2
=21*1681
1681
-19(mod 100) (по свойству)
21*(-19)=-399
399
1(mod 100) (по свойству)
Значит 11
100
1(mod 100)
11
100
-1
0(mod 100) (по свойству)
7.Даны три числа: 1771,1935,2222. Найти число, при делении на которое остатки трёх данных чисел будут равны. (ВШЭ2016)
Решение:
Пусть неизвестное нам число будет равно а,тогда
2222
1935(mod a); 1935
1771(mod a); 2222
1771(mod a)
2222-1935
0(moda) (посвойству); 1935-1771
0(moda) (по свойству); 2222-1771
0(moda) (по свойству)
287
0(mod a); 164
0(mod a); 451
0(mod a)
287-164
0(moda) (по свойству); 451-287
0(moda)(по свойству)
123
0(mod a); 164
0(mod a)
164-123
0(mod a) (посвойству)
41
- Решить систему сравнений
- Мавритания. Общие впечатления. Мавританцы Наука и культура Мавритании
- Графики линейных функций
- Сфера, вписанная в цилиндр, конус и усеченный конус
- Согласные звуки в русском языке П парный
- Воздействие частот в герцах (Гц) на организм
- Измерение времени реакции подростков и взрослых