Определение. Числа образуют полную систему вычетов по модулю , если любое целое число сравнимо по модулю с одним и только одним из этих чисел.
Любая полная система вычетов по модулю состоит из чисел, которые попарно не сравнимы по модулю .
Теорема. Пусть - полная система вычетов по модулю . Пусть - целое число, взаимно простое с . Тогда - тоже полная система вычетов по модулю .
Доказательство. Нужно доказать, что эти числа попарно не сравнимы по модулю . Предположим противное. Пусть
Так как НОД , то , что противоречит условию.
Теорема. Пусть - полная система вычетов по модулю . Пусть - целое число. Тогда - тоже полная система вычетов по модулю .
Лемма. Если , то НОД НОД .
Доказательство.
– целое число.
Отсюда . Любой общий делитель и является делителем . Отсюда НОД НОД .
Определение. Числа образуют приведенную систему вычетов по модулю , если они взаимно просты с и любое целое число, взаимно простое с , сравнимо с одним и только одним из этих чисел по модулю .
Пример. Приведенная система вычетов по модулю 10: 1,3,7,9.
Лемма. Все приведенные системы вычетов по модулю состоят из одного и того же количества чисел, которое обозначается - функция Эйлера.
Доказательство. Действительно, пусть есть две приведенные системы вычетов по модулю , состоящие из разного количества чисел:
Тогда так как числа образуют приведенную систему вычетов по модулю , то каждое из чисел сравнимо с одним и только одним из этих чисел. Поскольку , то, по принципу Дирихле, по крайней мере два числа из будут сравнимы с каким-то числом , а значит, будут сравнимы между собой по модулю . А это противоречит тому, что - приведенная система вычетов по модулю . Значит, .
Докажем теперь, что . В самом деле, числа, меньшие и взаимно простые с , образуют приведенную систему вычетов по модулю . Это следует из леммы.
Определение. Функция Эйлера (или тотиент) обозначает количество чисел, меньших и взаимно простых с .
Теорема. Если - приведенная система вычетов по модулю и - число, взаимно простое с , то - тоже приведенная система вычетов по модулю .
Если - простое, то .
Лемма. Если - простое, то .
Доказательство. Действительно, чисел, меньших простого и имеющих с ним общий делитель, всего .
Лемма. Пусть НОД . Тогда . Функция Эйлера мультипликативна.
Доказательство.
Запишем все числа от 1 до следующим образом:
Числа в каждой строке образуют полную систему вычетов по модулю . Значит, взаимно простых с среди них . При этом эти числа расположены по столбцам - друг под другом, поскольку в каждом столбце стоят числа, сравнимые по модулю .
Числа в каждом столбце образуют полную систему вычетов по модулю . Действительно, -й столбец получается, если взять числа , образующие полную систему вычетов по модулю , умножить их на число , взаимно простое с , и прибавить к каждому из них .
Таким образом, в каждом столбце ровно чисел, взаимно простых с .
Так как число будет взаимно простым с тогда и только тогда, когда оно взаимно просто с и взаимно просто с , то количество чисел, взаимно простых с , равно .
Теорема. Пусть
Каноническое разложение числа . Тогда
Доказательство. По лемме о мультипликативности функции Эйлера
Пример.
Теорема (Эйлера). Если и - взаимно простые числа, то
Пусть - какая-нибудь приведенная система вычетов по модулю . . Тогда - тоже приведенная система вычетов по модулю . Следовательно, каждое из чисел первой последовательности сравнимо с одним из чисел второй последовательности по модулю , а каждое из чисел второй последовательности сравнимо с одним из чисел первой последовательности. Тогда
Так как каждое из чисел взаимно просто с , то на них сравнение можно сократить:
Следствие. Пусть – целые числа, – натуральные. Если , , НОД , то .
Доказательство. Пусть . Так как , то – натуральное число. Тогда
Значит, .
88вопрос
Гомотетия и подобие пространства
Гомотетию с центром O и коэффициентом k обозначают H k 0
Свойства преобразований гомотетии и подобия пространства аналогичны свойствам гомотетии и подобия плоскости, поэтому изучение первых следует начинать с повторения вторых. Подобие пространства с коэффициентом k можно разложить в композицию движения и гомотетии с некоторым центром и тем же коэффициентом.
Учащиеся должны знать, что при подобном преобразовании пространства сохраняется величина угла (плоского и двугранного), параллельные (перпендикулярные) прямые и плоскости отображаются на параллельные (перпендикулярные) прямые и плоскости. Это означает, что при подобном преобразовании пространства образом любой фигуры является фигура, имеющая такую же форму, что и данная фигура, но отличающаяся от нее лишь «своими размерами».
Задача 12. Дан правильный тетраэдр РАВС ; точки Р 1 , А 1 , В 1 , С 1 - центры его граней (рис.14). Докажите, что тетраэдр Р 1 А 1 В 1 С 1 подобен тетраэдру РАВС ; найдите коэффициент этого подобия.
Решение . Пусть точки Н и K - середины ребер соответственно АВ и ВС тетраэдра РАВС , точка А 1 - центр грани РВС , точка Р 1 - центр грани АВС (рис. 14). Это означает, что
РА 1: А 1 K = АР 1: Р 1 K = 2: 1,
А 1 K : РK = Р 1 K : АK = 1: 3,
Аналогично можно доказать, что
А 1 В 1
: АВ
= 1: 3 и А 1 В 1
АВ
,
А 1 С 1
: АС
= 1: 3 и А 1 С 1
АС
,
В 1 С 1
: ВС
= 1: 3 и В 1 С 1
ВС
,
В 1 Р 1
: ВР
= 1: 3 и В 1 Р 1
ВР
,
С 1 Р 1
: СР
= 1: 3 и С 1 Р 1
СР
.
Из этих соотношений между ребрами тетраэдров РАВС
и Р 1 А 1 В 1 С 1
следует, что тетраэдр Р 1 А 1 В 1 С 1
- правильный, поэтому эти тетраэдры подобны; коэффициент подобия равен 1/3. (В профильных классах стоит доказать, что эти тетраэдры гомотетичны.)
Можно ввести определение: «Фигура F 1
называется подобной фигуре F
, если существует преобразование подобия пространства, отображающее фигуру F
на фигуру F 1
». Тогда для доказательства подобия фигуры F 1
фигуре F
достаточно найти хотя бы одно преобразование подобия, которое фигуру F
отображает на фигуру F 1
..
Определение. Параллельным переносом, или, короче, переносом фигуры, называется такое ее отображение, при котором все ее точки смещаются в одном и том же направлении на равные расстояния, т.е. при переносе каждым двум точкам X и Y фигуры сопоставляются такие точки X" и Y", что XX" = YY"
Основное свойство переноса:
Параллельный перенос сохраняет расстояния и направления, т.е. X"Y" = XY
Отсюда выходит, что параллельный перенос есть движение, сохраняющее направление и наоборот, движение, сохраняющее направление, есть параллельный перенос
Из этих утверждений также вытекает, что композиция параллельных переносов есть параллельный перенос
Параллельный перенос фигуры задается указанием одной пары соответствующих точек. Например, если указано, в какую точку A" переходит данная точка A, то этот перенос задан вектором AA", и это означает, что все точки смещаются на один и тот же вектор, т.е. XX" = AA" для всех точек Х
Центральная симметрия
Определение
Точки A и A" называются симметричными относительно точки О, если точки A, A", O лежат на одной прямой и OX = OX". Точка О считается симметричной сама себе (относительно О)
Две фигуры называются симметричными относительно точки О, если для каждой точки одной фигуры есть симметричная ей относительно точки О точка в другой фигуре и обратно
Как частный случай, фигура может быть симметрична сама себе относительно некоей точки О. Тогда эта точка О называется центром симметрии фигуры, а фигура центрально-симметричной
Определение
Центральной симметрией фигуры относительно О называется такое отображение этой фигуры, которое сопоставляет каждой ее точке точку, симметричную относительно О
Основное свойство: Центральная симметрия сохраняет расстояние, а направление изменяет на противоположное. Иначе говоря, любым двум точкам X и Y фигуры F соответствуют такие точки X" и Y", что X"Y" = -XY
Доказательство. Пусть при центральной симметрии с центром в точке О точки X и Y отобразились на X" и Y". Тогда, как ясно из определения центральной симметрии, OX" = -OX, OY" = -OY
Вместе с тем XY = OY - OX, X"Y" = OY" - OX"
Поэтому имеем: X"Y" = -OY + OX = -XY
Отсюда выходит, что центральная симметрия является движением, изменяющим направление на противоположное и наоборот, движение, изменяющее направление на противоположное, есть центральная симметрия
Центральная симметрия фигуры задается указанием одной пары существующих точек: если точка А отображается на А", то центр симметрии это середина отрезка AA"
Поворот вокруг прямой
Для более четкого представления о повороте вокруг прямой следует вспомнить поворот на плоскости около данной точки. Поворотом на плоскости около данной точки называется такое движение, при котором каждый луч, исходящий из данной точки, поворачивается на один и тот же угол в одном и том же направлении. Перейдем теперь к повороту в пространстве
Определение. Поворотом фигуры вокруг прямой a на угол (называется такое отображение, при котором в каждой плоскости, перпендикулярной прямой a, происходит поворот вокруг точки ее пересечения с прямой a на один и тот же угол (в одном и том же направлении. Прямая a называется осью поворота, а угол - углом поворота)
Отсюда видим, что поворот всегда задается осью, углом и направлением поворота
Теорема 1. Поворот вокруг прямой сохраняет расстояния, т.е. является движением
Теорема 2. Если движение пространства имеет множеством своих неподвижных точек прямую, то оно является поворотом вокруг этой прямой
Преобразования плоскости
Обычно в качестве полной системы вычетов по модулю m берутся наименьшие неотрицательные вычеты
0,1,...,m − 1или абсолютно наименьшие вычеты, состоящие из чисел
,в случае нечётного m и чисел
в случае чётного m .
См. также
Литература
- И. М. Виноградов Основы теории чисел . - М.-Л.: Гос. изд. технико-теоретической литературы, 1952. - 180 с.
Wikimedia Foundation . 2010 .
Смотреть что такое "Полная система вычетов" в других словарях:
По модулю m, любая совокупность целых чисел, содержащая по одному числу из каждого класса чисел по модулю m (два целых числа а и b принадлежат одному классу по модулю m, если а b делится на m; см. Вычет). В качестве П. с. в. чаще всего… …
По модулю т любой набор из тнесравнимых между собой по модулю тцелых чисел. Обычно в качестве П. с. в. по модулю тберутся наименьшие неотрицательные вычеты 0, 1, . . ., т 1 или абсолютно наименьшие вычеты, состоящие из чисел 0, +1, . . ., в… … Математическая энциклопедия
Часть полной системы вычетов (См. Полная система вычетов), состоящая из чисел взаимно простых с модулем m. П. с. в. содержит φ(m) чисел [φ(m) число чисел, взаимно простых с m и меньших m]. Всякие φ(m) чисел, не сравнимые по модулю m и… … Большая советская энциклопедия
Сравнение по модулю натурального числа n в теории чисел отношение эквивалентности на кольце целых чисел, связанное с делимостью на n. Факторкольцо по этому отношению называется кольцом вычетов. Совокупность соответствующих тождеств и… … Википедия
В теории чисел сравнение[уточнить] по модулю натурального числа n задаваемое означенным числом отношение эквивалентности на множестве целых чисел, связанное с делимостью на него. Факторпространство по этому отношению называется «кольцом… … Википедия
Симметрия снежинки связана с группой поворотов на угол, кратный 60° Конечная группа алгебраическая группа, содержащая конечное число элементов (это число называется её порядком). Далее группа предполагается мультипликативной, то есть операция в… … Википедия
Функция, к рая может быть представлена степенным рядом. Исключит, важность класса А. ф. определяется следующим. Во первых, этот класс достаточно ш и р о к: он охватывает большинство функций, встречающихся в основных вопросах математики и ее… … Математическая энциклопедия
I Содержание: I. Начальное народное образование вообще. II. Начальное народное образование за границей: Австро Венгрия, Англия, Бельгия, Болгария, Германия, Голландия, Дания, Испания, Италия, Норвегия, Португалия, Румыния, Сербия,… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
- — родился 26 мая 1799 г. в Москве, на Немецкой улице в доме Скворцова; умер 29 января 1837 г. в Петербурге. Со стороны отца Пушкин принадлежал к старинному дворянскому роду, происходившему, по сказанию родословных, от выходца "из… … Большая биографическая энциклопедия
Совокупность замкнутых формул логики предикатов 1 й ступени. Э. т. Th(К) класса К алгебраических систем сигнатуры наз. совокупность всех замкнутых формул логики предикатов 1 й ступени сигнатуры истинных на всех системах из класса К. Если класс… … Математическая энциклопедия
В предыдущем пункте было отмечено, что отношение m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности m (знатоки скажут – "индекс эквивалентности m ") в точности равно m .
Определение. Любое число из класса эквивалентности m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет ρ называется абсолютно наименьшим, если ⎪ρ ⎪ наименьший среди модулей вычетов данного класса.
Пример : Пусть m = 5. Тогда:
0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;
2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.
Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5.
Лемма 1 . 1) Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m .
2) Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m , то значения линейной формы а x + b , где b – любое целое число, тоже пробегают полную систему вычетов по модулю m .
Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2) Чисел а x +b ровно m штук. Покажем, что они между собой не сравнимы по модулю m . Ну пусть для некоторых различных x 1 и x 2 из полной системы вычетов оказалось, что ax 1 + b ≡ ax 2 + b (mod m). Тогда, по свойствам сравнений из предыдущего пункта, получаем:
ax 1 ≡ ax 2 (mod m )
x 1 ≡ x 2 (mod m )
– противоречие с тем, что x 1 и x 2 различны и взяты из полной системы вычетов.
Поскольку все числа из данного класса эквивалентности m получаются из одного числа данного класса прибавлением числа, кратного m , то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.
Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m .
Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит ϕ (m ) штук вычетов, где ϕ (m )– функция Эйлера – число чисел, меньших m и взаимно простых с m .
Функция Эйлера.
Функция Эйлера ϕ (a ) есть количество чисел из ряда 0, 1, 2,..., a –1, взаимно простых с a .
Лемма. Пусть
Т
огда:
в частности, φ(p α) = p α –p α -1 , φ(p ) = p –1.
Пример . Пусть m = 42. Тогда приведенная система вычетов суть:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Лемма 2. 1) Любые ϕ (m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .
2) Если d (a , m ) = 1 и x пробегает приведенную систему вычетов по модулю m , то а x так же пробегает приведенную систему вычетов по модулю m .
Доказательство . Утверждение 1) – очевидно. Докажем утверждение 2). Числа а x попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ϕ (m ) штук. Ясно также, что все они взаимно просты с модулем, ибо d (a , m )=1, d (x ,m )=1 ⇒ d (ax , m )=1. Значит, числа а x образуют приведенную систему вычетов.
Лемма 3. Пусть m 1 , m 2 , ..., m k – попарно взаимно просты и m 1 m 2 ...m k =M 1 m 1 =M 2 m 2 =...=M k m k , где M j =m 1 ...m j -1 m j +1 ...m k
1) Если x 1 , x 2 , ..., x k пробегают полные системы вычетов по модулям m 1 , m 2 , ..., m k M 1 x 1 +M 2 x 2 + ...+M k x k пробегают полную систему вычетов по модулю m= m 1 m 2 ...m k .
2) Если ξ 1 , ξ 2 , ..., ξ k пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k соответственно, то значения линейной формы M 1 ξ 1 +M 2 ξ 2 + ...+M k ξ k пробегают приведенную систему вычетов по модулю m= m 1 m 2 ...m k .
Лемма 4. Пусть x 1 , x 2 , ..., x k , x пробегают полные, а ξ 1 , ξ 2 ,..., ξ k , ξ – пробегают приведенные системы вычетов по модулям m 1 , m 2 ,...,m k и m=m 1 m 2 ...m k соответственно, где (m i m j )=1 при i ≠ j . Тогда дроби {x 1 /m 1 +x 2 /m 2 +...+x k /m k } совпадают с дробями {x/m} , а дроби { ξ 1 /m 1 + ξ 2 /m 2 +...+ ξ k /m k } совпадают с дробями { ξ/m} .
Обозначим через ε k k -ый корень m- ой степени из единицы:
Здесь k =0,1,...,m -1 – пробегает полную систему вычетов по модулю m .
Напомню, что сумма ε 0 + ε 1 +...+ ε m-1 всех корней m -ой степени из единицы равна нулю для любого m . Действительно, пусть ε 0 + ε 1 +...+ ε m-1 = a . Умножим эту сумму на ненулевое число ε 1 . Такое умножение геометрически в комплексной плоскости означает поворот правильного m -угольника, в вершинах которого расположены корни ε 0 + ε 1 +...+ ε m-1 , на ненулевой угол 2 π/m . Ясно, что при этом корень ε 0 перейдет в корень ε 1 , корень ε 1 перейдет в корень ε 2 , и т.д., а корень ε m-1 перейдет в корень ε 0 , т.е. сумма ε 0 + ε 1 +...+ ε m-1 не изменится. Имеем ε 1 a=a , откуда a=0 .
Теорема 1. Пусть m>0 – целое число, a Z , x пробегает полную систему вычетов по модулю m . Тогда, если а кратно m , то
в противном случае, при а не кратном m ,
Теорема 2. Пусть m>0 – целое число, ξ пробегает приведенную систему вычетов по модулю m . Тогда (сумма первообразных корней степени m ):
где μ(m ) – функция Мебиуса.
или же любые последовательные p числа.
Данная система называется полною системою чисел, не сравнимых по модулю p или же полною системою вычетов по модулю p . Очевидно, что всякие p последовательных чисел образуют такую систему.
Все числа, принадлежащих к одному классу, имеют много общих свойств, следовательно по отношению к модулю их можно рассматривать как одно число. Каждое число, входящее в сравнение как слагаемое или множитель, может быть заменено, без нарушения сравнения, числом, сравнимым с ним, т.е. с числом, принадлежащим к одному и тому же классу.
Другой элемент, который является общим для всех чисел данного класса, является наибольший общий делитель каждого элемента этого класса и модуля p .
Пусть a и b сравнимы по модулю p , тогда
Теорема 1. Если в ax+b вместо x подставим последовательно все p членов полной системы чисел
Поэтому все числа ax+b , где x =1,2,...p -1 не сравнимы по модулю p (в противном случае, числа 1,2,...p -1 были бы сравнимы по модулю p .
Примечания
1) В данной статье под словом число будем понимать целое число.
Литература
- 1. К.Айрленд, М.Роузен. Классическое введение в современную теорию чисел.− М:Мир, 1987.
- 2. Г.Дэвенпорт. Высшая арифметика.− М:Наука, 1965.
- 3. П.Г. Лежен Дирихле. Лекции по теории чисел. − Москва, 1936.
Полная система вычетов. Приведённая система вычетов. Наиболее употребительные системы вычетов: наименьшая положительная, наименьшая неотрицательная, абсолютно наименьшая и т.д.
Теорема 1 . Свойства полной и приведённой система вычетов.
1°.Критерий полной системы вычетов. Любая совокупность из m целых чисел, попарно не сравнимых по модулю m , образует полную систему вычетов по модулю m .
2°. Если числа x 1 , x 2 , ..., x m – полная система вычетов по модулю m , (a , m ) = 1, b – произвольное целое число, то числа ax 1 +b , ax 2 +b , ..., ax m +b также составляют полную систему вычетов по модулю m .
3°. Критерий Приведённой системы вычетов. Любая совокупность, состоящая из j(m ) целых чисел, попарно не сравнимых по модулю m и взаимно простых с модулем, образует приведённую систему вычетов по модулю m .
4°. Если числа x 1 , x 2 , ..., x j ( m ) – приведённая система вычетов по модулю m , (a , m ) = 1, то числа ax 1 , ax 2 , ..., a x j ( m ) также составляют приведённую систему вычетов по модулю m .
Теорема 2. Теорема Эйлера.
Если числа a и m взаимно простые, то a j ( m ) º 1(mod m ).
Cледствие .
1°. Теорема Ферма. Если p – простое число и a не делится на p , то a p –1 º 1(mod p ).
2°. Обобщенная теорема Ферма. Если p – простое число, то a p º a (mod p ) для любых a ÎZ .
§ 4. Решение сравнений с переменной
Решение сравнений. Равносильность. Степень сравнения.
Теорема . Свойства решений сравнений.
1°.Решениями сравнений являются целые классы вычетов.
2°. ("k )(a k º b k (mod m ))Ùk = Þ сравнения º 0 (mod m ) и º 0 (mod m ) равносильны.
3°. Если обе части сравнения умножить на число, взаимно простое с модулем, то получится сравнение, равносильное исходному.
4°. Всякое сравнение по простому модулю p равносильно сравнению, степень которого не превосходит p –1.
5°. Сравнение º 0 (mod p ), где p – простое число, имеет не более n различных решений.
6°. Теорема Вильсона. (n –1)! º –1 (mod n ) Û n простое число.
§ 5. Решение сравнений первой степени
ax º b (mod m ).
Теорема . 1°. Если (a , m ) = 1, то сравнение имеет решение, причем единственное.
2°. Если (a , m ) = d и b не делится на d , то сравнение не имеет решений.
3°. Если (a , m ) = d и b делится на d , то сравнение имеет d различных решений, которые составляют один класс вычетов по модулю .
Способы решения сравнений ax º b (mod m ) в случае, когда (a , m ) = 1:
1) подбор (перебор элементов полной системы вычетов);
2) использование теоремы Эйлера;
3) использование алгоритма Евклида;
4) вариация коэффициентов (использование свойства 2° полной системы вычетов из Теоремы 2.2);
§ 6. Неопределенные уравнения первой степени
ax +by = c .
Теорема . Уравнение ax +by = c разрешимо тогда и только тогда, когда c (a , b ).
В случае (a , b ) = 1 все решения уравнения задаются формулами
t ÎZ , где x 0 является каким-либо решением сравнения
ax º c (mod b ), y 0 = .
Диофантовы уравнения.
ГЛАВА 10. Комплексные числа
Определение системы комплексных чисел. Существование системы комплексных чисел
Определение системы комплексных чисел.
Теорема . Система комплексных чисел существует.
Модель: R 2 с операциями
(a , b )+(c , d ) = (a +c , b +d ), (a , b )×(c , d ) = (ac –bd , bc +ad ),
i = (0, 1) и отождествлением а = (а , 0).
Алгебраическая форма комплексного числа
Представление комплексного числа в виде z = a +bi , где a , b ÎR , i 2 = –1. Единственность такого представления. Re z , Im z .
Правила выполнения арифметических действий над комплексными числами в алгебраической форме.
Арифметическое n -мерное векторное пространство C n . Системы линейных уравнений, матрицы и определители над C .
Извлечение квадратных корней из комплексных чисел в алгебраической форме.