ИЗБРАННЫЕ ВОПРОСЫ ТЕОРИИ ЧИСЕЛ (110

Министерство образования и науки российской федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Оренбургский государственный педагогический университет»

М.И. Черемисина

ИЗБРАННЫЕ ВОПРОСЫ ТЕ О Р И И Ч И С Е Л

Учебное пособие

Оренбург

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