ИЗБРАННЫЕ ВОПРОСЫ ТЕОРИИ ЧИСЕЛ (110
..pdfМинистерство образования и науки российской федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Оренбургский государственный педагогический университет»
М.И. Черемисина
ИЗБРАННЫЕ ВОПРОСЫ ТЕ О Р И И Ч И С Е Л
Учебное пособие
Оренбург
2011
УДК 512
ББК 22.14 Ч 46
Рецензенты:
А. С. Ракитянский, к. ф.-м. н., доцент, зав. кафедрой алгебры и истории математики
Г. М. Гузаиров, к. ф.-м. н., доцент кафедры математического анализа и МПМ
Черемисина М.И.
Ч 46
Избранные вопросы теории чисел [Текст]: учебное пособие / М.И. Черемисина; Мин-во образования и науки РФ; Оренбург., Гос. пед. ун-т. – Оренбург: ООО «Агентство «Пресса», 2011. – с. 26.
УДК 512
ББК 22.14
© Черемисина М.И., 2011 © ООО «Агентство «Пресса», 2011
1
Предисловие
Данное учебное пособие посвящено важному разделу теории чисел: арифметическим приложениям теории сравнений. В пособии приведены основные понятия теории сравнений, свойства сравнений и их приложения к школьной математике. Из приложений рассмотрены признаки делимости, проверка результатов арифметических действий, нахождение остатков при делении на данное число, обращение обыкновенных дробей в десятичные.
Методика изложения материала позволяет использовать его на факультативных занятиях в средней школе, так как материал данного учебного пособия непосредственно примыкает к школьному курсу алгебры.
Данное пособие окажется полезным учителям, студентам высших учебных заведений и колледжей (в первую очередь – педагогических), учащимся старших классов и всем, кто интересуется теорией чисел.
Теоретический материал иллюстрируется примерами. Каждый параграф заканчивается упражнениями, позволяющими проверить усвоение изложенного материала.
2
§ 1. Сравнение по модулю
Рассмотрим множество целых чисел Z и m – произвольное целое, неравное нулю.
Определение 1. Два целых числа a и b называются сравнимыми по модулю m, если разность этих чисел делится на m .
Так как делимость на m равносильна делимости на m , то можно считать, что m 0 .
Если числа a и b сравнимы по модулю m , то пишут a b(mod m) .
Условие a b(mod m) , означает, что a b делится на m . Поэтому числа a
и b сравнимы по модулю m в том и только том случае, когда a b
делится на m. a b(mod m) (a b) m .
Примеры:
1.m 3; 8 5 (mod 3) , так как 8 5 3 и 3 делится на 3.
2.m 5;12 2(mod 5) , так как 12 2 10 и 10 делится на 5.
3. |
m 2; 3 7 (mod 2) , так как 3 7 4 и 4 делится на 2. |
4. |
m 5;11 3 (mod 5) , так как 11 3 8 , а 8 не делится на 5. |
Теорема (признак сравнимости двух чисел по модулю m ). Два целых числа a и b сравнимы по модулю m тогда и только тогда, когда a и b имеют одинаковые остатки при делении на m .
Доказательство. Пусть остатки при делении a и b на m равны, т. е.
|
|
a mq1 r |
(1) |
|
|
|
b mq 2 |
r |
(2) |
где 0 r m . Вычтем (2) |
из (1). Получим a b m(q1 q2 ) , т. е. 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 , |
0 r m . Подставив b mq r в |
3
(3), будем иметь a m(q t) r , т. е. при делении a на m получается тот же остаток, что и при делении b на m .
Пример. Определим, сравнимы ли числа 13 и 49 по модулю 6. Решение. При делении 13 и 49 на 6 получаются одинаковые остатки
r1 r2 1. Следовательно, 13 49 (mod 6) .
Определение 2. Два или несколько чисел, дающие при делении на m
одинаковые остатки, называются равноостаточными или сравнимыми по модулю m.
Отметим далее несколько часто используемых фактов:
1. Если два целых числа a и b сравнимы по модулю m , то это можно записать различными способами: a b (mod m) или a b mt , (где t целое число), или a b mt , или (a b) m .
2. Если a m , то и a 0 m или a 0 (mod m) , т. е. всякое число,
кратное m, сравнимо с нулем по модулю m .
3. Если a mq r , т. е. a при делении на m дает остаток r , то a r mq или a r (mod m) . Таким образом, всякое целое число a всегда сравнимо с остатком r , получающимся при делении его на m .
§2. Свойства сравнений
1.Свойства сравнений, не зависящие от модуля
1)Отношение a b (mod m) является отношением эквивалентности,
т. е. удовлетворяет требованиям:
а) рефлексивности: a a (mod m) (всякое целое число a сравнимо с
самим собой по модулю m );
в) симметричности: если a b (mod m), то и b a (mod m) ;
с) |
транзитивности: если |
a b (mod m) |
и b c (mod m) , то |
a c (mod m) . |
|
|
|
2) |
Сравнения по одному и |
тому же модулю можно почленно |
|
|
|
4 |
|
складывать.
3)Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого.
4)(Следствие свойств 1, 2, 3). К обеим частям сравнения можно прибавлять одно и тоже число. Действительно, пусть a b (mod m) и k
любое целое число. По свойству рефлексивности k k (mod m) , а согласно
свойствам 2 и 3 имеем: a k b k (mod m) .
Следствие. Члены сравнения можно переносить из одной части
сравнения в другую с противоположным знаком.
5) Сравнения по одному и тому же модулю можно почленно перемножать.
Следствие. Обе части сравнения можно возводить в одну и ту же
целую |
неотрицательную степень: если |
a b (mod m) и |
s целое |
неотрицательное число, то as bs (mod m) . |
|
|
|
6) |
Обе части сравнения можно умножать на одно и то же целое |
||
число. |
|
|
|
|
Свойства сравнений, зависящие от модуля |
|
|
7) |
Если a b (mod m) и m n , то a b (mod n) . |
|
|
Доказательство. Так как a b (mod m), то (a b) m . А так как m n |
|||
, то в |
силу транзитивности отношения |
делимости (a b) n , т. е. |
ab (mod n) .
8)Обе части сравнения и модуль можно умножить на одно и тоже целое положительное число. Действительно, пусть a b (mod m) и c
целое положительное число. Тогда a b mt и |
ac bc mtc , или |
|||
ac bc (mod mc) . |
|
|
|
|
|
|
|
m |
|
9) Если ak bk (mod m) |
и (k, m) d , то a b mod |
|
. |
|
|
||||
|
|
|
d |
5
Доказательство. Пусть |
k k1d , |
m m1d . |
|
Из |
ak bk (mod m) |
|||||
следует (ak bk) m , или |
(a b) k1d m1d , |
откуда |
(a b)k1 m1 . Так как |
|||||||
|
|
|
m |
|
|
|
|
m |
|
|
(k1 , m1 ) 1, то (a b) m1, или a b |
|
, т. е. a b mod |
|
. |
|
|||||
d |
|
|
||||||||
|
|
|
|
|
|
|
d |
|
||
Следствие 1. Если |
d k , |
т. е. если |
m k , то из |
ak bk (mod m) |
следует |
|
a b mod |
|
|
|
, а это означает, что обе части сравнения и модуль
k
можно разделить на любой их общий делитель. Большое значение имеет следующее следствие.
Следствие 2. Если d 1, т. е. если (k, m) 1, то из ak bk (mod m)
следует a b (mod m), а это означает, что обе части сравнения можно
разделить на их общий делитель, если он взаимно прост с модулем.
Пример. 60 9 (mod 17) . После деления обеих частей сравнения на 3
получим 20 3 (mod 17) .
Делить обе части сравнения на число, не взаимно простое с модулем, вообще говоря, нельзя, так как после деления могут получиться числа, несравнимые по данному модулю.
Пример. 8 4 (mod 4) , но 2 |
1 (mod 4) . |
|
|
|
|
|||||||
Из рассмотренных свойств сравнений вытекает следующее общее |
||||||||||||
свойство. |
|
|
|
|
|
|
|
|
|
|
|
|
10) |
Пусть P x многочлен |
с целыми коэффициентами, a и |
b |
|||||||||
переменные, |
принимающие целые значения. Тогда если a b (mod m) , то |
|||||||||||
P a P b (mod m) . |
|
|
|
|
|
|
|
|
|
|||
Доказательство. |
|
Пусть |
|
P x c xn c xn 1 ... c |
x c . |
По |
||||||
|
|
|
|
|
|
|
|
0 |
1 |
n 1 |
n |
|
условию |
a b (mod m), |
тогда |
ak bk (mod m) |
при k 0, 1, 2, ..., n . |
||||||||
Умножая |
обе части |
каждого из полученных n 1 сравнений на |
cn k , |
|||||||||
получим: |
c |
n k |
ak c |
n k |
bk (mod m) |
, где |
k 0, 1, |
2, ..., n . |
Складывая |
|||
|
|
|
|
|
|
|
|
|
|
|
||
последние сравнения, получим: |
P a P b (mod m) . Если a b (mod m) и |
6
ci di (mod m), 0 i n , то
c0an c1an 1 ... cn 1a cn d0bn d1bn 1 ... dn 1b dn (mod m) .
Таким образом, в сравнении по модулю m отдельные слагаемые и множители можно заменять числами, сравнимыми по тому же модулю m . В частности, все числа, кратные модулю, можно заменять нулями (так как,
если a m , то a 0 (mod m) ). Вместе с тем следует обратить внимание на то, что встречающиеся в сравнениях показатели степеней заменять таким
образом нельзя: из an c (mod m) и n k (mod m) не следует, что
ak c (mod m) .
Свойство 10 имеет ряд важных применений. В частности, с его помощью можно дать теоретическое обоснование признаков делимости. Для иллюстрации в качестве примера дадим вывод признака делимости на 3.
Всякое натуральное число N можно представить в виде систематического числа:
N a010n a110n 1 ... an 110 an .
Рассмотрим многочлен
f x a0 xn a1xn 1 ... an 1x an .
Так как 10 1(mod 3) , то по свойству 9:
f 10 f 1 (mod 3)
или
N a010n a110n 1 ... an 110 an a1 a2 ... an 1 an (mod 3) ,
т. е. для делимости N на 3 необходимо и достаточно, чтобы сумма цифр этого числа делилась на 3.
7
Уп р а ж н е н и я
1.Установите, сравнимы ли числа 726 и 162 по модулю 5, пользуясь: а) определением; б) признаком сравнимости чисел по модулю.
2.Запишите в виде сравнений условия:
а) числа 219 и 128 дают одинаковые остатки при делении на 7 (проверить!);
б) число 352 при делении на 31 дает остаток, равный 20; в) число 487 7 делится на 12; г) 20 – остаток от деления числа 389 на 41.
3. Запишите в виде сравнений следующие утверждения: а) число N четно;
б) число N нечетно;
в) число N имеет вид 4k 1;
г) число N имеет вид 8k 3; д) число N имеет вид 10k 3.
§ 3. Арифметические приложения теории сравнений
1. Обращение несократимой обыкновенной дроби в десятичную
|
|
Рассмотрим |
несократимую |
обыкновенную |
дробь: |
||||
|
m |
, m Z , n N , |
m , n 1. Опишем |
десятичную |
запись этой |
дроби. |
|||
|
n |
||||||||
|
|
|
|
|
|
|
|
|
|
Пусть десятичная дробь имеет вид: |
m |
a , a a |
, ...., a Z . |
|
|||||
|
|
||||||||
|
|
|
|
n |
0 1 2 |
|
i |
|
|
|
|
|
|
|
|
|
|
Мантиссой этой дроби будем называть совокупность знаков после
m
запятой и обозначать M a1a2 ....
n
|
3 |
0,15 |
|
3 |
|
15. |
Например, |
|
M |
|
|
||
|
|
|||||
|
20 |
|
|
20 |
|
|
8
Теорема 1. Если заданы дроби mn и mn1 , m, m1 Z , n N , m, n 1,
m1 , n 1, то мантиссы этих дробей равны тогда и только тогда, когда числители этих дробей сравнимы по модулю, равному их знаменателю,
m |
m |
|
|
|
|
|
mod n . |
|
|
|
|
|
||||||
т. е. M |
|
|
M |
1 |
|
m m |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|||||||||
n |
|
n |
|
|
1 |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|||||||||
Доказательство. |
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
m |
m |
|
|
|
|
m |
|
m |
|
|||||
I. Пусть M |
|
|
|
M |
1 |
|
, тогда разность дробей |
|
|
1 |
есть целое |
|||||||
|
|
|
|
|
||||||||||||||
|
|
|
|
n |
|
n |
|
|
|
n |
|
n |
|
|||||
число, т. е. |
m m1 |
Z , это означает, что m m |
n , а на языке сравнений |
|||||||||||||||
|
||||||||||||||||||
|
|
|
n |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m m1 mod n .
II. Если m m1 mod n , то по определению сравнения m m1 n ,
|
m m |
|
m |
|
m |
m |
m |
|
|||
т. е. |
1 |
|
|
|
1 |
есть целое число, т. е. M |
|
|
M |
1 |
. |
|
|
|
|||||||||
|
n |
|
n |
|
n |
n |
|
n |
|
Теорема 2. Если задана несократимая дробь mn , m, n 1 , m Z ,
n N и n, 10 1, то эта дробь при обращении в десятичную равна чистой периодической дроби, длина периода которой определяется числом k , где k – порядок числа 10 по модулю n ; т. е. наименьшее натуральное число,
удовлетворяющее условию: 10k 1 mod n .
Доказательство. Пусть дробь m удовлетворяет условиям теоремы. n
Обозначим через k – порядок числа 10 по модулю n . Пусть мантисса
|
m |
a1 a2 |
|
10 m |
|
||
дроби |
M |
|
|
a3.... Рассмотрим дробь вида |
|
, тогда |
|
|
|
||||||
|
n |
|
|
n |
|
|
10 m |
a2 |
|
102 m |
|
|
M |
|
|
a3.... Для дроби |
|
, |
|
|
n |
|||||
|
n |
|
|
|
|
102 m |
|
|
|
|
|
|
a3 |
a4 .... Рассуждая |
|
||||
M |
n |
|
||
|
|
|
|
|
10k m |
|
k |
1 mod n , |
|
|
|
|
ak 1 ak 2 .... По условию, 10 |
|
|
|
|
||||
аналогично, получим: M |
n |
|
|
||
|
|
|
|
|
9