Если мы хотим выяснить, является ли данное множество с определенной на нем бинарной операцией группой, нам следует проверить, выполняются ли сформулированные в предыдущей главе аксиомы. Давайте выясним, какие из рассмотренных далее множеств можно считать группами. Начнем с группы А (см. стр. 10).
Пример 1. Множество элементов: все целые числа (положительные, отрицательные и нуль).
Бинарная операция: сложение.
Ассоциативность: сложение чисел ассоциативно.
Единичный элемент: нуль является элементом рассматриваемого множества и для любого целого числа и выполняются равенства . Нуль является единицей группы.
Обратные элементы: если u - целое число, то , противоположное число, также является целым и таким образом, является обратным к и элементом, или, в групповых обозначениях, .
Итак, проверка показывает, что А есть группа. Так как она содержит бесконечно много элементов, то мы будем говорить, что эта группа бесконечна, и называть ее бесконечной аддитивной группой, или аддитивной группой целых чисел.
Пример 2. Рассмотрим то же множество, что и в примере 1, но теперь с операцией умножения. Читатель может убедиться, что умножение является бинарной операцией на множестве целых чисел и что для этой операции справедливы аксиома ассоциативности и аксиома о единичном элементе.
Чтобы выяснить, выполняется ли аксиома 3, попытаемся найти элемент, обратный к элементу 2. Нам нужно найги целое число и, такое, что или . Такого целого числа не существует. Следовательно, это не группа.
Пример 3. Множество состоит из двух чисел а в качестве бинарной операции возьмем умножение:
Ассоциативность: очевидно.
Единичный элемент: единицей является 1.
Обратные элементы: имеем . Таким образом, обратным к любому элементу является он сам.
Итак, это группа. Число элементов в ней конечно, и поэтому мы будем говорить, что эта группа конечна. Порядок конечной группы равен числу ее элементов. Рассматриваемая группа есть группа порядка 2.
Пример 4. Существует ли группа порядка 1? Будет ли группой множество, состоящее из одного числа 1 с умножением в качестве бинарной операции? Проверка трех аксиом показывает, что это действительно группа порядка 1.
Пример 5. Теперь рассмотрим группу, элементами которой являются движения геометрической фигуры. При изучении этой группы мы столкнемся со многими существенными особенностями таких движений. Возникающие при этом понятия будут часто встречаться в дальнейшем, и потому мы займемся этим вопросом довольно подробно. К тому же это поможет читателю заложить прочную основу для дальнейшего.
Рассмотрим движение равностороннего треугольника, который может вращаться в своей плоскости вокруг оси, проходящей через его центр. За элементы предполагаемой группы примем некоторые вращения этого треугольника, а в качестве бинарной операции - их суперпозицию, или «последовательное выполнение» (см. стр. 17).
Нас будут интересовать только те движения, в результате которых повернутый треугольник совмещается с исходным. Такие движения назовем самосовмещениями.
Чтобы дать конкретное описание самосовмещений, выберем некоторое произвольное положение нашего равностороннего треугольника на плоскости в качестве его начального положения.
Затем мы сопоставим каждой вершине некоторое число как ее опознавательную метку. Тогда наш равносторонний треугольник будет выглядеть, как это показано на рис. 3.1. Точка в центре - это точка пересечения оси вращения с плоскостью треугольника. Метки при вершинах помогут нам их узнать, когда вершины будут смещены некоторым движением из нашего множества. Нужно помнить, что для совмещения треугольника с самим собой не обязательно, чтобы каждая (помеченная) вершина совпала с собой, нужно только, чтобы множество точек, составляющих стороны треугольника после поворота, совпало с множеством точек, составляющим его стороны в начальном положении. Например, если треугольник, изображенный на рис. 3.1, будет повернут вокруг оси на 120° против часовой стрелки, то мы сможем рассматривать повернутый треугольник как второй треугольник, наложенный на треугольник, находящийся в начальном положении. Эта ситуация изображена на рис. 3.2. Цифры в скобках соответствуют расположению вершин треугольника, когда он находился в начальном положении.
Мы видим, что такое вращение связано с перестановкой вершин, а именно вершина 1 замещается вершиной 2, вершина 2 - вершиной 3, вершина 3 - вершиной 1.
Совмещение с собой в результате вращения удобно представлять себе с помощью «разделения» двух положений треугольника (см. рис. 3.3). Заметим, что угол при вершине 1 зачернен, для того чтобы легче было следить за движениями треугольника.
Рис. 3.3. Слева треугольник изображен в начальном положении, а справа - после вращения на 120° против часовой стрелки.
Хотя два положения треугольника изображены рядом, не следует забывать, что этот рисунок - лишь удобное представление такого вращения треугольника, после которого он совмещается с собой.
Существуют ли другие вращения, которые переводят треугольник из исходного положения во второе положение, изображенное выше? Конечно, таким будет вращение на 240° по часовой стрелке, равно как и вращение против часовой стрелки на 480 или 840°. Читатель может сам убедиться, что любое вращение из бесконечного множества
обладает этим свойством (вращения против часовой стрелки на отрицательный угол интерпретируются как вращения по часовой стрелке).
Все движения из множества А обладают общим свойством, а именно все они одинаковым образом объединяют в пары вершины нашего треугольника в начальном положении с вершинами того же треугольника после поворота:
Читателю следует обратить внимание на то, что вращения из множества А обладают этим свойством вне зависимости от того, какое положение треугольника мы выбрали в качестве начального.
Пусть теперь а - произвольный элемент множества А.
Рис. 3.4. Слева изображено начальное положение треугольника; справа - положение, которое принял треугольник в результате движения а.
Движение а можно рассматривать как представитель множества А в том смысле, что вращение а переводит треугольник из (произвольно) выбранного начального положения в такое положение, когда он совмещается с исходным, а вершины объединяются в пары следующим образом (рис. 3.4):
(Помните, что все движения из множества А обладают этим свойством.)
В этой ситуации нам кажется удобным обозначить через а некоторое движение из множества А. Например, можно взять в качестве а поворот на 120° против часовой стрелки. Такой выбор соответствует k = 0 в выражении Если читатель предпочтет какое-либо другое а, он может выбрать, скажем, k = 13 и запомнить, что вращение на 4800° против часовой стрелки является «его собственным» представителем множества А.
Тот или иной выбор - это лишь вопрос удобства. Существенно здесь лишь то, что все движения, входящие в множество А, объединяют вершины нашего треугольника в пары одинаковым образом, не зависящим от выбора начального положения треугольника.
Используя наши опознавательные метки обозначим это объединение в пары так:
Существуют ли другие, не входящие в множество А вращения, которые являются самосовмещениями этого треугольника? Рассмотрим множество вращений
В результате каждого из этих движений происходит наложение, изображенное на рис. 3.5. Рис. 3.6 изображает то же самое, но в «разделенной» форме.
Рис. 3.6. Слева изображен треугольник в начальном положении.
Как и выше, пусть b обозначает произвольный элемент множества В, который и будет его «представителем» Для удобства мы пометили на рисунке символом I положение, которое принял треугольник в результат движения b.
Вне зависимости от того, какое вращение мы выбрали в множестве В, мы получаем следующую группировку в пары вершин нашего треугольника:
(т. е. вершина 1 замещается вершиной 3, вершина 3 - вершиной 2 и вершина 2 - вершиной 1).
Есть еще одно множество движений, которые переводят треугольник в себя, - это множество
На рис. 3.7 символом с обозначен произвольный элемент множества С.
Рис. 3.7. Слева изображен треугольник в начальном положении.
Отметим, что результат движения с состоит в следующем: треугольник совмещается со своим исходным положением; при этом вершины группируются следующим образом:
Наша цель - получить группу движений, и, так как группа должна иметь единицу (аксиома о единичном элементе), нам следует убедиться, что любое движение с из множества С удовлетворяет требованиям, предъявляемым к единичному элементу. Действительно, если - произвольный элемент множества А, В или С, то как суперпозиция движений с и так и суперпозиция и с суть вращения из того же множества, что и х. Чтобы проверить это, вспомним, что вращения, например, из множества А - это вращения на а вращения из множества С - это вращения на ,
Если два вращения выполняются последовательно, то угол, на который окажется повернутым в результате обоих вращений треугольник, есть сумма углов, на которые поворачивается треугольник при каждом из них. Таким образом, суперпозиция вращений а и с есть поворот на угол
Так как - целые числа, то k + m - также целое число и, следовательно, суперпозиция а и с есть вращение из множества А. Аналогично, суперпозиция с и а есть вращение на из множества А.
В обозначениях группового умножения (стр. 23) это запишется так:
и результат не зависит от того, какие элементы а, b и с выбраны в качестве представителей множеств А, В и С соответственно. Эти соотношения объясняют, почему мы будем использовать символ (обозначающий единичный элемент) для произвольного элемента из множества С.
Мы перебрали все возможные вращения вокруг выбранной нами оси, являющиеся самосовмещениями данного треугольника. Каждое такое вращение содержится в одном из трех множеств A, В, С с представителями а, b, I, соответствующими положениям треугольника, изображенным (в «разделенном» виде) на рис. 3.8. Отметим, что каждое из трех положений треугольника помечено символом, обозначающим то движение треугольника, которое переводит его из заданного начального положения в изображенное на рисунке.
Мы утверждаем, что множество, состоящее из трех классов самосовмещений с представителями I, а, b, образует группу с операцией «последовательного выполнения» в качестве бинарной операции.
Чтобы проверить, что операция «последовательного выполнения» является на этом множестве бинарной операцией, и убедиться в том, что аксиомы группы выполнены, найдем произведение любых двух элементов.
Найдем, например, определяя, какая группировка вершин в пары соответствует суперпозиции вращений а и b:
Движение а связывает вершину 1 с вершиной 2 (так, как это было описано на стр. 29), а движение b - вершину 2 с вершиной 1; таким образом, в результате суперпозиции движений а и b вершина 1 объединяется в пару сама с собой. То же самое происходит и с другими вершинами. Итак,
Ясно, что
Читатель может легко убедиться в том, что (и тогда будут рассмотрены уже все произведения).
Мы установили таким образом, что суперпозиция - бинарная операция на нашем множестве. Осталось проверить лишь выполнение групповых аксиом,
Ассоциативность. Мы уже проверили (стр. 20), что операция «последовательного выполнения» ассоциативна, когда элементами множества являются движения.
Единичный элемент. Предыдущие рассуждения показывают, что множество С с представителем I есть единица.
Обратные элементы. Так как разумеется, то каждый элемент в нашем множестве обладает обратным.
Пример 6. Предположим, что нас интересуют не сами целые числа, а лишь их остатки от деления на 2; будем считать два числа эквивалентными, если они дают при делении на 2 один и тот же остаток. Два целых числа эквивалентны, если оба они четные или оба нечетные.
Тот факт, что числа 6 и 8 имеют один и тот же остаток при делении на 2, мы будем выражать записью
где означает «эквивалентно», - «по модулю». Аналогично можно написать
так как 7 и 3 дают одинаковые остатки при делении на 2. Таким образом, если через обозначить произвольное четное число, а через у - нечетное, то
Действительно, понятие «эквивалентность по модулю 2» дает нам возможность взять 0 и 1 в качестве «представителей» четных и нечетных чисел соответственно.
Мы теперь можем исследовать группу с элементами 0 и 1 и бинарной операцией «сложение по модулю 2».
Определим сложение по модулю 2 (обозначаемое через двух целых чисел а и b следующим образом.
Задания типа С6 появились в вариантах ЕГЭ в 2010 году одновременно с отменой группы А (задачи с выбором ответа). Это задание олимпиадного типа, рассчитанное на сильных учащихся, претендующих на поступление в вузы с высокими требованиями к математической подготовке.
Пример задачи С6 образца 2010 года.
Перед каждым из чисел
4, 5, …, 8 и
14, 15, …, 20 произвольным образом ставят знак плюс или минус, после чего к каждому из образовавшихся чисел первого набора прибавляют каждое из образовавшихся чисел второго набора, а затем все
35 полученных результатов складывают. Какую наименьшую по модулю и какую наибольшую сумму можно получить в итоге?
(Ответ: 1 и 805)
Критерии оценивания выполнения задания С6 образца 2010 года:
Что нужно помнить при решении задачи С6?
1. Задача С6 – относительно сложная, поскольку требует нестандартных путей решения. Однако для ее решения не нужны никакие специальные знания, выходящие за рамки школьной программы. Вполне возможно, что она окажется проще и короче решаемой, чем даже задачи С3-С5. Поэтому бояться ее не стоит.
2. В этой задаче ситуация «все или ничего» маловероятна. Продвинуться в решении на 1-2 балла из 4 на самом деле не так уж и сложно – достаточно рассмотреть самый простой частный случай или просто подобрать некоторые решения, удовлетворяющие. Например, если в приведенной выше задаче мы догадаемся, что для нахождения наибольшего значения суммы достаточно подсчитать сумму
7 Х (4 + 5 + 6 + 7 + 8) + 5 х (14 + 15 + 16 + 17 + 18 + 19 + 20),
То мы уже получим 1 балл, а если выяснить, что при любых знаках эта сумма будет нечетной, то 2.
Какие темы необходимо повторить перед решением задач С6?
1. Простые и составные числа. Наименьшее общее кратное и наибольший общий делитель. Взаимно простые числа. Деление с остатком. Алгоритм Евклида НОД(A , B ) = НОД(A , B – nA ),
Пример:
НОД (546, 658) = НОД (546, 658 - 546) = НОД (546, 112) = НОД (546 - 112 Х 4, 112) =
НОД (98, 112) = НОД (98, 112 - 98) = НОД (98, 14) = 14.
2. Признаки делимости на 2, 3, 4, 5, 6, 8, 9, 10, 11. При этом признаки делимости на 3 и на 9 желательно помнить в следующем виде: «Само число и сумма его цифр при делении на 3 (9) дают один и тот же остаток».
Пример:
Сумма цифр числа 123456789101112 равна 51, сумма цифр числа 51 равна 6. Значит, число 123456789101112 делится на 3 нацело, а при делении на 9 дает остаток 6.
3. Десятичная запись числа.
4. Арифметическая и геометрическая прогрессии.
5. Неравенство между средним арифметическим и средним геометрическим.
Для любых неотрицательных чисел выполняется неравенство
Title="{{a_1 + a_2 + ... + a_n}/n}>=root{n}{a_1 * a_2 * ... * a_n}">
Причем равенство достигается только при равенстве всех чисел . В частности:
– для любых неотрицательных чисел и выполняется неравенство title="{{a + b}/2}>=sqrt{ab}"> ;
– для любого числа title="a0"> выполняется неравенство title="delim{|}{a + {1/a}}{|}>=2"> .
Пример:
Найти наибольшее значение выражения
при положительных
Имеем:
При title="x = y = z >0">
Таким образом, данное выражение не может принимать значений, больших 1, но может принимать значение 1. Значит, наибольшее значение данного выражения равно 1.
Некоторые полезные факты, которые важно знать до начала решения задач С6.
1. Основная теорема арифметики и количество делителей.
Каждое натуральное число n>1 имеет единственное (с точностью до порядка множителей) разложение на простые множители 
, где – попарно различные простые числа, – натуральные числа. Данная форма записи называется каноническим разложением числа .
Количество натуральных делителей числа , записанного в канонической форме, равно 
.
В частности, нечетное количество натуральных делителей может иметь только точный квадрат (так как будет нечетным тогда и только тогда, когда все числа будут четными).
Пример:
Найдите все натуральные числа, которые делятся на 42 и имеют ровно 42 различных натуральных делителя, включая 1 и само число.
Если число делится на 42, то оно делится на 2, 3 и 7. Следовательно, данное число имеет вид
, где – некоторое натуральное число, не делящееся ни на 2, ни на 3, ни на 7. Значит, 
Однако число 42 можно разложить на натуральные множители, большие 1, только одним (с точностью до порядка множителей) способом:Отсюда а и – это числа 2, 3 и 7, взятые в некотором порядке.
Остается перебрать 6 вариантов и записать все возможные значения
При этом вычислять не нужно – ответ будет принят и в такой форме, а у вас будет меньше возможностей допустить ошибку.
2. Свойства квадратов целых чисел
В первую очередь нам важно знать, какие остатки могут давать квадраты целых чисел при делении на 2, 3, 4, 5, 6, 7, 8, 9, 10. Сведем все эти данные в таблицу (которую вам лучше вывести самостоятельно – это простое, но полезное упражнение).
| Остатки, которые могут получиться при делении числа вида на | Остатки, которые не могут получиться при делении числа вида на | |
|---|---|---|
| 2 | 0, 1 | – |
| 3 | 0, 1 | 2 |
| 4 | 0, 1 | 2, 3 |
| 5 | 0, 1, 4 | 2, 3 |
| 6 | 0, 1, 3, 4 | 2, 5 |
| 7 | 0, 1, 2, 4 | 3, 5, 6 |
| 8 | 0, 1, 4 | 2, 3, 5, 6, 7 |
| 9 | 0, 1, 4, 7 | 2, 3, 5, 6, 8 |
| 10 | 0, 1, 4, 5, 6, 9 | 2, 3, 7, 8 |
Пример.
Десятизначное число
на 1 больше квадрата натурального числа. Доказать, что в нем есть одинаковые цифры.
Пусть верно обратное: все 10 цифр в этом числе различны. Тогда в записи числа используются все 10 цифр от 0 до 9. Сумма этих цифр 45, следовательно, делится на 9, а точный квадрат, который на 1 меньше , при делении на 9 дает остаток 8, что невозможно. Получили противоречие. Значит, в десятичной записи числа есть одинаковые цифры.
Пример.
Решить уравнение в простых числах:
Подбором легко найти одну пару решений: Докажем, что других решений нет. Будем отталкиваться от возможных остатков, которые может давать при делении на 7. Как догадаться, что нужно рассматривать именно остатки от деления на 7? Ну так других частных решений мы подобрать не смогли, а начинать с чего-то нужно.
Давайте распишем рассуждения по пунктам.
1. Любой точный квадрат при делении на 7 дает остатки 0, 1, 2 и 4 (см. таблицу).
2. 1999 при делении на 7 дает остаток 4.
4. не делится на 7 (так как – простое число).
5. Следовательно, при делении на 7 может давать остатки 1, 2 и 4.
6. при делении на 7 может давать остатки 5, 6 и 1.
7. при делении на 7 может давать остатки 2, 4, 1 (докажите это самостоятельно).
8. Остатки при делении левой и правой частей на 7 равны друг другу, а значит, равны 1.
9.
Однако
дает остаток 1 при делении на 7, только если
т.е.
– составное число.
10.
Следовательно,
– единственное решение в простых числах.
Некоторые приемы и методы решения задач С6 будут рассмотрены в следующих номерах.
Источники для подготовки:
1. Пратусевич М.Я. и др. ЕГЭ 2011. Математика. Задача Сб. Арифметика и алгебра / Под ред. А. Л. Семенова и И. В. Ященко. – М.: МЦНМО, 2011. – 48 с.
2. Корянов А.Г. Уравнения и неравенства в целых числах (от учебных задач до олимпиадных)
3. Ященко И. В., Шестаков С. А., Захаров П. И. Подготовка к ЕГЭ по математике в 2011 году. Методические указания. – М.: МЦНМО, 2011. – 144 с.
Обозначения
$\mathbb{N}$ - множество натуральных чисел $1, 2, 3, 4, 5, 6, \ldots$
$\mathbb{Z}$ - множество целых чисел $0, \pm 1, \pm 2, \pm 3, \pm 4, \ldots$
$[x]$ - целая часть числа $x$ (наибольшее целое число, не превосходящее $x$)
$sgn(x)$ - знак числа $x$ ($sgn(0)=0$ и $sgn(x)=\frac{x}{|x|}$ при $x\neq 0$)
Делимость
Определение и свойства делимости
Пусть имеются два целых числа $a$ и $b$. Говорят, что $b$ делит $a$, если существует целое число $b_1$ такое, что $a=b\cdot b_1$. Обозначается это так $b|a$. Также в этом случае ещё говорят, что $a$ делится на $b$. Это обозначается $a\,\vdots\, b$.
Рассмотрим некоторые свойства делимости целых чисел:
Пусть $c|b$ и $b|a$. Тогда $c|a$.
Действительно, по определению имеются целые числа $b_1$ и $c_1$ такие, что $a=b\cdot b_1$ и $b=c\cdot c_1$. Но тогда $a=c\cdot c_1b_1$, то есть $c|a$.
Пусть $c|a,\ c|b$ и $k,l\in\mathbb{Z}$. Тогда $c|(ka+lb)$.
Действительно, по определению имеются целые числа $c_1$ и $c_2$ такие, что $a=c\cdot c_1$ и $b=c\cdot c_2$. Но тогда $ka+lb=c\cdot (kc_1+lc_2)$, что и требуется. Это свойство можно распространить и на произвольное количество чисел.
Пусть $k\in\mathbb{Z},k\neq 0$. Тогда $b|a$ тогда и только тогда, когда $kb|ka$.
Действительно, если $k\in\mathbb{Z},k\neq 0$, то $a=b\cdot b_1$ тогда и только тогда, когда $k\cdot a=k\cdot b\cdot b_1$, где $b_1$ – произвольное целое число.
Определение простых и составных чисел
У числа $1$ есть только один натуральный делитель - оно само. У любого натурального числа $n>1$ имеется как минимум два натуральных делителя – это $1$ и $n$. Если других натуральных делителей у числа $n$ больше нет, то оно называется простым . Примерами простых чисел являются $2,3,5,7,11,13,\ldots$
Таким образом, простые числа - это натуральные числа, имеющие ровно два натуральных делителя . Можно ввести специальную функцию $\tau(n)$, считающую количество натуральных делителей натурального числа $n$. $$\tau(n)=\sum\limits _{d|n}\;1.$$ Тогда натуральное число $n$ простое тогда и только тогда, когда $\tau(n)=2$. Натуральные числа, большие единицы, будем называть составными , если они не являются простыми.
Пример 1 . Число $4$ делится на $1,2$ и $4$, а значит $\tau(4)=3$ и это число составное. Число $17$ делится только на $1$ и $17$, а значит $\tau(17)=2$ и это число простое.
Замечание 1
. Согласно определению у составного числа $n$ имеется хотя бы один делитель $d$ с условием $1 Замечание 2
. Целые числа, делящиеся на $2$, называются чётными
, а не делящиеся на $2$ - нечётными
. Из этого определения видно, что среди чётных натуральных чисел только число $2$ является простым, а все остальные простые числа являются нечётными. общим делителем
называется целое число, делящее каждое из них. Наибольшим общим делителем
нескольких целых чисел, не все из которых равны нулю, называется наибольший из их общих делителей. Наибольший общий делитель чисел $a_1,\ldots ,a_n$ обозначается $\textrm{НОД}(a_1,\ldots ,a_n)$ или, чаще всего, просто $(a_1,\ldots ,a_n)$. Заметим, что он будет положительным, то есть натуральным числом. Пример 2
. Пусть $p$ – простое число, $a$ – натуральное. Найдём $(a,p)$. Согласно последнему замечанию достаточно найти лишь натуральные общие делители рассматриваемых чисел и среди них выбрать наибольший. Но у числа $p$ лишь два натуральных делителя – это число $1$ (которое также делит и $a$) и само $p$. Поэтому, если $p\nmid a$ ($p$ не делит $a$), то есть лишь один общий делитель, и $(a,p)=1$. Если же $p|a$, то общих делителей два – $1$ и $p$. Тогда $(a,p)=p$. Пример 3
. Пусть даны натуральные числа $a$ и $b$ и $b|a$. Тогда $(a,b)=b$. Это следует из того, что $b$ является общим делителем чисел $a$ и $b$, но при этом у $b$ не может быть делителей, больших, чем $b$. Теорема 1
. Наибольший общий делитель целых чисел $a_1,\ldots ,a_n$, не все из которых равны нулю, может быть представлен с некоторыми целыми числами $x_1,\ldots ,x_n$ в виде $$(a_1,\ldots ,a_n)=x_1a_1+\ldots +x_na_n.$$ Доказательство
. Рассмотрим множество $M=\{y_1a_1+\ldots +y_na_n>0\; |\; y_1,\ldots ,y_n\in\mathbb{Z}\}$. Оно не пусто, поскольку выбор $y_i=a_i,\ i=1,\ldots ,n$ гарантирует, что $y_1a_1+\ldots +y_na_n>0$. Так как это множество состоит из натуральных чисел, то в нём есть наименьший элемент. Пусть он равен $x_1a_1+\ldots +x_na_n$. Положим $d=(a_1,\ldots ,a_n)$. Так как $d|a_1,\ldots ,d|a_n$, то $d|(x_1a_1+\ldots +x_na_n)$, а значит $x_1a_1+\ldots +x_na_n\geqslant d$. Покажем, что $x_1a_1+\ldots +x_na_n$ является общим делителем чисел $a_1,\ldots ,a_n$, тогда по определению наибольшего общего делителя будем иметь $x_1a_1+\ldots +x_na_n\leqslant d$, и из сравнения двух полученных неравенств будет следовать $x_1a_1+\ldots +x_na_n=d$. Поделим $a_1$ на $x_1a_1+\ldots +x_na_n$ с остатком:
$$a_1=q(x_1a_1+\ldots +x_na_n)+r,\quad 0\leqslant r Следствие 1
. Для любого натурального $n\geqslant 2$ множество всех общих делителей целых чисел $a_1,\ldots ,a_n$ совпадает с множеством всех делителей числа $\textrm{НОД}(a_1,\ldots ,a_n)$. В частности, любой общий делитель нескольких целых чисел делит их наибольший общий делитель.
Доказательство
. Согласно теореме 1 существуют целые числа $x_1,\ldots ,x_n$, такие что $(a_1,\ldots ,a_n)=x_1a_1+\ldots +x_na_n$. Тогда по второму свойству делимости $(a_1,\ldots ,a_n)$ делится на любой общий делитель целых чисел $a_1,\ldots ,a_n$. При этом из первого свойства делимости следует, что любой делитель $(a_1,\ldots ,a_n)$ будет являться общим делителем чисел $a_1,\ldots ,a_n$. Таким образом, множество всех общих делителей нескольких целых чисел совпадает с множеством всех делителей их наибольшего общего делителя. Следствие 1 доказано
. Следствие 2
. Имеет место формула
$$(a_1,\ldots ,a_{n+1})=((a_1,\ldots ,a_n), a_{n+1}).$$ Доказательство
. Множество общих делителей числа $(a_1,\ldots ,a_n)$ и числа $a_{n+1}$ по следствию 1 состоит из множества всех общих делителей чисел $a_1,\ldots ,a_n$, которые одновременно делят ещё и число $a_{n+1}$. Получается, что это множество состоит из всех общих делителей чисел $a_1,\ldots ,a_{n+1}$. Но если два множества совпадают, то и наибольшие элементы этих множеств равны. Получаем $(a_1,\ldots ,a_{n+1})=((a_1,\ldots ,a_n), a_{n+1})$. Следствие 2 доказано
. Лемма 1
. Пусть $a,b,c$ – целые числа, $c|ab$ и $(a,c)=1$. Тогда $c|b$. Доказательство
. По теореме 1 найдутся целые числа $x,y$ такие, что $1=ax+cy$. Домножим обе части этого равенства на $b$, получим $b=abx+bcy$. По условию $c|ab$, а значит и $c|abx$. Очевидно, что также $c|bcy$. Из второго свойства делимости имеем $c|b$. Лемма 1 доказана
. Следствие 3
. Пусть $a,b$ – целые числа, $p$ – простое число, $p|ab$ и $p\nmid a$. Тогда $p|b$. Доказательство
. Согласно примеру 2, если $p\nmid a$, то $(a,p)=1$, так что все условия леммы 1 соблюдены. Следствие 3 доказано
. Пусть имеется несколько целых чисел. Их общим кратным
называется целое число, делящееся на каждое из них. Наименьшим общим кратным
нескольких целых чисел называется наименьшее натуральное из их общих кратных. Наименьшее общее кратное чисел $a_1,\ldots ,a_n$ обозначается $\textrm{НОК}$ или, чаще всего, просто $$. Теорема 2
. Наименьшее общее кратное целых чисел
$a_1,\ldots ,a_n$ делит любое общее кратное этих чисел
. Доказательство
. Пусть $b=$ и $c$ – произвольное общее кратное этих же чисел. Поделим $c$ на $b$ с остатком: $c=qb+r,\ 0\leqslant r С помощью сравнения совокупностей общих кратных из теоремы 2 легко выводится Следствие 4
. $$=[, a_{n+1}]. $$ Лемма 2
. Пусть $a$ и $b$ натуральные числа. Тогда $\displaystyle\left(\frac{a}{(a,b)},\frac{b}{(a,b)}\right)=1,\quad \left[\frac{a}{(a,b)},\frac{b}{(a,b)}\right]=\frac{}{(a,b)}$. Доказательство
. Пусть $d$ – наибольший общий делитель чисел $\displaystyle \frac{a}{(a,b)}$ и $\displaystyle \frac{b}{(a,b)}$. Тогда по третьему свойству делимости число $d\cdot(a,b)$ будет делить $a$ и $b$, то есть будет их общим делителем. Но так как $(a,b)$ является наибольшим из их общих делителей, то $d=1$. Пусть теперь $k$ – наименьшее общее кратное чисел $\displaystyle \frac{a}{(a,b)}$ и $\displaystyle \frac{b}{(a,b)}$. По третьему свойству делимости число $\displaystyle \frac{}{(a,b)}$ также будет их общим кратным, поэтому $k\: | \displaystyle \frac{}{(a,b)}$, а значит $k\leqslant\displaystyle \frac{}{(a,b)}$. C другой стороны, также по третьему свойству делимости, $k\cdot(a,b)$ будет делиться на $a$ и на $b$, то есть будет их общим кратным. Следовательно $\: |\: (k\cdot(a,b))$, и $\leqslant(k\cdot(a,b))$. Из двух полученных неравенств следует $k=\displaystyle \frac{}{(a,b)}$. Лемма 2 доказана
. Лемма 3
. Пусть $a$ и $b$ натуральные числа, $(a,b)=1$. Тогда $=ab$. Доказательство
. Так как $$ делится на $a$ и на $b$, то существуют натуральные числа $a_1$ и $b_1$ такие, что $$=a\cdot a_1=b\cdot b_1.$$ Значит $b|a\cdot a_1$ и $(a,b)=1$. По лемме 1 имеем $b|a_1$, но тогда $ab|aa_1=$ и следовательно $ab\leqslant $. C другой стороны $ab$ является общим кратным чисел $a$ и $b$, и по теореме 2 $|(ab)$, откуда $\leqslant ab$. Из двух полученных неравенств вытекает, что $=ab$. Лемма 3 доказана
. Следствие 5
. Пусть $a$ и $b$ натуральные числа. Тогда $(a,b)=ab$. Доказательство
. Из лемм 2 и 3 находим
$$\displaystyle\frac{}{(a,b)}=\left[\frac{a}{(a,b)},\frac{b}{(a,b)}\right]=\frac{a}{(a,b)}\cdot\frac{b}{(a,b)}.$$ Домножим левую и правую части полученного равенства на $(a,b)^2$, получится в точности требуемое равенство. Следствие 5 доказано
. Следствие 6
. Пусть $a_1,\ldots ,a_n$ натуральные числа, и $(a_i,a_j)=1$ для всех $i,j=1,\ldots ,n,\ i\neq j$. Тогда $=a_1\cdots a_n$. Доказательство
. Проведём индукцию по $n$ (покажем, что утверждение верно при $n=2$, а также, что из справедливости утверждения при произвольном $n\geqslant 2$ вытекает его справедливость и при $n+1$, тогда это будет означать, что утверждение верно при всех $n\geqslant 2$). При $n=2$ утверждение следует из леммы 3. Пусть утверждение верно для некоторого $n\geqslant 2$. По предположению индукции $=a_1\cdots a_n$. Кроме того, из следствия 3 очевидно вытекает, что
$(a_1\cdots a_n, a_{n+1})=1$ (если бы нашёлся общий простой делитель, то он делил бы одновременно $a_{n+1}$ и какое-то из $a_i, i=1,\ldots ,n$, что противоречило бы условию $(a_i,a_{n+1})=1$). Вновь из леммы 3 следует, что $[, a_{n+1}]=a_1\cdots a_n\cdot a_{n+1}$. Тогда по следствию 4 получаем
$$=[, a_{n+1}]= a_1\cdots a_n\cdot a_{n+1}. $$
Следствие 6 доказано
. Пусть для двух натуральных чисел $p$ и $q$ необходимо найти их наибольший общий делитель. Для этого применяется следующая процедура. Поделим с остатком $p$ на $q$:
$$p=a_0q+r_1,\quad 0\leqslant r_1 Заметим, что последовательность неотрицательных целых чисел $r_1,r_2,r_3,\ldots$ строго убывающая, так что при некотором $n\geqslant 0$ будет выполнено $r_{n+1}=0$, то есть
$$r_{n-2}=a_{n-1}r_{n-1}+r_n,\quad 0\leqslant r_n Теорема 1 утверждает, что с некоторыми целыми $x,y$ можно записать $r_n=(p,q)=px+qy$. Алгоритм Евклида позволяет отыскать эти числа явно. Из первого равенства имеем $r_1=p+q(-a_0)$. Из второго $r_2=q-a_1r_1=p(-a_1)+q(1+a_0a_1)$. И так далее последовательно каждое из чисел $r_1,\ldots ,r_n$ выразится в виде линейной комбинации чисел $p$ и $q$ с целыми коэффициентами. Замечание 3
. Из первого в цепочке делений с остатком равенства имеем
$$\frac{p}{q}=a_0+\frac{r_1}{q}=a_0+\frac{1}{\frac{q}{r_1}}.$$ Из второго равенства
$$\frac{q}{r_1}=a_1+\frac{r_2}{r_1}=a_1+\frac{1}{\frac{r_1}{r_2}}\ldots$$
Из последнего равенства будем иметь $$\frac{r_{n-1}}{r_n}=a_n.$$
Получается представление $\frac{p}{q}$ в виде многоэтажной дроби
$$\frac{p}{q}=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{\ldots\ +\frac{1}{a_n}}}}.$$
Такая конструкция называется цепной дробью
и обозначается $$. Подробнее о них речь пойдёт в следующих главах. Упомянем лишь, что числа $x,y$, для которых $r_n=px+qy$, могут быть найдены из равенства
$$-\frac{x}{y}=a_0+\frac{1}{a_1+\frac{1}{\ldots\ +\frac{1}{a_{n-1}}}}.$$ Пусть $p,q,r$ – целые числа и требуется найти все целые $x,y$, удовлетворяющие уравнению $px+qy=r$. Предложение 1
. Решение данного уравнения существует тогда и только тогда, когда $(p,q)|r$. Доказательство
. Если какое-либо решение $x,y$ существует, то по второму свойству делимости любой общий делитель чисел $p$ и $q$ делит $r$. В частности $(p,q)|r$. Обратно, если $(p,q)|r$, то найдётся целое число $s$ такое, что $(p,q)s=r$. По теореме 1 найдутся целые числа $x_0,y_0$ с условием $px_0+qy_0=(p,q)$, но тогда $p(x_0s)+q(y_0s)=r$. Предложение 1 доказано
. Итак, если $(p,q)\nmid r$, то решений не существует. Если же $(p,q)|r$, то имеется как минимум одно решение, скажем $x_1,y_1$. Чтобы его явно найти, можно с помощью алгоритма Евклида отыскать числа $x_0,y_0$ такие, что $px_0+qy_0=(p,q)$. Тогда, согласно предложению 1, будем иметь
$$x_1=x_0\frac{r}{(p,q)},\quad y_1= y_0\frac{r}{(p,q)}.$$
В некоторых простых случаях частное решение $x_1,y_1$ можно просто подобрать. Пусть $x,y$ – произвольное решение нашего уравнения. Тогда $px+qy=px_1+qy_1$. Поделим обе части равенства на $(p,q)$ и перегруппируем слагаемые. Получим$$\frac{p}{(p,q)}(x-x_1)=-\frac{q}{(p,q)}(y-y_1),$$ то есть $\frac{p}{(p,q)}$ делит $\frac{q}{(p,q)}(y-y_1)$, и по лемме 2 $$\left(\frac{p}{(p,q)},\frac{q}{(p,q)}\right)=1.$$ Отсюда по лемме 1 $\frac{p}{(p,q)}$ делит $(y-y_1)$, или же $y-y_1=\frac{p}{(p,q)}t$ с некоторым целым числом $t$. Но тогда, деля обе части исходного равенства на $\frac{p}{(p,q)}$, находим $x-x_1=-\frac{q}{(p,q)}t$. Получаем, что произвольное решение должно иметь вид $$x=x_1-\frac{q}{(p,q)}t, \qquad
y=y_1+\frac{p}{(p,q)}t, \quad t\in\mathbb{Z}.$$
Поскольку подстановка такой пары $x,y$ при любом $t\in\mathbb{Z}$ даёт решение рассматриваемого уравнения, то полученная формула описывает все его решения. Диофантовым называют уравнение, которое требуется решить в целых числах. Пусть $a_1,\ldots ,a_n$ и $b$ – целые числа и требуется решить диофантово уравнение $a_1x_1+\ldots +a_nx_n=b$. Положим $d=(a_1,\ldots ,a_n)$, тогда повторение рассуждений, проведённых при доказательстве предложения 1, покажет, что если $d\nmid b$, то решений нет, а если $d|b$, то есть. Найти решение можно с помощью следующей процедуры. Необходимо составить матрицу из $n+1$ строки и $n$ столбцов:
$$a_1\ a_2\ \ldots\ a_{n-1}\ a_n$$
$$ 1\quad 0\ \ldots\quad 0\quad 0$$
$$0\quad 1\ \ldots\quad 0\quad 0$$
$$\ldots\, \ldots\, \ldots\, \ldots\, \ldots $$
$$ 0\quad 0\ \ldots\quad 1\quad 0$$
$$0\quad 0\ \ldots\quad 0\quad 1$$
и с помощью трёх допустимых операций Прибавление к любому столбцу любого другого столбца, умноженного на произвольное целое число (при этом прибавляемый столбец остаётся нетронутым) Замена местами любых двух столбцов Умножение любого столбца на $-1$ привести эту матрицу к виду
$$d\hspace{2.8mm} 0\hspace{2.8mm} \ldots\ 0$$
$$ c_{11} c_{12}\ \ldots c_{1n}$$
$$c_{21} c_{22}\ \ldots c_{2n}$$
$$\ldots\ldots\ldots\ldots $$
$$c_{n1} c_{n2}\ \ldots c_{nn}$$
Добиться этого можно всегда. Например, можно сделать все элементы первой строки неотрицательными (домножая на $-1$ столбцы, в которых первый элемент отрицателен). После этого можно выбрать наименьший ненулевой элемент в первой строке, поделить остальные элементы первой строки на него с остатком и вычесть из всех столбцов столбец, в котором находится этот наименьший элемент, домноженный на подходящее целое число так, чтобы первыми элементами в столбцах оказались уже остатки от деления. В результате наименьший натуральный элемент первой строки будет уменьшаться и, так как процедуру можно продолжать неограниченное число раз, то всё большее количество элементов первой строки будет обнуляться. В итоге станут равны нулю все элементы первой строки, кроме одного, который действительно окажется равен определённому нами выше числу $d$. Это видно из того, что ни одна из трёх допустимых операций со столбцами матрицы не меняет наибольшего общего делителя всех элементов первой строки
.
Заметим также следующее свойство столбцов изначально построенной матрицы. Верхний элемент столбца равен результату подстановки стоящих под ним элементов вместо
$x_1,\ldots , x_n$ в выражение
$a_1x_1+\ldots +a_nx_n.$ Например, $a_1=a_1\cdot 1+a_2\cdot 0\ldots +a_n\cdot 0$. Это свойство также сохраняется при любой из трёх допустимых операций со столбцами матрицы
. Таким образом $$a_1\cdot c_{11}+a_2\cdot c_{21}\ldots +a_n\cdot c_{n1}=d$$ и
$$a_1\cdot c_{1j}+a_2\cdot c_{2j}\ldots +a_n\cdot c_{nj}=0,\quad j=2,\ldots ,n.$$
Значит при любых $t_2,\ldots ,t_n$ вектор
$$x_1\hspace{13mm}c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$
$$x_2\hspace{13mm}c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$
$$\cdot\hspace{3mm} =\hspace{.9mm} \frac{b}{d}\hspace{1.9mm} \cdot\hspace{2.4mm} +\hspace{2mm} t_2\hspace{1.9mm} \cdot\hspace{2.7mm} +\hspace{1.5mm}\ldots\hspace{.5mm} +\ t_n\hspace{2.3mm} \cdot$$
$$\cdot\hspace{15mm}\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$
$$x_n\hspace{12.9mm}c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.9mm}c_{nn}$$
будет являться решением уравнения $a_1x_1+\ldots +a_nx_n=b$. Теперь заметим, что мы выразили векторы
$$c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$
$$c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$
$$\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$
$$\cdot\hspace{14.5mm}\cdot\hspace{10.9mm}\ldots\hspace{10.4mm}\cdot$$
$$c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.9mm}c_{nn}$$
с помощью трёх допустимых операций в виде линейных комбинаций векторов
$$1\hspace{11mm}0\hspace{24mm}0$$
$$0\hspace{11mm}1\hspace{24mm}0$$
$$\cdot\hspace{11.2mm}\cdot\hspace{24mm}\cdot$$
$$\cdot\hspace{11.2mm}\cdot\hspace{9.1mm}\ldots\hspace{9mm}\cdot$$
$$0\hspace{11mm}0\hspace{24mm}1$$
Значит, если последовательно обратить все эти допустимые операции, то уже векторы
$$1\hspace{11mm}0\hspace{24mm}0$$
$$0\hspace{11mm}1\hspace{24mm}0$$
$$\cdot\hspace{11.2mm}\cdot\hspace{24mm}\cdot$$
$$\cdot\hspace{11.2mm}\cdot\hspace{9.1mm}\ldots\hspace{9mm}\cdot$$
$$0\hspace{11mm}0\hspace{24mm}1$$
будут выражены в виде линейных комбинаций векторов
$$c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$
$$c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$
$$\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$
$$\cdot\hspace{14.5mm}\cdot\hspace{10.9mm}\ldots\hspace{10.4mm}\cdot$$
$$c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.9mm}c_{nn}$$
Тогда, если мы имеем произвольное решение нашего уравнения, скажем вектор
$$x_1\hspace{13mm}1\hspace{11mm}0\hspace{24mm}0$$
$$x_2\hspace{13mm}0\hspace{11mm}1\hspace{24mm}0$$
$$\cdot\hspace{4.5mm} =\hspace{0.4mm} x_1\hspace{0.2mm} \cdot\hspace{1.4mm} +\hspace{1mm} x_2\hspace{0.2mm} \cdot\hspace{1.3mm} +\hspace{1.0mm}\ldots\hspace{.5mm} +\ x_n\hspace{0.2mm} \cdot$$
$$\cdot\hspace{14.7mm}\cdot\hspace{11.5mm}\cdot\hspace{24mm}\cdot$$
$$x_n\hspace{13mm}0\hspace{11mm}0\hspace{23.8mm}1,$$
то он выразится с некоторыми целыми коэффициентами $t_1,t_2,\ldots ,t_n$ в виде
$$x_1\hspace{13mm}c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$
$$x_2\hspace{13mm}c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$
$$\cdot\hspace{3mm} =\hspace{.9mm} t_1\hspace{1.9mm} \cdot\hspace{2.4mm} +\hspace{2mm} t_2\hspace{1.9mm} \cdot\hspace{2.7mm} +\hspace{1.5mm}\ldots\hspace{.5mm} +\ t_n\hspace{2.3mm} \cdot$$
$$\cdot\hspace{15mm}\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$
$$x_n\hspace{12.9mm}c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.9mm}c_{nn}$$
Подставив же полученный вектор в уравнение, получим $a_1x_1+\ldots +a_nx_n=t_1\cdot d=b.$ Откуда $t_1=\frac{b}{d}.$ Итак, мы доказали, что все решения нашего уравнения и только они имеют вид
$$x_1\hspace{13mm}c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$
$$x_2\hspace{13mm}c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$
$$\cdot\hspace{3mm} =\hspace{.9mm} \frac{b}{d}\hspace{1.9mm} \cdot\hspace{2.4mm} +\hspace{2mm} t_2\hspace{1.9mm} \cdot\hspace{2.7mm} +\hspace{1.5mm}\ldots\hspace{.5mm} +\ t_n\hspace{2.3mm} \cdot$$
$$\cdot\hspace{15mm}\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$
$$x_n\hspace{12.9mm}c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.7mm}c_{nn},$$
где $t_2,\ldots ,t_n$ принимают произвольные целые значения. Лемма 4
. Пусть $n>1$ натуральное число. Тогда у него есть простой делитель. Доказательство
. Рассмотрим наименьший превышающий единицу делитель числа $n$. Обозначим его через $p$. Если это число составное, то, согласно замечанию 1, существует число $d$ такое, что $d|p$ и $1 Следствие 7
. Пусть $n>1$ натуральное число. Тогда оно представляется в виде произведения простых чисел (некоторые из которых могут совпадать). Доказательство
. По лемме 4 у числа $n$ есть простой делитель, скажем $p_1$. Если $\frac{n}{p_1}>1$, то у этого числа тоже найдётся простой делитель, скажем $p_2$ (при этом допускается и случай $p_2=p_1$). Если и $\frac{n}{p_1p_2}>1$, то у этого числа также найдётся простой делитель, скажем $p_3$. Поскольку последовательность натуральных чисел $n,\frac{n}{p_1},\frac{n}{p_1p_2},\frac{n}{p_1p_2p_3},\ldots $ строго убывает, то за конечное число шагов (гарантированно не более $n-1$ шага) в этой последовательности возникнет наименьшее натуральное число, то есть $1$. Значит, с некоторым $k$ будем иметь $n=p_1\cdot p_2\cdots p_k$, что и требовалось. Следствие 7 доказано
. Следствие 8
. Пусть $n>1$ натуральное число. Тогда оно является простым, если у него нет простых делителей, не превосходящих $[\sqrt{n}]$. Доказательство
. Предположим, что у $n$ нет простых делителей, не превосходящих $[\sqrt{n}]$. Покажем, что у него тогда не может быть и простых делителей, больших чем $[\sqrt{n}]$, кроме него самого. Пусть $p|n,\ [\sqrt{n}]+1\leqslant p Теорема 3
. Простых чисел бесконечно много. Доказательство
. Предположим, у нас имеется несколько простых чисел $p_1, p_2,\ldots ,p_k$. Рассмотрим число $N=p_1\cdot p_2\cdots p_k+1$. Это число не делится ни на одно из имеющихся простых чисел, так как остаток от деления $N$ на любое из них равен $1$. Вместе с тем, по лемме 4, у числа $N$ должен быть хотя бы один простой делитель. Следовательно, помимо чисел $p_1, p_2,\ldots ,p_k$ существуют и другие простые числа. Поскольку по доказанному мы можем к любой совокупности простых чисел всегда добавить ещё хотя бы одно простое число, то простых чисел бесконечно много. Теорема 3 доказана
. На основе результата леммы 4 возникает следующий алгоритм нахождения всех простых чисел, не превышающих некоторого числа $n$, если известны все простые числа, скажем $p_1,p_2,\ldots ,p_k$, не превосходящие $\sqrt{n}$. Этот алгоритм именуется решетом Эратосфена
. Для осуществления алгоритма нужно выписать все числа от $2$ до $n$ включительно. После этого нужно для каждого $i=1,2,\ldots ,k$ вычеркнуть числа $2p_i, 3p_i,\ldots ,\left[\frac{n}{p_i}\right] p_i$. Тогда все невычеркнутые числа и составят список всех простых, не превышающих $n$. Действительно, пусть число $m\leqslant n$ не вычеркнуто. Тогда либо это одно из простых, не превосходящих $\sqrt{n}$, либо оно не делится ни на одно из этих простых. В последнем случае $m$ не делится ни на одно из простых, не превосходящих $\sqrt{m}$, так как $\sqrt{m}\leqslant \sqrt{n}$, поэтому по следствию 8 число $m$ – простое. Очевидно, что каждое простое число, не превосходящее $n$, попадёт в список невычеркнутых, так как оно либо не превосходит $\sqrt{n}$ и не вычеркнуто по условию алгоритма, либо оно больше $\sqrt{n}$ и тогда оно не вычеркнуто, так как по определению не делится на отличные от себя простые числа. Теорема 4
(основная теорема арифметики). Пусть $n>1$ натуральное число. Тогда $n$ раскладывается в произведение простых чисел, причём единственным образом с точностью до перестановки сомножителей. Доказательство
. Существование разложения показано в следствии 7. Докажем, что разложение единственно. Пусть $n$ – наименьшее из чисел, которые раскладываются в произведение простых более чем одним способом, и два из его разложений имеют вид
$$p_1\cdot p_2\cdots p_k=q_1\cdot q_2\cdots q_l.$$
Ни одно из чисел $p_1, p_2,\ldots ,p_k$ не равно ни одному из чисел $q_1, q_2,\ldots ,q_l$, так как в противном случае обе части равенства можно было бы сократить на совпадающие простые, и число $n$ было бы не наименьшим из чисел, которые раскладываются в произведение простых более чем одним способом. Поэтому можно считать, что $p_1 Замечание 4
. Разложение числа на простые множители, согласно основной теореме арифметики, единственно с точностью до порядка сомножителей. Один способ упорядочивания сомножителей является общепринятым и называется каноническим
. Он подразумевает упорядочивание сомножителей по возрастанию, при этом равные сомножители объединяются в единый множитель в виде простого числа в некоторой степени. В общем виде это выглядит так:
$$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k},\quad p_1 $\nu_p(m\cdot n)=\nu_p(m)+\nu_p(n)$ $\nu_p(m+n)\geqslant\min\{\nu_p(m),\nu_p(n)\}$, причём, если $\nu_p(m)>\nu_p(n)$, то $\nu_p(m+n)=\nu_p(n)$ Пусть $f$ – функция натурального аргумента, принимающая действительные (или даже комплексные) значения. Тогда $f$ называется мультипликативной
, если $f(m\cdot n)=f(m)\cdot f(n)$ при $(m,n)=1$. Очень важно запомнить, что достаточно, чтобы второе свойство выполнялось только при взаимной простоте чисел $m$ и $n$. Функция $f$ называется вполне мультипликативной
, если $f$ принимает не только нулевые значения; $f(m\cdot n)=f(m)\cdot f(n)$ при любых $m,n$. Из определения следует, что если $f$ – мультипликативная функция, то $f(1)=1$. Действительно,
$$f(1)=f(1\cdot 1)=f(1)\cdot f(1).$$ Отсюда либо $f(1)=0$, либо $f(1)=1$. Но если $f(1)=0$, то для любого натурального $n$ имеем $f(n)=f(n\cdot 1)=f(n)\cdot f(1)=0$, то есть $f$ принимает только нулевые значения, что противоречит определению мультипликативной функции. Значит, $f(1)=1$. Предложение 2
. Пусть $f,g$ – мультипликативные функции. Тогда для любого натурального числа $n$
$$\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right)=\prod_{p|n}\left(f(1)\cdot g(p^{\nu_p(n)})+f(p)\cdot g(p^{\nu_p(n)-1})+\ldots +f(p^{\nu_p(n)-1})\cdot g(p)+f(p^{\nu_p(n)})\cdot g(1)\right).$$ Здесь в левой части равенства стоит сумма по всем различным натуральным
делителям числа $n$, а справа стоит произведение по всем различным
простым делителям числа $n$, $\nu_p(n)$ – показатель, определённый после доказательства основной теоремы арифметики. Например, при $n=12$ данное равенство выглядит так:
$$f(1)\cdot g(12)+f(2)\cdot g(6)+f(3)\cdot g(4)+f(4)\cdot g(3)+f(6)\cdot g(2)+f(12)\cdot g(1)=$$
$$=\big(f(1)\cdot g(4)+f(2)\cdot g(2)+f(4)\cdot g(1)\big)\cdot\big(f(1)\cdot g(3)+f(3)\cdot g(1)\big).$$ Доказательство
. Пусть $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$. Тогда
$$\prod_{p|n}\left(f(1)\cdot g(p^{\nu_p(n)})+f(p)\cdot g(p^{\nu_p(n)-1})+\ldots +f(p^{\nu_p(n)-1})\cdot g(p)+f(p^{\nu_p(n)})\cdot g(1)\right)=$$
$$=\prod_{i=1}^k\left(\sum_{\beta_i=0}^{\alpha_i}f(p_i^{\beta_i})\cdot g(p_i^{\alpha_i-\beta_i})\right)=\sum_{\beta_1=0}^{\alpha_1}\ldots\sum_{\beta_k=0}^{\alpha_k}f(p_1^{\beta_1})\cdot g(p_1^{\alpha_1-\beta_1})\cdots f(p_k^{\beta_k})\cdot g(p_k^{\alpha_k-\beta_k}).$$
Воспользуемся мультипликативностью функций $f$ и $g$. Тогда полученное выражение запишется в виде
$$\sum_{\beta_1=0}^{\alpha_1}\ldots\sum_{\beta_k=0}^{\alpha_k}f(p_1^{\beta_1}\cdots p_k^{\beta_k})\cdot g(p_1^{\alpha_1-\beta_1}\cdots p_k^{\alpha_k-\beta_k})=\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right).$$
Последнее равенство выполняется потому, что $d$ является делителем $n$ тогда и только тогда, когда $d=p_1^{\beta_1}\cdots p_k^{\beta_k}$ и $0\leqslant\beta_i\leqslant\alpha_i$ для каждого $i=1,\ldots ,k$. Предложение 2 доказано
. По двум заданным функциям $f$ и $g$ натурального аргумента всегда можно построить третью функцию, которую мы будем обозначать $f\circ g$, определяемую для каждого натурального числа $n$ так:
$$f\circ g(n)=\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right).$$
Эта функция называется свёрткой Дирихле
функций $f$ и $g$. Следствие 9
. Если функции $f$ и $g$ мультипликативны, то мультипликативна и их свёртка Дирихле. Доказательство
. Пусть $(m,n)=1$. Это значит, что данные числа раскладываются в произведения простых так, что ни одно простое из разложения одного числа не встречается в разложении другого. Пусть $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k},\ m=p_{k+1}^{\alpha_{k+1}}\cdots p_{k+l}^{\alpha_{k+l}}$. Тогда по предложению 2
$$f\circ g(m\cdot n)=\sum_{d|m\cdot n}f(d)\cdot g\left(\frac{m\cdot n}{d}\right)=\prod_{i=1}^{k+l}\left(\sum_{\beta_i=0}^{\alpha_i}f(p_i^{\beta_i})\cdot g(p_i^{\alpha_i-\beta_i})\right)=$$
$$=\prod_{i=1}^{k}\left(\sum_{\beta_i=0}^{\alpha_i}f(p_i^{\beta_i})\cdot g(p_i^{\alpha_i-\beta_i})\right)\prod_{i=k+1}^{k+l}\left(\sum_{\beta_i=0}^{\alpha_i}f(p_i^{\beta_i})\cdot g(p_i^{\alpha_i-\beta_i})\right)=$$
$$=\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right)\cdot\sum_{d|m}f(d)\cdot g\left(\frac{m}{d}\right)=f\circ g(m)\cdot f\circ g(n).$$
Следствие 9 доказано
. Теорема 5
. Множество всех мультипликативных функций образует абелеву группу относительно операции свёртки Дирихле. Доказательство
. По следствию 9 свёртка Дирихле двух мультипликативных функций есть также мультипликативная функция. Заметим, что
$$f\circ g(n)=\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right)=\sum_{d_1\cdot d_2=n}f(d_1)\cdot g(d_2)=\sum_{d_2\cdot d_1=n}g(d_2)\cdot f(d_1)=g\circ f(n),$$
то есть свёртка Дирихле коммутативна.
Аналогично доказывается ассоциативность свёртки Дирихле:
$$f\circ \big(g\circ h\big)(n)=\sum_{d_1\cdot d"=n}f(d_1)\cdot\big(g\circ h\big)(d")=
\sum_{d_1\cdot d"=n}f(d_1)\cdot\left(\sum_{d_2\cdot d_3=d"}g(d_2)\cdot h(d_3)\right)=$$
$$=\sum_{d_1\cdot d_2\cdot d_3=n}f(d_1)\cdot g(d_2)\cdot h(d_3)=\sum_{d\cdot d_3=n}\left(\sum_{d_1\cdot d_2=d}f(d_1)\cdot g(d_2)\right)\cdot h(d_3)=\big(f\circ g\big)\circ h(n).$$
Определим функцию $\varepsilon(n)$ так, что $\varepsilon(1)=1$ и $\varepsilon(n)=0$ при всех $n>1$.
Тогда очевидно, что $\varepsilon(n)$ мультипликативна, и для любой функции $f$
$$f\circ\varepsilon=\varepsilon\circ f=f.$$
Осталось показать, что для любой мультипликативной функции $f$ существует мультипликативная функция $f"$ такая, что
$$f\circ f"=\varepsilon.$$
Поскольку $f\circ f"(1)=f(1)\cdot f"(1)=1\cdot 1=1=\varepsilon(1)$, то благодаря мультипликативности достаточно, чтобы для любого простого числа $p$ для каждого $i=1,2,\ldots$ выполнялось
$$f\circ f"(p^i)=f(1)\cdot f"(p^i)+f(p)\cdot f"(p^{i-1})+\ldots +f(p^{i-1})\cdot f"(p)+f(p^i)\cdot f"(1)=0=\varepsilon(p^i).$$
Ясно как подобрать функцию $f"$. Нужно задать $f"(p)$ так, чтобы выписанное равенство выполнялось при $i=1$. После этого нужно задать $f"(p^2)$ так, чтобы равенство выполнялось при $i=2$. Продолжая эту процедуру, можно задать (причём единственным образом) значение функции $f"$ на $p^i$ при любом $i$. Теорема 5 доказана
. В доказательстве теоремы 5 уже появился первый пример мультипликативной (и даже вполне мультипликативной) функции - это нейтральный элемент группы мультипликативных функций - функция $\varepsilon(n)$. Функции $\textrm{id}(n)=n$ и ${\bf 1}(n)=1$, очевидно, тоже (вполне) мультипликативны. Рассмотрим функцию $\tau(n)$, которая подсчитывает количество различных натуральных делителей числа $n$. Имеем
$$\tau(n)=\sum_{d|n}1=\sum_{d|n}{\bf 1}(d)\cdot {\bf 1}\left(\frac{n}{d}\right)={\bf 1}\circ{\bf 1}(n).$$
Теперь по следствию 9 функция $\tau(n)$ мультипликативна. Легко увидеть, что
$$\tau(p_1^{\alpha_1}\cdots p_k^{\alpha_k})=(\alpha_1+1)\cdots(\alpha_k+1).$$ Для функции $\sigma(n)$, которая подсчитывает сумму различных натуральных делителей числа $n$, находим
$$\sigma(n)=\sum_{d|n}d=\sum_{d|n}\textrm{id}(d)\cdot {\bf 1}\left(\frac{n}{d}\right)=\textrm{id}\circ{\bf 1}(n).$$
Отсюда по следствию 9 функция $\sigma(n)$ также мультипликативна. При этом
$$\sigma(p_1^{\alpha_1}\cdots p_k^{\alpha_k})=(1+p_1+p_1^2+\ldots +p_1^{\alpha_1})\cdots(1+p_k+p_k^2+\ldots +p_k^{\alpha_k})=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdots\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$ Функция Мёбиуса $\mu(n)$ определяется так: $\mu(n)=0$, если $m^2|n$ при некотором $m>1$; $\mu(n)=(-1)^k$, если $n$ есть произведение первых степеней $k$ различных простых чисел. Её мультипликативность следует из определения. Действительно, пусть $p^2|m$ или $p^2|n$. Тогда $\mu(m\cdot n)=0=\mu(m)\cdot\mu(n)$. Если же $(m,n)=1,\ m=q_1\cdots q_l,\ n=p_1\cdots p_k$, то
$\mu(m\cdot n)=(-1)^{l+k}=(-1)^{l}\cdot (-1)^{k}=\mu(m)\cdot\mu(n)$. При этом $\mu(n)$ не является вполне мультипликативной, так как при простом $p$ имеем $\mu (p\cdot p)=0$, но $\mu(p)\cdot\mu (p)=(-1)\cdot (-1)=1$. Пользуясь предложением 2, можно заметить, что
$$\mu\circ {\bf 1}(n)=\prod_{p|n}(\mu(1)+\mu(p)+\mu(p^2)+\ldots+\mu(p^{\nu_p(n)}))=\prod_{p|n}(1-1+0+\ldots +0)=\varepsilon(n).$$
Так что функция Мёбиуса является обратной функцией к тождественной единице ${\bf 1}(n)$ относительно операции свёртки Дирихле. Также заметим, что
$$\mu\circ\textrm{id}(n)=\prod_{p|n}(\mu(1)\cdot p^{\nu_p(n)}+\mu(p)\cdot p^{\nu_p(n)-1}+\mu(p^2)\cdot p^{\nu_p(n)-2}+\ldots+\mu(p^{\nu_p(n)})\cdot 1)=\prod_{p|n}(p^{\nu_p(n)}-p^{\nu_p(n)-1}).$$ Из равенства $\mu\circ {\bf 1}=\varepsilon$ и ассоциативности свёртки Дирихле вытекает знаменитая формула обращения Мёбиуса
:
$$f=g\circ {\bf 1}\Longleftrightarrow g=f\circ\mu .$$ Пример 4
. Какая функция получится в результате свёртки Дирихле функции Мёбиуса с функцией суммы делителей? Мы уже показали, что $\sigma=\textrm{id}\circ{\bf 1}$. По формуле обращения Мёбиуса находим $\textrm{id}=\sigma\circ\mu$, то есть $\sum_{d|n}\sigma(d)\cdot\mu\left(\frac{n}{d}\right)=n$. Аналогично из $\tau={\bf 1}\circ{\bf 1}$ получаем ${\bf 1}=\tau\circ\mu$, то есть $\sum_{d|n}\tau(d)\cdot\mu\left(\frac{n}{d}\right)=1$. Функция Эйлера $\varphi (n) $ подсчитывает количество натуральных чисел, не превосходящих $n$ и взаимно простых с $n$. Например, среди чисел от $1$ до $6$ только числа $1$ и $5$ взаимно просты с числом $6$, поэтому $\varphi (6)=2$. Для функции Эйлера можно найти следующее представление.
$$\varphi (n) =\sum_{1\leqslant k\leqslant n, (k, n)=1} 1=\sum_{k=1}^n\varepsilon ((k, n))=\sum_{k=1}^n\mu\circ {\bf 1} ((k, n))=$$
$$=\sum_{k=1}^n\sum_{d|(k, n)}\mu(d)=\sum_{d|n}\mu(d)\sum_{1\leqslant k\leqslant n,\ k\,\vdots\, d}1=\sum_{d|n}\mu(d)\frac {n}{d}=\mu\circ\textrm {id}(n). $$
По предложению 2, таким образом, функция $\varphi (n) $ мультипликативна. Здесь при перемене местами двух сумм мы воспользовались следующим соображением: если $d|(k, n)$, то $d|k$ и $d|n$. Так как $k$ меняется от $1$ до $n$, то $d$ пробежит все натуральные делители числа $n $, причём некоторые, возможно, по несколько раз. Каждое конкретное $d$ встречается столько раз, сколько найдётся чисел $k$, делящихся на это $d$. А их будет ровно $\frac{n}{d}$. Из равенства $\varphi=\mu\circ\textrm {id} $ по формуле обращения Мёбиуса находим $\textrm {id}=\varphi\circ {\bf 1} $, то есть $\sum_{d|n}\varphi(d)=n$. Покажем явную формулу для функции Эйлера. Имеем
$$\varphi (n) =\mu\circ\textrm {id}(n)=\prod_{p|n}(p^{\nu_p(n)}-p^{\nu_p(n)-1}). $$
Последнее равенство доказано выше в разделе про функцию Мёбиуса. Поясним отдельно эту формулу в двух простых случаях. Пусть $p$ – простое число. Тогда среди чисел $1,\ldots ,p$ с ним взаимно просты все, кроме него самого. Получаем $\varphi(p)=p-1$. Среди же чисел $1,\ldots ,p^{\alpha}$ взаимно просты с $p^{\alpha}$ будут все, кроме тех, что делятся на $p$. А таких чисел ровно $p^{\alpha-1}$. Следовательно, $\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1}$. Иногда в формуле для функции Эйлера избегают использования показателя $\nu_p(n)$. Заметим, что
$$\varphi (n) =\prod_{p|n}(p^{\nu_p(n)}-p^{\nu_p(n)-1})=\prod_{p|n}p^{\nu_p(n)}\cdot\left(1-\frac{1}{p}\right)=n\cdot\prod_{p|n}\left(1-\frac{1}{p}\right).$$
Последнее равенство справедливо, так как $\prod_{p|n}p^{\nu_p(n)}=n$. Замечание 5
. Равенство $\varphi\circ {\bf 1}=\textrm {id} $ можно получить самостоятельно из очень простых соображений, если уже установлена мультипликативность функции Эйлера. Воспользуемся предложением 2:
$$\sum_{d|n}\varphi(d)=\prod_{p|n}(\varphi(1)+\varphi(p)+\varphi(p^2)+\ldots +\varphi(p^{\nu_p(n)}))
=\prod_{p|n}(1+p-1+p^2-p+\ldots +p^{\nu_p(n)}-p^{\nu_p(n)-1})=\prod_{p|n}p^{\nu_p(n)}=n.$$ Полученная выше формула для функции Эйлера может быть доказана и с помощью формулы включений и исключений. Сформулируем последнюю. Пусть имеется $N$ объектов, которые могут обладать (или нет) свойствами $ a_1,\ldots , a_k $. Будем обозначать через $N (a_{i_1},\ldots ,a_{i_j}) $ количество тех из наших $N $ объектов, что обладают каждым из свойств $a_{i_1},\ldots ,a_{i_j},\ 1\leqslant i_1,\ldots , i_j\leqslant k$ (но при этом, возможно, и какими-то ещё свойствами). За $ N_0^{(k)}$ обозначим количество тех из наших $N $ объектов, которые не обладают ни одним из свойств $a_1,\ldots ,a_k$. Теорема 6
(формула включений и исключений).
$$N_0^{(k)}=N-N(a_1)-N(a_2)-\ldots - N(a_k)+N(a_1,a_2)+N(a_1,a_3)+\ldots +N(a_{k-1},a_k)-$$
$$-N(a_1,a_2,a_3)-\ldots -N(a_{k-2},a_{k-1},a_k)+\ldots +(-1)^k\cdot N(a_1,\ldots ,a_k).$$ Доказательство
. Проведём индукцию по $k$ (если мы покажем, что утверждение верно при $k=1$, а также, что из справедливости утверждения при произвольном натуральном $k$ следует его справедливость и при $k+1$, то утверждение будет справедливо при всех натуральных $k$). При $k=1$ утверждается, что количество объектов, не обладающих свойством $a_1$, есть количество всех объектов за вычетом количества объектов, которые обладают этим свойством:
$$N_0^{(1)}=N-N(a_1).$$
Это очевидно. Пусть для некоторого $k\geqslant 1$ утверждение теоремы верно и пусть имеется ещё одно свойство $a_{k+1}$. Пусть $M$ – это количество всех тех из наших $N$ объектов, которые обладают свойством $a_{k+1}$. Обозначим через $M (a_{i_1},\ldots ,a_{i_j})$ количество тех из только что выделенных $M$ объектов, что обладают каждым из свойств $a_{i_1},\ldots ,a_{i_j},\ 1\leqslant i_1,\ldots , i_j\leqslant k$. За $M_0$ обозначим количество тех из этих же $M$ объектов, которые не обладают ни одним из свойств $a_1,\ldots ,a_k$. Заметим, что, вообще говоря, $M=N(a_{k+1})$ и $M (a_{i_1},\ldots ,a_{i_j})=N(a_{i_1},\ldots ,a_{i_j},a_{k+1})$.
Запишем формулу включений и исключений для этих выделенных $M$ объектов:
$$M_0=M-M(a_1)-\ldots - M(a_k)+M(a_1,a_2)+\ldots +M(a_{k-1},a_k)+\ldots +(-1)^k\cdot M(a_1,\ldots ,a_k).$$
Очевидно, что $N_0^{(k+1)}=N_0^{(k)}-M_0$, так как количество чисел, не обладающих ни одним из свойств $a_1,\ldots ,a_k,a_{k+1}$ равно количеству чисел, не обладающих ни одним из свойств $a_1,\ldots ,a_k$, за вычетом количества тех из них, что обладают свойством $a_{k+1}$.
Имеем
$$N_0^{(k+1)}=N_0^{(k)}-M_0=N-N(a_1)-\ldots - N(a_k)+N(a_1,a_2)+\ldots +N(a_{k-1},a_k)+\ldots +(-1)^k\cdot N(a_1,\ldots ,a_k)-$$
$$-\big(M-M(a_1)-\ldots - M(a_k)+M(a_1,a_2)+\ldots +M(a_{k-1},a_k)+\ldots +(-1)^k\cdot M(a_1,\ldots ,a_k)\big)=$$
$$=N-N(a_1)-\ldots - N(a_k)-N(a_{k+1})+N(a_1,a_2)+\ldots +N(a_{k-1},a_k)+N(a_1,a_{k+1})+\ldots +N(a_k,a_{k+1})+\ldots +$$
$$+(-1)^{k+1}\cdot N(a_1,\ldots ,a_k,a_{k+1}).$$
Теорема 6 доказана
. Пусть теперь у нас есть натуральное число $N=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$. Рассмотрим $N$ объектов, которыми будут числа $1,2,\ldots ,N$. Введём свойства $ a_1,\ldots , a_k $ так: натуральное число обладает свойством $a_i, i=1,\ldots ,k$, если $p_i$ делит данное число. Очень легко сосчитать $N (a_{i_1},\ldots ,a_{i_j}) $, ведь некоторое число делится одновременно на $p_{i_1},\ldots ,p_{i_j}$ тогда и только тогда, когда оно делится на $p_{i_1}\cdots p_{i_j}$, а таких чисел ровно $\frac{N}{p_{i_1}\cdots p_{i_j}}$. Заметим также, что $N_0^{(k)}=\varphi(N)$, поскольку число не делится ни на одно из простых $p_1,\ldots ,p_k$ тогда и только тогда, когда это число взаимно просто с $N$. Имеем
$$\varphi(N)=N_0^{(k)}=N-N(a_1)-\ldots - N(a_k)+N(a_1,a_2)+\ldots +N(a_{k-1},a_k)+\ldots +(-1)^k\cdot N(a_1,\ldots ,a_k)=$$
$$=N-\frac{N}{p_1}-\ldots -\frac{N}{p_k}+\frac{N}{p_1\cdot p_2}+\ldots+\frac{N}{p_{k-1}\cdot p_k}+\ldots+(-1)^k\frac{N}{p_1\cdots p_k}=$$
$$=N\cdot\Big(1-\frac{1}{p_1}-\ldots -\frac{1}{p_k}+\frac{1}{p_1\cdot p_2}+\ldots+\frac{1}{p_{k-1}\cdot p_k}+\ldots+(-1)^k\frac{1}{p_1\cdots p_k}\Big)=$$
$$=N\cdot\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=N\cdot\prod_{p|N}\left(1-\frac{1}{p}\right).$$
Заметим, что в сумме в предпоследней строчке перед каждым слагаемым вида $\frac{1}{p_{i_1}\cdots p_{i_j}}$ стоит знак $(-1)^j$, что по определению функции Мёбиуса равно $\mu(p_{i_1}\cdots p_{i_j})$. На самом деле, мультипликативность функции Эйлера можно доказать, пользуясь совсем простыми соображениями. Пусть $m,n$ – натуральные числа и $(m,n)=1$. Тогда натуральное число взаимно просто с $m\cdot n$ тогда и только тогда, когда оно взаимно просто как с $m$, так и с $n$.
Запишем числа $1,2,\ldots ,m\cdot n$ в несколько строк одинаковой длины:
$${}\hspace{10mm}1\hspace{28mm}2\hspace{28mm}3\hspace{8mm}\ldots\hspace{9mm}n$$
$${}\hspace{6mm}n+1\hspace{20mm}n+2\hspace{20mm}n+3\hspace{7mm}\ldots\hspace{7mm}2n$$
$${}\hspace{11mm}\vdots\hspace{29mm}\vdots\hspace{29mm}\vdots\hspace{7mm}\ldots\hspace{10mm}\vdots$$
$$(m-1)n+1\hspace{5mm}(m-1)n+2\hspace{5mm}(m-1)n+3\hspace{6mm}\ldots\hspace{5mm}m\cdot n$$
По второму свойству делимости в каждой строке столько же взаимно простых с $n$ чисел, сколько и в первой строке, а именно $\varphi(n)$, причём взаимно простые с $n$ числа из каждой строки стоят в одних и тех же столбцах, то есть для каждого столбца либо все элементы взаимно просты с $n$ (и таких столбцов $\varphi(n)$), либо все элементы не взаимно просты с $n$. Покажем теперь, что все числа, которые стоят в любом из столбцов, дают различные остатки при делении на $m$. Поскольку в каждом столбце находится $m$ чисел, то это будет означать, что при делении на $m$ они дают все $m$ остатков, какие только бывают. А значит, снова по второму свойству делимости, среди них будет столько же чисел, взаимно простых с $m$, сколько их среди чисел $0,1,2,\ldots ,m-1$, а именно $\varphi(m)$. Тогда всего в нашей таблице чисел, взаимно простых одновременно с $m$ и с $n$, будет $\varphi(m)\cdot\varphi(n)$. С другой стороны, это количество чисел среди $1,2,\ldots ,m\cdot n$, взаимно простых с $m\cdot n$, что равно $\varphi(m\cdot n)$. Итак, числа в $k$-м столбце имеют вид $a\cdot n+k,\ a=0,1,2,\ldots ,m-1$. Допустим, у двух из них совпали остатки при делении на $m$. То есть $a_1\cdot n+k=q_1\cdot m+r$ и $a_2\cdot n+k=q_2\cdot m+r$, где $0\leqslant a_1 Пусть $m$ натуральное число. Произвольное целое число можно поделить на $m$ с остатком, который принимает значения $0,1,2,\ldots ,m-1$. Разобьём множество целых чисел на $m$ классов, каждый из которых содержит все целые числа, дающие один и тот же остаток при делении на $m$. Это будут так называемые классы вычетов по модулю числа
$m$. Выберем из каждого класса вычетов ровно по одному представителю, тогда полученное множество называется полной системой вычетов по модулю
$m$. Если же из произвольной полной системы вычетов дополнительно выбрать только те числа, которые взаимно просты с $m$, то полученное множество будем называть приведённой системой вычетов по модулю
$m$. Пример 5
. Вот некоторые полные системы вычетов по модулю $7$:
$$\{0,1,2,3,4,5,6\},\quad\{1,2,3,4,5,6,7\},\quad\{-27,-19,-11,-3,5,13,21\}.$$
Соответствующие им приведённые системы вычетов по модулю $7$:
$$\{1,2,3,4,5,6\},\quad\{1,2,3,4,5,6\},\quad\{-27,-19,-11,-3,5,13\}.$$
Дадим также некоторые полные системы вычетов по модулю $9$:
$$\{0,1,2,3,4,5,6,7,8\},\quad\{-4,-3,-2,-1,0,1,2,3,4\},\quad\{100,200,300,400,500,600,700,800,900\}.$$
Соответствующие им приведённые системы вычетов по модулю $9$:
$$\{1,2,4,5,7,8\},\quad\{-4,-2,-1,1,2,4\},\quad\{100,200,400,500,700,800\}.$$ Заметим, что если имеются две полные системы вычетов по модулю $m$, то каждый элемент одной из них сравним по модулю $m$ с каким-то одним и только одним элементом другой, просто потому, что каждая полная система вычетов по модулю $m$ содержит ровно по одному представителю из каждого класса вычетов по модулю $m$. То же самое свойство сохранится и если мы рассмотрим две произвольные приведённые системы вычетов по модулю $m$. В частности, поскольку числа $1,2,\ldots ,m$ образуют полную систему вычетов по модулю $m$, то соответствующая приведённая система вычетов будет выбираться из этих чисел и по определению функции Эйлера будет состоять из $\varphi(m)$ элементов. А следовательно и в любой приведённой системе вычетов по модулю $m$ будет содержаться $\varphi(m)$ чисел. Одновременно таково будет количество классов вычетов по модулю $m$, состоящих из взаимно простых с $m$ чисел. Если числа $a$ и $b$ содержатся в одном и том же классе вычетов по модулю $m$, то говорят, что они сравнимы по модулю
$m$. Обозначается это так:
$$a\equiv b\pmod{m}.$$
Заметим, что $a\equiv b\pmod{m}\Leftrightarrow m|(b-a)$. Из этого замечания, самого определения и из свойств делимости вытекают следующие очевидные свойства сравнений: $a\equiv a\pmod{m}$. Если $a\equiv b\pmod{m}$ и $b\equiv c\pmod{m}$, то $a\equiv c\pmod{m}$. Если $a\equiv b\pmod{m}$ и $c\in\mathbb{Z}$, то $a\cdot c\equiv b\cdot c\pmod{m}$. Если $a\cdot n\equiv b\cdot n\pmod{m}$ и $(m,n)=1$, то $a\equiv b\pmod{m}$. Если $a\cdot n\equiv b\cdot n\pmod{m\cdot n}$, то $a\equiv b\pmod{m}$. Если $a\equiv b\pmod{m}$ и $c\equiv d\pmod{m}$, то $a\pm c\equiv b\pm d\pmod{m}$ и $a\cdot c\equiv b\cdot d\pmod{m}$. Прокомментируем лишь последнее свойство. Из третьего свойства получаем $a\cdot c\equiv b\cdot c\pmod{m}$ и $b\cdot c\equiv b\cdot d\pmod{m}$. Теперь по второму свойству находим $a\cdot c\equiv b\cdot d\pmod{m}$. Предложение 3
. Пусть $a$ пробегает полную систему вычетов по модулю $m$, а также $k,n\in\mathbb{Z}$ и $(m,n)=1$. Тогда числа вида $a\cdot n+k$ тоже пробегают полную систему вычетов по модулю $m$. Доказательство
. Достаточно повторить рассуждения последнего абзаца предыдущего доказательства мультипликативности функции Эйлера. Сделаем это. Необходимо показать, что все эти числа $a\cdot n+k$ лежат в разных классах вычетов по модулю $m$. Допустим, что два из них лежат в одном и том же классе, то есть $a_1\cdot n+k\equiv a_2\cdot n+k\pmod{m}$, где $a_1\not\equiv a_2\pmod{m}$. Но тогда из первого и шестого свойств сравнений следует, что $a_1\cdot n\equiv a_2\cdot n\pmod{m}$, и, так как $(m,n)=1$, то по четвёртому свойству сравнений $a_1\equiv a_2\pmod{m}$. Противоречие. Предложение 3 доказано
. Следствие 10
. Пусть $a$ пробегает приведённую систему вычетов по модулю $m$, а также $n\in\mathbb{Z},\ (m,n)=1$. Тогда числа вида $a\cdot n$ тоже пробегают приведённую систему вычетов по модулю $m$. Доказательство
. По предложению 3, если $a$ пробегает полную систему вычетов по модулю $m$, то и $a\cdot n$ тоже. Очевидно, что взаимно просты с $m$ будут те и только те числа $a\cdot n$, для которых $a$ взаимно просто с $m$. Следствие 10 доказано
. Теорема Эйлера
. Пусть $m$ натуральное число, $b\in\mathbb{Z},\ (b,m)=1$. Тогда $b{}^{\varphi(m)}\equiv 1\pmod{m}$. Доказательство
. Пусть $a$ пробегает приведённую систему вычетов по модулю $m$. Тогда по следствию 10 числа вида $a\cdot b$ тоже пробегают приведённую систему вычетов по модулю $m$. Каждый элемент первой совокупности сравним по модулю $m$ с каким-то одним и только одним элементом второй совокупности. Следовательно произведение элементов первой совокупности сравнимо по модулю $m$ с произведением элементов второй. Если занумеровать элементы первой совокупности $a_1,a_2,\ldots ,a_{\varphi(m)}$, то можно записать это так:
$$\prod_{i=1}^{\varphi(m)}a_i\ \equiv\ \prod_{i=1}^{\varphi(m)}(a_i\cdot b)\ =\ b{}^{\varphi(m)}\prod_{i=1}^{\varphi(m)}a_i\pmod{m}.$$
Так как по определению все элементы приведённой системы вычетов взаимно просты с $m$, то по четвёртому свойству сравнений мы можем сократить левую и правую части сравнения на $\displaystyle\prod_{i=1}^{\varphi(m)}a_i$ и получим, что $b{}^{\varphi(m)}\equiv 1\pmod{m}$. Теорема Эйлера доказана
. Заметим, что если $(b,m)>1$, то сравнение $b{}^{\varphi(m)}\equiv 1\pmod{m}$ не может выполняться, так как из него бы следовало, что с некоторым целым числом $y$ верно $b{}^{\varphi(m)}+my= 1$, откуда по второму свойству делимости $(b,m)|1$. Пусть $(M,m)=1$. Тогда существует бесконечно много решений уравнения $Mx+my=1$. Общее решение имеет вид $x=x_0+m\cdot t,\ y=y_0-M\cdot t,\ t\in\mathbb{Z}$. Если перейти на язык сравнений, то получится, что сравнение $Mx\equiv 1\pmod{m}$ имеет решение $x\equiv x_0\pmod{m}$. Каждого из представителей класса вычетов по модулю $m$, содержащего $x_0$, будем обозначать $M^{-1}$ и будем говорить, что это обратный к $M$ вычет по модулю $m$. Очевидно, что $(M^{-1},m)=1$ и $(M^{-1})^{-1}\equiv M\pmod{m}$. Мы видим, что все вычеты, обратные к данному, содержатся в одном единственном классе по модулю $m$, и для представителей разных классов вычетов по модулю $m$ обратные к ним вычеты будут содержаться также в разных классах по модулю $m$. Если же $(M,m)>1$, то уравнение $Mx+my=1$ не имеет решений и $M$ не будет иметь обратного элемента по модулю $m$. Пусть $m_1,\ldots ,m_n$ натуральные попарно взаимно простые числа, и требуется решить систему сравнений
$$x\equiv a_1\pmod{m_1};$$
$$\ldots$$
$$x\equiv a_n\pmod{m_n}.$$
Положим $M=m_1\cdots m_n$ и $M_i=\frac{M}{m_i},\ i=1,\ldots ,n$. По условию получается, что при всех $i=1,\ldots ,n$ будет $(M_i,m_i)=1$ и согласно предыдущему пункту можно найти $M_i^{-1}$ по модулю $m_i$. Теорема 7
. Все решения указанной системы состоят из всех представителей одного единственного класса вычетов по модулю $M$ и удовлетворяют условию
$$x\equiv a_1\cdot M_1\cdot M_1^{-1}+a_2\cdot M_2\cdot M_2^{-1}+\ldots +a_n\cdot M_n\cdot M_n^{-1}\pmod{M}.$$ Доказательство
. Пусть $x,y$ два решения нашей системы. Получаем для каждого $i=1,\ldots ,n$ выполнено сравнение $x\equiv a_i\equiv y\pmod{m_i}$. Таким образом, $x-y$ делится на каждое $m_i$, а значит является их общим кратным и делится на их наименьшее общее кратное, которое по следствию 6 равняется $M$. Это эквивалентно тому, что $x\equiv y\pmod{M}$. Обратно, если $y$ является решением системы и $x\equiv y\pmod{M}$, то $x$ также будет решением системы, так как $x=y+kM$ с некоторым целым числом $k$ и $M\equiv 0\pmod{m_i}$ для каждого $i=1,\ldots ,n$. Далее, заметим, что при $j\neq i$ имеем $M_j\equiv 0\pmod {m_i} $. Поэтому при любом $i=1,\ldots ,n$ получаем
$$a_1\cdot M_1\cdot M_1^{-1}+\ldots +a_n\cdot M_n\cdot M_n^{-1}\equiv a_i\cdot M_i\cdot M_i^{-1}\equiv a_i\pmod {m_i}, $$
то есть данное число является решением нашей системы сравнений. Теорема 7 доказана
. Замечание 5
. Формула, приведённая в условии теоремы 7, устанавливает взаимно однозначное соответствие между совокупностью полных систем вычетов по модулям $m_1,\ldots ,m_n$ и полной системой вычетов по модулю $M$. В частности, тот факт, что решение системы единственно по модулю $M$, иногда позволяет на практике угадывать это решение, не прибегая к вычислениям. Например, решением системы
$$x\equiv 4\pmod{9};$$
$$x\equiv 5\pmod{8};$$
$$x\equiv 6\pmod{7}$$
очевидно будет $x\equiv 13\pmod{504}$. Пусть $p$ простое число, $a,b$ целые и $(a,p)=1$. У сравнения $ax\equiv b\pmod{p}$ существует единственное по модулю $p$ решение, так как все решения уравнения $ax+py=b$ имеют вид $x=x_0+pt,\ y=y_0-at,\ t\in\mathbb{Z}$.
Оказывается, имеет место более общее утверждение, а именно Теорема 8
(теорема Лагранжа). Пусть $p$ простое число и $f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots +a_1x+a_0$, где $a_n,\ldots ,a_0\in\mathbb{Z}$, причём $a_n\not\equiv 0\pmod{p}$. Тогда сравнение $f(x)\equiv 0\pmod{p}$ имеет не более $n$ решений по модулю $p$. Доказательство
. Проведём индукцию по $n$. При $n=1$ справедливость теоремы уже установлена. Пусть утверждение теоремы верно для всех многочленов степени $n-1$. Покажем, что оно справедливо и для многочленов степени $n$. Пусть $f(x)$ – многочлен, описанный в условии теоремы. Если сравнение $f(x)\equiv 0\pmod{p}$ неразрешимо, то утверждение теоремы выполняется. Допустим указанное сравнение имеет некоторое решение $x_0$, то есть $f(x_0)\equiv 0\pmod{p}$. Тогда
$$f(x)\equiv f(x)-f(x_0)=a_n(x^n-x_0^n)+a_{n-1}(x^{n-1}-x_0^{n-1})+\ldots +a_1(x-x_0)=(x-x_0)\cdot g(x)\pmod{p},$$
где $g(x)=a_nx^{n-1}+\ldots$ – многочлен степени $n-1$, и по предположению индукции сравнение $g(x)\equiv 0\pmod{p}$ имеет не более $n-1$ решения по модулю $p$. При этом из установленного сравнения следует, что $f(x)\equiv 0\pmod{p}$ тогда и только тогда, когда $g(x)\equiv 0\pmod{p}$ или $x-x_0\equiv 0\pmod{p}$. Второе из этих сравнений имеет единственное решение по модулю $p$, а значит сравнение $f(x)\equiv 0\pmod{p}$ имеет не более $n$ решений. Теорема 8 доказана
. Замечание 6
. Если $m$ составное число, то сравнение $f(x)\equiv 0\pmod{m}$ может иметь более $n$ решений по модулю $m$. Например у сравнения $x^2\equiv 4\pmod{15}$ имеется $4$ решения: $x\equiv \pm 2\pmod{15},\ x\equiv \pm 7\pmod{15}$. Дело в том, что если сравнение выполнено по модулю $15$, то оно также выполняется и по модулям $3$ и $5$. C другой стороны, из любой пары решений сравнения по модулям $3$ и $5$ по китайской теореме об остатках единственным образом можно получить одно из решений сравнения по модулю $15$. То есть решений по модулю $15$ будет ровно столько, сколько можно составить различных пар решений по модулям $3$ и $5$. По модулю $3$, как и по модулю $5$ есть ровно два решения, а именно $x\equiv\pm 2$. Это позволяет составить четыре различные пары, которые и отвечают предъявленным решениям по модулю $15$. В общем случае, если пользоваться обозначениями китайской теоремы об остатках, когда у некоторого сравнения будет $N_1,\ldots , N_n$ решений по модулям $m_1,\ldots , m_n$, то у этого же сравнения по модулю $M$ будет $N_1\cdots N_n$ решений. Пусть $p$ простое нечётное число, $a,b$ целые и $(a,p)=(b,p)=1$. У сравнения $ax\equiv b\pmod{p}$ существует, как мы видели, единственное по модулю $p$ решение.
Очевидно, что при различных $a$ эти решения тоже будут различны, ведь из сравнений $a_1x\equiv a_2x\equiv b\pmod{p}$ следовало бы $a_1\equiv a_2\pmod{p}$, так как очевидно $(x,p)=1$.
Заметим также, что если $a_1$ есть решение сравнения $ax\equiv b\pmod{p}$, то, наоборот, $a$ будет решением сравнения $a_1x\equiv b\pmod{p}$. При некоторых $b$ возможно, что само $a$ будет решением сравнения $ax\equiv b\pmod{p}$. Это случится тогда и только тогда, когда разрешимо сравнение $x^2\equiv b\pmod{p}$. Сколько решений может иметь такое сравнение? Пусть $x$ – некоторое решение данного сравнения, тогда $-x$ – тоже его решение. При этом из $(b,p)=1$ следует $x\not\equiv 0\pmod{p}$, а значит $x\not\equiv -x\pmod{p}$, поскольку $p$ нечётно. По теореме Лагранжа более двух решений данное сравнение иметь не может. Следовательно $x$ и $-x$ – все решения данного сравнения. Если же $p|b$, то $x\equiv 0\pmod{p}$, очевидно, является единственным решением. При $(b,p)=1$ получается, что если сравнение $x^2\equiv b\pmod{p}$ неразрешимо, то приведённая система вычетов по модулю $p$ разбивается на пары чисел $a,a_1$ таких, что $aa_1\equiv b\pmod{p}$, а значит произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $b^{\frac{p-1}{2}}$ по модулю $p$. Если же сравнение $x^2\equiv b\pmod{p}$ разрешимо, то приведённая система вычетов по модулю $p$ разбивается на пары чисел $a,a_1$ таких, что $aa_1\equiv b\pmod{p}$ за исключением двух решений $x$ и $-x$ сравнения $x^2\equiv b\pmod{p}$, произведение которых сравнимо с $-b$ по модулю $p$. Таким образом, произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $-b^{\frac{p-1}{2}}$ по модулю $p$. Очень удобно рассмотреть следующее обозначение, называемое символом Лежандра
: $\left(\frac{b}{p}\right)=1$, если $(b,p)=1$ и сравнение $x^2\equiv b\pmod{p}$ разрешимо; $\left(\frac{b}{p}\right)=0$, если $(b,p)\neq 1$, то есть $p|b$; $\left(\frac{b}{p}\right)=-1$, если сравнение $x^2\equiv b\pmod{p}$ неразрешимо. Пример 5
. $\left(\frac{1}{p}\right)=1$, так как $(1,p)=1$ и сравнение $x^2\equiv 1\pmod{p}$ имеет очевидные решения $x\equiv 1\pmod{p}$ и $x\equiv -1\pmod{p}$. Рассмотрим как раз случай $b=1$ в проведённых выше рассуждениях. Так как сравнение $x^2\equiv 1\pmod{p}$ разрешимо, то произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $-1^{\frac{p-1}{2}}$, то есть с $-1$ по модулю $p$. Это позволяет доказать ряд известных теорем. Теорема Вильсона
. Пусть $p$ простое число. Тогда $(p-1)!\equiv -1\pmod{p}$. Доказательство
. При $p=2$ утверждение теоремы очевидно выполняется. Поскольку числа $1,2,\ldots ,p-1$ составляют приведённую систему вычетов по модулю $p$, то их произведение, как раз равное $(p-1)!$, сравнимо с $-1$ по модулю $p$ и в случае любого нечётного простого $p$. Теорема Вильсона доказана
. Критерий Эйлера
. Пусть $b\in\mathbb{Z}$. Тогда $\left(\frac{b}{p}\right)\equiv b^{\frac{p-1}{2}}\pmod{p}$. Доказательство
. Пусть $b\in\mathbb{Z}, (b,p)=1$. Мы знаем, что если сравнение $x^2\equiv b\pmod{p}$ неразрешимо, то $b^{\frac{p-1}{2}}$ сравнимо с произведением всех элементов приведённой системы вычетов по модулю $p$, которое, в свою очередь, сравнимо с $-1$. Но и символ Лежандра $\left(\frac{b}{p}\right)$ в этом случае тоже равен $-1$. Если же сравнение $x^2\equiv b\pmod{p}$ разрешимо, то $-b^{\frac{p-1}{2}}$ сравнимо с произведением всех элементов приведённой системы вычетов по модулю $p$, а значит $b^{\frac{p-1}{2}}\equiv 1\pmod{p}$. При этом символ Лежандра $\left(\frac{b}{p}\right)$ в этом случае также равен $1$. Пусть теперь $p|b$. Но тогда $b^{\frac{p-1}{2}}\equiv 0\pmod{p}$, и символ Лежандра $\left(\frac{b}{p}\right)$ тоже равен $0$. Таким образом, во всех случаях критерий Эйлера доказан
. Теорема Ферма
. Пусть $b\in\mathbb{Z}, (b,p)=1$. Тогда $b^{p-1}\equiv 1\pmod{p}$. Доказательство
. Это очевидно следует из критерия Эйлера, поскольку при $(b,p)=1$ будет $b^{\frac{p-1}{2}}\equiv\pm 1\pmod{p}$, и утверждение теоремы Ферма получится при возведении обеих частей данного сравнения в квадрат. Теорема Ферма доказана
. Второй способ – повторить доказательство теоремы Эйлера, ведь теорема Ферма является её частным случаем при $m=p$. Заметим, что при $(b,p)\neq 1$, то есть когда $p|b$, будет $b^{p-1}\equiv 0\pmod{p}$. Поэтому, чтобы включить и этот случай в условие теоремы Ферма, используют следующую формулировку: для любого целого числа $b$ выполнено
$$b^p\equiv b\pmod{p}.$$ Пусть $p$ нечётное простое число, $a,b\in\mathbb{Z}$. Тогда Если $a\equiv b\pmod{p}$, то $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$; $\left(\frac{a\cdot b}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$; Если $p\nmid b$, то $\left(\frac{b^2}{p}\right)=1$, в частности $\left(\frac{1}{p}\right)=1$; $\left(\frac{-1}{p}\right)=1$, если $p\equiv 1\pmod{4}$, $\left(\frac{-1}{p}\right)=-1$, если $p\equiv -1\pmod{4}$; $\left(\frac{2}{p}\right)=1$, если $p\equiv\pm 1\pmod{8}$, $\left(\frac{2}{p}\right)=-1$, если $p\equiv\pm 3\pmod{8}$; Квадратичный закон взаимности
. Пусть $p,q$ нечётные простые числа, тогда $\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)$, если $p\equiv q\equiv -1\pmod{4}$, $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$ иначе. Докажем эти свойства символа Лежандра. Пусть $a\equiv b\pmod{p}$, тогда, если $p\nmid b$, то и $p\nmid a$, и сравнение $x^2\equiv a\pmod{p}$ разрешимо тогда и только тогда, когда разрешимо сравнение $x^2\equiv b\pmod{p}$. Если же $p|b$, то также $p|a$. В обоих случаях по определению символа Лежандра получаем, что $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$. Первое свойство доказано
. По критерию Эйлера имеем
$$\left(\frac{a\cdot b}{p}\right)\equiv (ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\pmod{p}.$$
Поскольку как правая, так и левая часть сравнения есть целое число, не превосходящее $1$ по абсолютной величине, то их разность не превосходит $2$ по абсолютной величине, при этом по определению сравнимости эта разность должна делиться на $p$, которое больше или равно трём, что возможно лишь когда эти два числа равны. Второе свойство доказано
. При $p\nmid b$ сравнение $x^2\equiv b^2\pmod{p}$ имеет два очевидных решения $x\equiv b\pmod{p}$ и $x\equiv -b\pmod{p}$, откуда по определению символа Лежандра получаем, что $\left(\frac{b^2}{p}\right)=1$. Третье свойство доказано
. По критерию Эйлера имеем
$$\left(\frac{-1}{p}\right)\equiv (-1)^{\frac{p-1}{2}}\pmod{p}.$$
Опять как правая, так и левая часть сравнения есть целое число, не превосходящее $1$ по абсолютной величине, а модуль по которому эти величины сравнимы, не меньше трёх, а значит эти два числа равны. Но то, что $(-1)^{\frac{p-1}{2}}=1$, если $p\equiv 1\pmod{4}$, и $(-1)^{\frac{p-1}{2}}=-1$, если $p\equiv -1\pmod{4}$, очевидно. Четвёртое свойство доказано
. Пятое свойство можно доказать отдельно, но удобнее воспользоваться следующим результатом: Лемма Гаусса
. Пусть $p$ нечётное простое число, $b\in\mathbb{Z},\ p\nmid b$. Тогда
$$\left(\frac{b}{p}\right)=(-1)^N,$$
где $N$ – количество отрицательных среди чисел $\varepsilon_1,\varepsilon_2,\ldots ,\varepsilon_{\frac{p-1}{2}}$, определяемых следующим образом. Поскольку числа $\pm 1,\pm 2,\ldots ,\pm\frac{p-1}{2}$ образуют приведённую систему вычетов по модулю $p$, то любое взаимно простое с $p$ число сравнимо по модулю $p$ ровно с одним из этих чисел. Пусть $k=1, 2,\ldots ,\frac{p-1}{2}$, тогда $b\cdot k\equiv\varepsilon_kr_k\pmod{p}$, где $\varepsilon_k=\pm 1$ и $r_k\in\{1, 2,\ldots ,\frac{p-1}{2}\}$. Доказательство
. Покажем, что среди чисел $r_1, r_2,\ldots ,r_{\frac{p-1}{2}}$ нет равных друг другу, то есть они представляют собой перестановку чисел $1, 2,\ldots ,\frac{p-1}{2}$. От противного, если $i Воспользуемся леммой Гаусса при $b=2$. Поскольку $2\cdot k\leqslant\frac{p-1}{2}$ при $1\leqslant k\leqslant\left[\frac{p-1}{4}\right]$, то $\varepsilon_1=\ldots =\varepsilon_{[\frac{p-1}{4}]}=1$, а так как $\frac{p-1}{2}<2\cdot k\leqslant p-1$ при $\left[\frac{p-1}{4}\right]< k\leqslant{\textstyle \frac{p-1}{2}}$, то $\varepsilon_{[\frac{p-1}{4}]+1}=\ldots =\varepsilon_{\frac{p-1}{2}}=-1$, например $2\cdot\frac{p-1}{2}\equiv -1\pmod{p}$. Отсюда $N=\frac{p-1}{2}-\left[\frac{p-1}{4}\right]=\left[\frac{p+1}{4}\right]$. Получаем, что
$\left(\frac{2}{p}\right)=(-1)^{[\frac{p+1}{4}]},$ и очевидно, что $(-1)^{[\frac{p+1}{4}]}=1$, если $p\equiv\pm 1\pmod{8}$, и $(-1)^{[\frac{p+1}{4}]}=-1$, если $p\equiv\pm 3\pmod{8}$. Пятое свойство доказано
. Если $p=q$, то шестое свойство верно. Пусть теперь $p,q$ различные нечётные простые числа и $b$ произвольное целое число. Будем ассоциировать с ним пару чисел $(b_p,b_q), |b_p|\leqslant\frac{p-1}{2},\ |b_q|\leqslant\frac{q-1}{2}$, где $b\equiv b_p\pmod{p}$ и $b\equiv b_q\pmod{q}$. Поскольку $b_p$ и $b_q$ пробегают полные системы вычетов по модулям соответственно $p$ и $q$, то согласно китайской теореме об остатках множество всех пар $(b_p,b_q)$ можно поставить во взаимно однозначное соответствие с произвольной полной системой вычетов по модулю $pq$. Рассмотрим множества
$$P_1=\left\{1,2,\ldots ,\frac{pq-1}{2}\right\},\quad P_2=\left\{-1,-2,\ldots ,-\frac{pq-1}{2}\right\}$$
и несколько их подмножеств
$$S_2=\left\{b\in P_1\ \Big|\ 1\leqslant b_p\leqslant\frac{p-1}{2},\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},\quad
R_2=\left\{b\in P_2\ \Big|\ 1\leqslant b_p\leqslant\frac{p-1}{2},\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},$$
$$S_3=\left\{b\in P_1\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ 1\leqslant b_q\leqslant\frac{q-1}{2}\right\},\quad
R_3=\left\{b\in P_2\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ 1\leqslant b_q\leqslant\frac{q-1}{2}\right\},$$
$$S_4=\left\{b\in P_1\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},\quad
R_4=\left\{b\in P_2\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},$$
$$T_1=\left\{b\in P_1\ \Big|\ b_p=0,\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},\quad
T_2=\left\{b\in P_1\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ b_q=0\right\}.$$
Так как объединение непересекающихся множеств $P_1$ и $P_2$ образует полную систему вычетов по модулю $pq$, то по вышесказанному ему можно поставить в соответствие множество всевозможных пар $(b_p,b_q)$, а значит объединение множеств $S_2$ и $R_2$ будет содержать все числа $b$, удовлетворяющие условиям $1\leqslant b_p\leqslant\frac{p-1}{2},\ -\frac{q-1}{2}\leqslant b_q\leqslant -1$, откуда
$$|S_2|+|R_2|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$
Но очевидное сопоставление $x\longleftrightarrow -x$ устанавливает взаимно однозначное соответствие между множествами $R_2$ и $S_3$. Поэтому $|R_2|=|S_3|$ и
$$|S_2|+|S_3|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$
Далее, объединение множеств $S_2,\ S_4$ и $T_1$ содержит все числа из $P_1$ с условием $-\frac{q-1}{2}\leqslant b_q\leqslant -1$. Эти числа можно явно перечислить:
$$\frac{q+1}{2},\ldots ,q-1,q+\frac{q+1}{2},\ldots ,2q-1,\ldots,\frac{p-3}{2}\cdot q+\frac{q+1}{2},\ldots ,\frac{p-1}{2}\cdot q-1.$$
Их количество равно $\frac{p-1}{2}\cdot\frac{q-1}{2}$, то есть
$$|S_2|+|S_4|+|T_1|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$
Аналогично $$|S_3|+|S_4|+|T_2|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$
Комбинируя три полученных равенства, находим
$$2|S_4|+|T_1|+|T_2|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$
Откуда $(-1)^{|T_1|+|T_2|}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$, что равносильно
$$(-1)^{|T_1|}=(-1)^{|T_2|}(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.$$
Остаётся заметить, что множество $T_2$ состоит в точности из тех чисел множества $\left\{q,2q,\ldots ,\frac{p-1}{2}q\right\}$, которые по модулю $p$ сравнимы с одним из чисел $-1,-2,\ldots ,-\frac{p-1}{2}$. Их количество есть в точности число $N$ из леммы Гаусса при $b=q$, так что по этой самой лемме
$$(-1)^{|T_2|}=\left(\frac{q}{p}\right).$$
Аналогично $$(-1)^{|T_1|}=\left(\frac{p}{q}\right).$$
При этом очевидно, что $(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}=-1$, если $p\equiv q\equiv -1\pmod{4}$, и $(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}=1$ иначе.
Квадратичный закон взаимности доказан
. Ещё вводя в рассмотрение символ Лежандра $\left(\frac{b}{p}\right)$ мы установили, что он даёт полную информацию о разрешимости сравнения $x^2\equiv b\pmod{p}$, а именно Если $\left(\frac{b}{p}\right)=1$, то сравнение имеет два решения; Если $\left(\frac{b}{p}\right)=0$, то сравнение имеет одно решение; Если $\left(\frac{b}{p}\right)=-1$, то сравнение не имеет решений. Это можно резюмировать утверждением, что данное сравнение имеет ровно $\left(\frac{b}{p}\right)+1$ решение. Данное наблюдение можно распространить на произвольное квадратичное сравнение. Пусть $p$ нечётное простое число и имеется сравнение $ax^2+bx+c\equiv 0\pmod{p}$, где $a,b,c\in\mathbb{Z}$ и $p\nmid a$ (чтобы сравнение имело именно вторую, а не меньшую степень). Домножим обе части сравнения на взаимно простое с $p$ число $4a$. Это не повлияет на разрешимость и не изменит решения данного сравнения. Получим $4a^2x^2+4abx+4ac\equiv 0\pmod{p}$. Выделяя полный квадрат и производя замену $y=2ax+b$, получаем
$$y^2\equiv b^2-4ac\pmod{p}.$$
Полученное сравнение, как мы видели, имеет в точности $\left(\frac{b^2-4ac}{p}\right)+1$ решений. Столько же решений будет и у исходного сравнения, так как замена $y=2ax+b$ взаимно однозначно отображает полную систему вычетов по модулю $p$ в таковую же. Следовательно, для подсчёта числа решений квадратичного сравнения по нечётному простому модулю достаточно уметь вычислять символ Лежандра. Доказанных выше свойств этого символа вполне достаточно для эффективного его вычисления, но чтобы делать это максимально быстро удобно ввести также символ Якоби. Пусть $P>1$ нечётное натуральное число, $P=p_1\cdots p_s$ – его разложение на простые множители (возможно совпадающие, но все нечётные) и $A\in\mathbb{Z}$. Тогда символ Якоби
определяется так:
$$\left(\frac{A}{P}\right)=\left(\frac{A}{p_1}\right)\cdots\ \left(\frac{A}{p_s}\right).$$
Свойства символа Лежандра переносятся и на символ Якоби.
Пусть $P$ нечётное число, $A,B\in\mathbb{Z}$. Тогда Если $A\equiv B\pmod{P}$, то $\left(\frac{A}{P}\right)=\left(\frac{B}{P}\right)$; $\left(\frac{A\cdot B}{P}\right)=\left(\frac{A}{P}\right)\left(\frac{B}{P}\right)$; Если $(P,B)=1$, то $\left(\frac{B^2}{P}\right)=1$, в частности $\left(\frac{1}{P}\right)=1$; $\left(\frac{-1}{P}\right)=1$, если $P\equiv 1\pmod{4}$, $\left(\frac{-1}{P}\right)=-1$, если $P\equiv -1\pmod{4}$; $\left(\frac{2}{P}\right)=1$, если $P\equiv\pm 1\pmod{8}$, $\left(\frac{2}{P}\right)=-1$, если $P\equiv\pm 3\pmod{8}$; Пусть $P,Q$ нечётные числа, большие $1$, тогда $\left(\frac{P}{Q}\right)=-\left(\frac{Q}{P}\right)$, если $P\equiv Q\equiv -1\pmod{4}$, $\left(\frac{P}{Q}\right)=\left(\frac{Q}{P}\right)$ иначе. Свойства с первого по третье напрямую следуют из определения символа Якоби и аналогичных свойств для символа Лежандра. Для доказательства четвёртого свойства заметим, что произведение двух чисел, сравнимых с $-1$ по модулю $4$, будет сравнимо с $1$ по модулю $4$. Поэтому, если $P\equiv -1\pmod{4}$, то в разложении $P=p_1\cdots p_s$ количество простых, сравнимых с $-1$ по модулю $4$, нечётно. Но тогда и в произведении $\left(\frac{-1}{p_1}\right)\cdots\ \left(\frac{-1}{p_s}\right)$ количество символов Лежандра, равных $-1$ будет нечётно, откуда $\left(\frac{-1}{P}\right)=-1$. Если же $P\equiv 1\pmod{4}$, то в разложении $P=p_1\cdots p_s$ количество простых, сравнимых с $-1$ по модулю $4$, чётно, и $\left(\frac{-1}{P}\right)=1$. Для доказательства пятого свойства необходимо заметить, что произведение двух чисел, сравнимых с $\pm 3$ по модулю $8$, даёт $\pm 1$ по модулю $8$. Дальнейшие рассуждения аналогичны предыдущему пункту. Для доказательства шестого свойства достаточно рассмотреть нетривиальный случай $(P,Q)=1$ и действовать аналогично, исследуя, чётно или нечётно количество простых, сравнимых с $-1$ по модулю $4$, в разложениях $P$ и $Q$. Замечание 7
. Символ Якоби $\left(\frac{A}{P}\right)$ не даёт полной информации о разрешимости сравнения $x^2\equiv A\pmod{P}$. Разумеется, если $\left(\frac{A}{P}\right)=-1$, то сравнение неразрешимо, но если символ Якоби принимает другие значения, то из этого нельзя сделать определённых выводов. Например, поскольку $15\equiv -1\pmod{8}$, то $\left(\frac{2}{15}\right)=1$, однако сравнение $x^2\equiv 2$ неразрешимо ни по модулю $3$, ни по модулю $5$, а следовательно оно не может быть разрешимо и по модулю $15$. Поэтому главным предназначением символа Якоби является ускорение процедуры вычисления символа Лежандра. Пусть требуется определить количество решений сравнения
$$x^2-19x+1\equiv 0\pmod{1013}.$$
Легко убедиться (например с помощью решета Эратосфена), что $1013$ – простое число, а значит данное сравнение будет иметь $1+\left(\frac{19^2-4}{1013}\right)=1+\left(\frac{357}{1013}\right)$ решений. Находим
$$\left(\frac{357}{1013}\right)=\left(\frac{1013}{357}\right)=\left(\frac{-58}{357}\right)=
\left(\frac{-1}{357}\right)\left(\frac{2}{357}\right)\left(\frac{29}{357}\right)=-\left(\frac{29}{357}\right)=-\left(\frac{357}{29}\right)=-\left(\frac{9}{29}\right)=-1.$$
Здесь мы последовательно применили шестое, первое, второе, четвёртое с пятым, снова шестое и, наконец, третье свойства символа Якоби. Мы имели право так действовать, не оглядываясь на то, что число $357$ является составным.
В итоге, получаем, что рассматриваемое сравнение не имеет решений. Итак, для того, чтобы всё же определить разрешимость сравнения $x^2\equiv A\pmod{P}$ необходимо обладать большей информацией, нежели просто значение символа Якоби $\left(\frac{A}{P}\right)$. Чтобы понять, что это за информация для начала рассмотрим сравнения вида $x^2\equiv A\pmod{p^k}$. Следующий результат описывает даже более полную ситуацию. Лемма Гензеля
. Пусть $p$ простое число, многочлен $f(x)$ имеет целые коэффициенты. Допустим имеется целое число $x_1$ такое, что $f(x_1)\equiv 0\pmod{p}$ и $f"(x_1)\not\equiv 0\pmod{p}$, где $f"(x)$ – производная многочлена $f(x)$. Тогда для любого натурального числа $k$ в любой полной системе вычетов по модулю $p^k$ найдётся единственный элемент $x_k$ с условиями $x_k\equiv x_1\pmod{p}$ и $f(x_k)\equiv 0\pmod{p^k}$. Прежде чем доказывать лемму Гензеля сформулируем следующий вспомогательный результат. Лемма 5
. Пусть $f(x)$ – многочлен степени $m$. Тогда
$$f(x+a)=f(x)+af"(x)+a^2\frac{f""(x)}{2}+\ldots +a^m\frac{f^{(m)}(x)}{m!}.$$ Доказательство
достаточно провести для многочлена вида $f(x)=x^n$ ввиду линейности. Для такого многочлена необходимое равенство приобретает вид
$$(x+a)^n=x^n+nx^{n-1}a+\frac{n(n-1)}{2}x^{n-2}a^2+\ldots +\frac{n(n-1)\cdots 2\cdot 1}{n!}a^n,$$
так что оно представляет из себя в точности формулу бинома Ньютона. Лемма 5 доказана
. Доказательство леммы Гензеля
проведём индукцией по $k$. При $k=1$ в произвольной полной системе вычетов по модулю $p$ найдётся единственный элемент, сравнимый по этому же модулю с $x_1$, а сравнение $f(x_1)\equiv 0\pmod{p}$ выполнено по условию. Пусть теперь $k>1$ и для $k-1$ утверждение верно. Мы ищем элемент $x_k$ с условиями $x_k\equiv x_1\pmod{p}$ и $f(x_k)\equiv 0\pmod{p^k}$. Но для этого элемента будет тогда также выполнено $f(x_k)\equiv 0\pmod{p^{k-1}}$. Ввиду единственности решения этого сравнения по модулю $p^{k-1}$ будем иметь $x_k\equiv x_{k-1}\pmod{p^{k-1}}$. Поэтому $x_k$ следует искать в виде $x_k=x_{k-1}+t\cdot p^{k-1}$ с некоторым целым числом $t$. В приведённой системе вычетов по модулю $p^{k}$ найдётся ровно $p$ элементов такого вида, причём соответствующие им значения $t$ составят полную систему вычетов по модулю $p$. Условие $x_k\equiv x_1\pmod{p}$ будет выполнено автоматически. Для проверки условия $f(x_k)\equiv 0\pmod{p^k}$ воспользуемся леммой 5 и запишем
$$f(x_k)=f(x_{k-1}+t\cdot p^{k-1})=f(x_{k-1})+t\cdot p^{k-1}\cdot f"(x_{k-1})+\ldots\equiv
f(x_{k-1})+t\cdot p^{k-1}\cdot f"(x_{k-1})\pmod{p^k}.$$
Таким образом, должно быть выполнено
$$f(x_{k-1})+t\cdot p^{k-1}\cdot f"(x_{k-1})\equiv 0\pmod{p^k}.$$
Так как $f(x_{k-1})\equiv 0\pmod{p^{k-1}}$, то обе части и модуль этого сравнения можно поделить на $p^{k-1}$. Получим
$$\frac{f(x_{k-1})}{p^{k-1}}+t\cdot f"(x_{k-1})\equiv 0\pmod{p}.$$ Поскольку $f"(x_{k-1})\equiv f"(x_1)\not\equiv 0\pmod{p}$, полученное сравнение относительно $t$ имеет единственное решение. А следовательно и $x_k$ существует и единственно. Лемма Гензеля доказана
. Применим лемму Гензеля для решения сравнения $x^2\equiv A\pmod{p^k}$, где $p$ – нечётное простое число.
Если сравнение $x^2\equiv A\pmod{p}$ неразрешимо, то и наше сравнение не может иметь решений при любом натуральном $k$. Если сравнение $x^2\equiv A\pmod{p}$ имеет единственное решение, то $A\equiv 0\pmod{p}$, а значит и решением будет $x_1\equiv 0\pmod{p}$. В этом случае лемма Гензеля неприменима, так как при $f(x)=x^2$ будем иметь $f"(x)=2x$, но $2x_1\equiv 0\pmod{p}$. Однако этот случай достаточно прост, чтобы уделять ему внимание. Пусть теперь сравнение $x^2\equiv A\pmod{p}$ имеет два различных решения $x\equiv\pm x_1\pmod{p}$. Очевидно $2x_1\not\equiv 0\pmod{p}$ и лемма Гензеля может быть применена. Из неё следует, что для каждого натурального $k$ будет иметься ровно два различных решения сравнения $x^2\equiv A\pmod{p^k}$. Для полноты картины изучим случай $p=2$, при котором лемма Гензеля для сравнения $x^2\equiv A\pmod{2^k}$ неприменима, поскольку $2x_1\equiv 0\pmod{2}$ независимо от значения $x_1$. По модулям $2$ и $4$ ситуация прозрачна. Предложение 4
. Пусть $A\in\mathbb{Z}$ нечётно, $k\in\mathbb{N},\ k\geqslant 3$. Тогда сравнение $x^2\equiv A\pmod{2^k}$ имеет $4$ решения, если $A\equiv 1\pmod{8}$, и неразрешимо иначе. Доказательство
. Проведём индукцию по $k$. При $k=3$ четыре числа $\pm 1,\pm 3$ удовлетворяют сравнению $x^2\equiv 1\pmod{8}$, а так как они образуют приведённую систему вычетов по модулю $8$, то это все решения данного сравнения. Из этого же следует, что сравнения $x^2\equiv A\pmod{8}$ неразрешимы при $A=-1,\pm 3$. Пусть теперь для некоторого $k\geqslant 3$ предложение верно. Выберем некоторое $A\equiv 1\pmod{8}$. По предположению индукции найдётся некоторое нечётное число $x_k$ такое, что $x_k^2\equiv A\pmod{2^k}$, то есть $x_k^2=A+c\cdot 2^k$. Если теперь $c$ чётно, то $x_k^2\equiv A\pmod{2^{k+1}}$. Если же $c$ нечётно, то $(x_k+2^{k-1})^2\equiv A\pmod{2^{k+1}}$, то есть сравнение $x^2\equiv A\pmod{2^{k+1}}$ будет иметь некоторое решение $x_{k+1}$. Но вместе с ним оно будет иметь по крайней мере четыре решения $\pm x_{k+1}\pm 2^k$. C другой стороны, поскольку в приведённой системе вычетов по модулю $2^{k+1}$ ровно каждое четвёртое число сравнимо с $1$ по модулю $8$, то, взяв для каждого из этих чисел по четыре решения соответствующего сравнения, мы уже исчерпаем всю приведённую систему вычетов по модулю $2^{k+1}$, а значит более четырёх решений ни у одного из этих сравнений быть не может. Более того, не может быть решений и у сравнений $x^2\equiv A\pmod{2^{k+1}}$ при $A\not\equiv 1\pmod{8}$. Предложение 4 доказано
. Замечание 8
. Пусть многочлен $f(x)$ имеет целые коэффициенты, и требуется решить сравнение $f(x)\equiv 0\pmod{p_1^{k_1}\cdots p_m^{k_m}}$, где одно из $p_i$ может быть и чётным. Для этого нужно найти решения сравнений $f(x)\equiv 0\pmod{p_i^{k_i}}$ при всех $i=1,\ldots ,m$, и если хотя бы одно из них неразрешимо, то и у исходного сравнения решений нет. Если же каждое из указанных сравнений имеет, скажем, $T_i$ различных решений вида $x\equiv x_1\pmod{p_1^{k_1}},\ldots ,x\equiv x_m\pmod{p_m^{k_m}}$, то, решая такую систему сравнений (с помощью китайской теоремы об остатках), мы получим решение исходного сравнения по модулю $P$. Всего, действуя таким образом, найдётся $T_1\cdots T_m$ решений исходного сравнения. Из всего вышесказанного видно, что если $P=p_1^{k_1}\cdots p_m^{k_m}$, сравнение
$x^2\equiv A\pmod{P}$ будет разрешимо тогда и только тогда, когда разрешимо каждое из сравнений
$x^2\equiv A\pmod{p_i},\ i=1,\ldots ,s$. При этом, если, скажем, $p_1=2$, то по модулю $p_1^{k_1}$ количество решений определяется с учётом предложения 4, а если $p_i^{k_i}$ – число нечётное, то в соответствии с рассуждениями, идущими после леммы Гензеля. При этом случаи $p_i|A$ нужно аккуратно разбирать индивидуально. Пусть $m$ натуральное число. Если целое число $a$ не взаимно просто с $m$, то сравнение $$a^d\equiv 1\pmod{m}$$ невозможно ни при каком натуральном $d$, так как левая часть сравнения и модуль будут делиться на одно и то же отличное от $1$ натуральное число. Если же $(a,m)=1$, то натуральное число $d$, с которым это сравнение будет выполняться, обязательно найдётся. Например по теореме Эйлера подойдёт $d=\varphi(m)$. Наименьшее натуральное
$d$, с которым выполняется сравнение $a^d\equiv 1\pmod{m}$, называется показателем числа
$a$ по модулю
$m$. Из теоремы Эйлера видно, что показатель любого числа не превосходит $\varphi(m)$, но он может быть и меньше этого числа. Например, показатель числа $2$ по модулю $7$ равен $3$, поскольку $2^3\equiv 1\pmod{7}$ и $2^1\not\equiv 1\pmod{7},\ 2^2\not\equiv 1\pmod{7}$. При этом $\varphi(7)=6$. Но если всё же показатель числа $a$ оказался равен $\varphi(m)$, то это число $a$ называется первообразным корнем по модулю
$m$. Например, $3^1\not\equiv 1\pmod{7},\ 3^2\not\equiv 1\pmod{7},\ 3^3\not\equiv 1\pmod{7},\ 3^4\not\equiv 1\pmod{7},\ 3^5\not\equiv 1\pmod{7}$. С другой стороны, очевидно, что $3^6\equiv 1\pmod{7}$, а значит $3$ является первообразным корнем по модулю $7$. Предложение 5
. Пусть $d$ – показатель числа $a$ по модулю $m$ и также с некоторым целым числом $n$ выполняется сравнение $a^n\equiv 1\pmod{m}$. Тогда $d|n$. Доказательство
. От противного, пусть $n=qd+r,\ 0 Следствие 11
. Пусть $d$ – показатель числа $a$ по модулю $m$. Тогда $d|\varphi(m)$. Доказательство
. Рассуждения в начале данного параграфа показывают, что наличие у числа $a$ показателя означает, что $(a,m)=1$, а значит применима теорема Эйлера и $a^{\varphi(m)}\equiv 1\pmod{m}$. По предложению 5 теперь $d|\varphi(m)$. Следствие 11 доказано
. Следствие 12
. Если $(a,m)=1$ и $d$ – показатель числа $a$ по модулю $m$, то $a^k\equiv a^n\pmod{m}$ тогда и только тогда, когда $k\equiv n\pmod{d}$. Доказательство
. Если $k\equiv n\pmod{d}$, то с некоторым $s$ будет $k=n+sd$. Тогда $a^k=a^n(a^d)^s\equiv a^n\pmod{m}$. Обратно, если $a^k\equiv a^n\pmod{m}$, то $a^n(a^{k-n}-1)\equiv 0\pmod{m}$, и так как $(a,m)=1$, то $a^{k-n}\equiv 1\pmod{m}$, откуда по предложению 5 $d|k-n$, то есть $k\equiv n\pmod{d}$. Следствие 12 доказано
. Следствие 13
. Если $a$ – первообразный корень по модулю $m$, то числа $a^0,a^1,\ldots ,a^{\varphi(m)-1}$ образуют приведённую систему вычетов по модулю $m$. Доказательство
. По следствию 12, если $a^k\equiv a^n\pmod{m},\ 0\leqslant n Пусть $p$ простое число. Согласно следствию 13 показателем какого бы то ни было числа может быть только натуральное число $d$, делящее $p-1$. Допустим найдётся какое-то число $a$, имеющее данный показатель $d$. Тогда каждое из чисел $a^0,a^1,\ldots ,a^{d-1}$ является решением сравнения $x^d-1\equiv 0\pmod{p}$, которое не может иметь более $d$ решений по теореме Лагранжа. С другой стороны, по аналогичным с доказательством следствия 13 рассуждениям все эти числа попарно не сравнимы по модулю $p$, а значит это все решения указанного сравнения и только среди них могут присутствовать числа, имеющие показатель $d$. Но если $(k,d)=s$, то $(a^k)^{d/s}\equiv 1\pmod{p}$, поэтому показатель $d$ могут иметь только такие числа $a^k$, для которых $(k,d)=1$, а таких чисел всего $\varphi(d)$. Следовательно, показатель $d$ могут иметь не более чем $\varphi(d)$ некоторых чисел. Если мы обозначим за $\chi(d)$ количество чисел, имеющих по модулю $p$ показатель $d$, то можно записать $$0\leqslant\chi(d)\leqslant\varphi(d).$$
Поскольку каждое из чисел $1,2,\ldots ,p-1$ имеет некоторый показатель, то будем иметь
$$\sum_{d|p-1}\chi(d)=p-1.$$
Но для функции Эйлера мы также выводили соотношение
$$\sum_{d|p-1}\varphi(d)=p-1.$$
Из этих двух тождеств и выписанного чуть выше неравенства следует, что для каждого $d$, делящего $p-1$, выполнено $\chi(d)=\varphi(d)$, в том числе и $\chi(p-1)=\varphi(p-1)$, то есть существуют числа, имеющие показателем $p-1$. По определению это и означает, что существуют первообразные корни по модулю $p$. Причём их найдётся ровно $\varphi(p-1)$ штук (не сравнимых друг с другом по модулю $p$). По предыдущему параграфу существует первообразный корень по модулю $2$. Им является, например, число $1$. По модулю $2^2$ также можно предъявить первообразный корень, скажем $3$. По модулю же $2^3$ не может существовать первообразный корень, так как мы видели, что любое нечётное число $a$ удовлетворяет сравнению $a^2\equiv 1\pmod{8}$. Покажем индукцией по $k$, что для любого $k\geqslant 3$ и нечётного $a$ будет выполнено
$$a^{2^{k-2}}\equiv 1\pmod{2^k},$$
то есть при таких $k$ по модулю $2^k$ первообразных корней нет.
Действительно, при $k=3$ это верно. Если это верно при некотором $k\geqslant 3$, то можно записать
$$a^{2^{k-1}}-1=(a^{2^{k-2}}-1)(a^{2^{k-2}}+1).$$ По предположению индукции первая из скобок в получившемся произведении делится на $2^k$, а вторая делится на $2$. Тогда всё произведение делится на $2^{k+1}$ и требуемое сравнение выполняется для $k+1$. Доказательство завершено. Пусть $m=p_1^{k_1}\cdots p_s^{k_s}$. Покажем, что при $N=[\varphi(p_1^{k_1}),\ldots,\varphi(p_s^{k_s})]$ будем иметь $a^N\equiv 1\pmod{m}$ для любого взаимно простого с $m$ числа $a$. Действительно, число $a$ будет также взаимно просто с каждым из чисел $p_i^{k_i}$ и по теореме Эйлера будем иметь $a^{\varphi(p_i^{k_i})}\equiv 1\pmod{p_i^{k_i}}$. А так как $\varphi(p_i^{k_i})|N$, то для каждого $i=1,\ldots,s$ будет выполнено $a^N\equiv 1\pmod{p_i^{k_i}}$. По китайской теореме об остатках из этой системы сравнений будет следовать $a^N\equiv 1\pmod{p_1^{k_1}\cdots p_s^{k_s}}$, что и требовалось. Заметим, что когда $m=p_1^{k_1}\cdots p_s^{k_s}$ не имеет вид $2^k,\ p^{k}$ или $2p^{k}$ с нечётным простым $p$, то среди чисел, от которых берётся наименьшее общее кратное, обязательно будет несколько чётных чисел, и
$$N=[\varphi(p_1^{k_1}),\ldots,\varphi(p_s^{k_s})]<\varphi(p_1^{k_1})\cdots\varphi(p_s^{k_s})=\varphi(m),$$
а это означает что по модулю $m$ не может быть первообразных корней.
При этом отсутствие первообразных корней по модулю $2^k$, где $k>2$, уже показано. При $k=1$ существование первообразного корня нами уже показано. Теорема 9
. Пусть $g$ – первообразный корень по модулю нечётного простого числа $p$. Если $g^{p-1}\not\equiv 1\pmod{p^2}$, то $g$ будет первообразным корнем по модулю $p^k$ при любом натуральном $k$. Доказательство
. Покажем индукцией по $k$, что $g^{p^{k-1}(p-1)}\not\equiv 1\pmod{p^{k+1}}$ и что $g$ будет первообразным корнем по модулю $p^k$. По условию теоремы оба эти утверждения выполняются при $k=1$. Пусть они выполняются для некоторого $k$. Покажем, что будут они выполнены и для $k+1$. Поскольку $g^{p^{k-1}(p-1)}\not\equiv 1\pmod{p^{k+1}}$, но по теореме Эйлера $g^{p^{k-1}(p-1)}\equiv 1\pmod{p^{k}}$, то можно записать
$g^{p^{k-1}(p-1)}=1+cp^{k}$, где $c$ не делится на $p$. Возведём обе части полученного равенства в степень $p$ и, применив формулу бинома Ньютона, увидим, что $g^{p^{k}(p-1)}=1+cp^{k+1}+c_1p^{k+2}$, откуда $g^{p^{k}(p-1)}\not\equiv 1\pmod{p^{k+2}}$. Пусть теперь $g$ не первообразный корень по модулю $p^{k+1}$. Тогда найдётся $d$, меньшее чем $\varphi(p^{k+1})$, такое что $g^d\equiv 1\pmod{p^{k+1}}$. По предложению 5 число $d$ является делителем $\varphi(p^{k+1})=p^{k}(p-1)$. Но так как $g$ – первообразный корень по модулю $p^{k}$, то $d\geqslant\varphi(p^{k})=p^{k-1}(p-1)$, а из того, что $g^{p^{k-1}(p-1)}\not\equiv 1\pmod{p^{k+1}}$ следует $d\neq p^{k-1}(p-1)$. Значит $d=p^kd"$, где $d"|p-1,\ d" Покажем как найти первообразный корень, удовлетворяющий условию теоремы 9. Если выбрать произвольный первообразный корень $g$ по модулю $p$, то либо $g^{p-1}\not\equiv 1\pmod{p^2}$, и тогда $g$ удовлетворяет всем условиям теоремы, либо $g^{p-1}\equiv 1\pmod{p^2}$, но тогда рассмотрим число $g_1=g+p$. Очевидно, что это также будет первообразный корень по модулю $p$. Однако по формуле бинома Ньютона $$g_1^{p-1}=(g+p)^{p-1}=g^{p-1}+(p-1)pg^{p-2}+cp^2$$ с некоторым числом $c$. Тогда $g_1^{p-1}\equiv 1-pg^{p-2}\not\equiv 1\pmod{p^2}$, так как $p$ не делит первообразный корень $g$. Таким образом, достаточно взять произвольный первообразный корень
$g$ по модулю
$p$ и если
$g^{p-1}\not\equiv 1\pmod{p^2}$, то
$g$ удовлетворяет всем условиям теоремы 9, а иначе
$g+p$ удовлетворяет всем условиям теоремы 9
. Теорема 10
. Пусть $g$ – первообразный корень по модулю $p^k$ для некоторого нечётного простого числа $p$. Если $g$ нечётное число, то $g$ будет первообразным корнем по модулю $2p^k$. Доказательство
. Так как $g$ нечётное число, то оно взаимно просто с $2p^k$. Если оно не первообразный корень по этому модулю, то существует натуральное число $d$, меньшее чем $\varphi(2p^{k})=p^{k-1}(p-1)$, такое что $g^d\equiv 1\pmod{2p^{k}}$. Но тогда и $g^d\equiv 1\pmod{p^{k}}$. Это противоречит тому, что $g$ – первообразный корень по модулю $p^k$, поскольку $d Как видно из теорем 9 и 10, если $g$ – первообразный корень по модулю $p^2$, то это же число будет первообразным корнем и по модулю $p^k$ при любом натуральном $k$, а если $g$ нечётно, то и по модулю $2p^k$. При этом, если $g$ – чётное число, то $g+p^2$ будет уже нечётным и при этом останется первообразным корнем по модулю $p^2$. Таким образом, чтобы для нечётного простого числа
$p$ предъявить первообразный корень по модулю
$2p^k$, нужно найти первообразный корень
$g$ по модулю
$p^2$, и если
$g$ нечётно, то это и есть искомый первообразный корень, а иначе это будет
$g+p^2$. Теорема 11
. Пусть $m$ натуральное число и $g$ целое, взаимно простое с $m$ число. Пусть $\varphi(m)=q_1^{k_1}\cdots q_s^{k_s}$ – разложение на простые множители. Тогда, если для каждого $i=1,\ldots ,s$ выполнено $g^{\varphi(m)/q_i}\not\equiv 1\pmod{m}$, то $g$ – первообразный корень по модулю $m$. Доказательство
. Если $g$ – не первообразный корень по модулю $m$, то найдётся натуральное число $d$, меньшее чем $\varphi(m)$, такое что $g^d\equiv 1\pmod{m}$. По предложению 5 $d|\varphi(m)$, а значит $d=q_1^{n_1}\cdots q_s^{n_s}$, где $0\leqslant n_i\leqslant k_i$ при всех $i=1,\ldots ,s$, причём при некотором $j$ будет $n_j\leqslant k_j-1$. Но тогда $d|\varphi(m)/q_j$ и $g^{\varphi(m)/q_j}\equiv 1\pmod{m}$. Противоречие. Теорема 11 доказана
. Отыскивать первообразные корни с помощью теоремы 11 рекомендуется только по простому модулю $p$, после чего разумнее находить (если это требуется) первообразные корни по модулям $p^{k}$ и $2p^{k}$, пользуясь процедурами, описанными в предыдущем параграфе. Итак, требуется разложить на простые множители число $p-1=2^kq_1^{k_1}\cdots q_s^{k_s}$ выбрать какое-нибудь число $g$ (кандидата в первообразные корни), причём необходимо $p\nmid g$ убедиться, что символ Лежандра $\displaystyle\left(\frac{g}{p}\right)=-1$ проверять, выполняется ли условие $g^{p-1/q_i}\not\equiv 1\pmod{p}$ для каждого $i=1,\ldots ,s$ Если все проверки пройдены успешно, то $g$ – первообразный корень по модулю $p$. Условие $\displaystyle\left(\frac{g}{p}\right)=-1$ является проверкой эквивалентного ему условия $g^{p-1/2}\not\equiv 1\pmod{p}$. Дело в том, что по критерию Эйлера $g^{p-1/2}\equiv \displaystyle\left(\frac{g}{p}\right)\pmod{p}$, а ненулевой символ Лежандра, если он не сравним с $1$, должен равняться $-1$. В качестве первого кандидата имеет смысл брать $g=2$. Нет необходимости рассматривать заведомые квадратичные вычеты, например $4$ или вообще какие бы то ни было квадраты. Число $-1$ является первообразным корнем по модулям $2,\ 3,\ 4,\ 6$ и ни по каким другим модулям его рассматривать не нужно, поскольку $(-1)^2\equiv 1\pmod{m}$ при любом $m$. Пример 6
. Найти первообразный корень по модулю $31$. Решение
. Разложим на простые множители $31-1=2\cdot 3\cdot 5$. Не будем брать в качестве кандидата число $2$, так как $31\equiv -1\pmod{8}$ и $\displaystyle\left(\frac{2}{31}\right)=1$. Зато $\displaystyle\left(\frac{-2}{31}\right)=-1$. Но $(-2)^{30/3}=(-2)^{10}=(-32)^2\equiv 1\pmod{31}$. Возьмём $3$ в качестве кандидата. Имеем
$$\left(\frac{3}{31}\right)=-\left(\frac{31}{3}\right)=-1.$$ Кроме того
$$3^{30/3}=(3^3)^3\cdot 3\equiv (-4)^3\cdot 3\equiv -64\cdot 3\equiv -6\not\equiv 1\pmod{31}$$
и
$$ 3^{30/5}=(3^3)^2\equiv (-4)^2\equiv 16\not\equiv 1\pmod{31}.$$
Значит $3$ – первообразный корень по модулю $31$. Пример 7
. Найти первообразный корень по модулю $1637$. Решение
. Разложим на простые множители $1637-1=2^2\cdot 409$. Возьмём 2 в качестве кандидата. Так как $1637\equiv 5\pmod{8}$, то $\displaystyle\left(\frac{2}{1637}\right)=-1$. Кроме того
$2^{1636/409}=16\not\equiv 1\pmod{1637}$. Значит $2$ – первообразный корень по модулю $1637$. Пример 8
. Найти первообразный корень по модулю $2\cdot 23^{19}$. Решение
. Достаточно найти нечётный первообразный корень по модулю $23^2$. Для начала найдём первообразный корень по модулю $23$. Разложим на простые множители $23-1=2\cdot 11$. Не будем брать в качестве кандидата число $2$, так как $23\equiv -1\pmod{8}$ и $\displaystyle\left(\frac{2}{23}\right)=1$. Зато $\displaystyle\left(\frac{-2}{23}\right)=-1$. Кроме того
$(-2)^{22/11}=4\not\equiv 1\pmod{23}$. Значит $-2$ – первообразный корень по модулю $23$. Теперь проверим, что $(-2)^{22}\not\equiv 1\pmod{23^2}$. Это действительно так, поскольку
$$(-2)^{22}-1=2^{22}-1=(2^{11}-1)(2^{11}+1)=2047\cdot 2049,$$ но $2047=23\cdot 89$, а значит, во-первых, $23$ не делит $2049$, а во-вторых, $23^2$ не делит $(-2)^{22}-1$. Это означает, что $-2$ является первообразным корнем и по модулю $23^2$. Но тогда число $23^2-2=527$ будет нечётным первообразным корнем по модулю $23^2$, а значит и по модулю $2\cdot 23^{19}$. Пользуясь следствием 13 можно решать сравнения некоторого вида. Допустим необходимо найти все решения сравнения
$$x^{17}\equiv 5\pmod{31}.$$
Мы знаем, что $3$ – первообразный корень по модулю $31$. Все его степени от нулевой до двадцать девятой образуют приведённую систему вычетов по модулю $31$ (всего в ней $\varphi(31)=30$ элементов). Находим $3^5=243\equiv -5\pmod{31}$, следовательно $5\equiv 3^{20}\pmod{31}$. Это связано с тем, что для любого первообразного корня
$g$ по любому простому модулю
$p$ выполнено
$-1\equiv g^{p-1/2}$. В этом легко убедиться, ведь для первообразного корня всегда выполнено $\displaystyle\left(\frac{g}{p}\right)=-1$, а $\displaystyle\left(\frac{g}{p}\right)\equiv g^{p-1/2}\pmod{p}$ по критерию Эйлера. При этом ни в какой другой степени от $0$ до $p-2$ первообразный корень не даст $-1$, поскольку по следствию 13 все его степени попарно не сравнимы по модулю $p$. Положим теперь $x\equiv 3^y\pmod{31}$. Мы можем это сделать, так как из самого условия задачи очевидно, что $x$ не делится на $31$, а значит сравним с одной (и только одной) из степеней первообразного корня (по следствию 13). Исходное сравнение теперь перепишется в виде
$$ 3^{17y}\equiv 3^{20}\pmod{31}.$$
По следствию 12 это равносильно сравнению уже по модулю $\varphi(31)=30$
$$17y\equiv 20\pmod{30}.$$ Решая это сравнение, находим $y\equiv 10\pmod{30}$, откуда $x\equiv 3^y\equiv -6\pmod{31}$. a-b
– положительное число, то a>b
. Если при сравнении чисел a и b разность a-b
– отрицательное число, то a Если неравенства записываются знаками < или >, то их называют строгими неравенствами. Если неравенства записывают знаками ≤ или ≥, то их называют нестрогими неравенствами. Примеры.
1.
Сравните числа а и b по их разности. а) a-b=-7. Решение.
Так как разность a-b – отрицательное число, то a б) a-b=4,5. Решение.
Так как разность a-b – положительное число, то a>b. в) a-b=0. Решение.
Так как разность a-b равна нулю, то a=b. 2.
Сравните данные числа. а) 0,099 и 0,1. Решение.
Десятичные дроби сравниваются поразрядно: из двух чисел больше то, которое содержит больше единиц высшего разряда. 0,099 < 0,1, так как 0<1 (сравнили десятые доли чисел). б) -5,43 и -5,6. Решение. -5,43 > -5,6, так как из двух отрицательных чисел больше то, модуль которого меньше. так как из двух дробей с одинаковыми знаменателями больше та, числитель которой больше, а меньше та, числитель которой меньше. так как из двух дробей с одинаковыми числителями больше та, знаменатель которой меньше, а меньше та, знаменатель которой больше. Решение.
Приведем дроби к общему знаменателю. Получаем: Теперь сравниваем дроби с одинаковыми знаменателями. Получаем: 3.
Записать в виде двойного неравенства: 6 < 12 и 12 < 15. Решение
. 6 < 12 < 15. Читают: двенадцать больше шести и меньше пятнадцати. 4.
— 4 ≤ х < 3. Решение:
-4; -3; -2; -1; 0; 1; 2. 5.
Задания для самостоятельного решения. 5.1
Сравните с нулем разность чисел а и b, если а) a 5.2.
Сравните данные числа. а) -2,467 и -2,476; б) 8,98 и 8,899; 5.3.
Выписать все целые числа, удовлетворяющие двойному неравенству: а) -5 ≤ х < 1; б) -3 < x ≤ 3; в) 4 < x < 9; г) -8 ≤ x ≤ -4. Ответы.
5.1.
а
.
a-b<0; 5.1.
б
.
a-b>0; 5.1.
в
.
a-b=0. 5.2.
а
.
-2,467 > -2,476; 5.2.б.
8,98 > 8,899; 5.3.а
-5; -4; -3; -2; -1; 0; 5.3.б.
-2; -1; 0; 1; 2; 3; 5.3.в.
5; 6; 7; 8; 5.3.г.
-8; -7; -6; -5; -4. Примеры. Решить уравнение. 1.
1,5х+4 = 0,3х-2. 1,5х-0,3х = -2-4. Собрали слагаемые, содержащие переменную, в левой части равенства, а свободные члены – в правой части равенства. При этом применяли свойство: 1,2х = -6. Привели подобные слагаемые по правилу: х = -6 :
1,2. Обе части равенства разделили на коэффициент при переменной, так как х = -5. Делили по правилу деления десятичной дроби на десятичную дробь: чтобы разделить число на десятичную дробь, нужно перенести запятые в делимом и делителе на столько цифр вправо, сколько их стоит после запятой в делителе, а затем выполнить деление на натуральное число:
6 :
1,2 = 60 :
12 = 5. Ответ:
5. 2.
3∙
(2х-9) = 4∙
(х-4). 6х-27 = 4х-16. Раскрыли скобки, используя распределительный закон умножения относительно вычитания: (a-b) ∙
c = a ∙
c-b ∙
c. 6х-4х = -16+27. Собрали слагаемые, содержащие переменную, в левой части равенства, а свободные члены – в правой части равенства. При этом применяли свойство: любое слагаемое уравнения можно перенести из одной части равенства в другую, изменив при этом знак слагаемого на противоположный.
2х = 11. Привели подобные слагаемые по правилу: чтобы привести подобные слагаемые, надо сложить их коэффициенты и полученный результат умножить на их общую буквенную часть (т.е. к полученному результату приписать их общую буквенную часть).
х = 11 :
2. Обе части равенства разделили на коэффициент при переменной, так как если обе части уравнения умножить или разделить на одно и то же отличное от нуля число, то получится уравнение, равносильное данному уравнению.
Ответ:
5,5. 3.
7х- (3+2х)=х-9. 7х-3-2х = х-9. Раскрыли скобки по правилу раскрытия скобок, перед которыми стоит знак «-»: если перед скобками стоит знак «-», то убираем скобки, знак «-» и записываем слагаемые, стоявшие в скобках, с противоположными знаками.
7х-2х-х = -9+3. Собрали слагаемые, содержащие переменную, в левой части равенства, а свободные члены – в правой части равенства. При этом применяли свойство: любое слагаемое уравнения можно перенести из одной части равенства в другую, изменив при этом знак слагаемого на противоположный.
4х = -6. Привели подобные слагаемые по правилу: чтобы привести подобные слагаемые, надо сложить их коэффициенты и полученный результат умножить на их общую буквенную часть (т.е. к полученному результату приписать их общую буквенную часть).
х = -6 :
4. Обе части равенства разделили на коэффициент при переменной, так как если обе части уравнения умножить или разделить на одно и то же отличное от нуля число, то получится уравнение, равносильное данному уравнению.
Ответ:
-1,5. 3 ∙
(х-5) = 7 ∙
12 — 4 ∙
(2х-11). Умножили обе части равенства на 12 – наименьший общий знаменатель для знаменателей данных дробей. 3х-15 = 84-8х+44. Раскрыли скобки, используя распределительный закон умножения относительно вычитания: чтобы разность двух чисел умножить на третье число, можно отдельно уменьшаемое и отдельно вычитаемое умножить на третье число, а затем из первого результата вычесть второй результат, т.е.
(a-b) ∙
c = a ∙
c-b ∙
c. 3х+8х = 84+44+15. Собрали слагаемые, содержащие переменную, в левой части равенства, а свободные члены – в правой части равенства. При этом применяли свойство: любое слагаемое уравнения можно перенести из одной части равенства в другую, изменив при этом знак слагаемого на противоположный.
11х = 143. Привели подобные слагаемые по правилу: чтобы привести подобные слагаемые, надо сложить их коэффициенты и полученный результат умножить на их общую буквенную часть (т.е. к полученному результату приписать их общую буквенную часть).
х = 143 :
11. Обе части равенства разделили на коэффициент при переменной, так как если обе части уравнения умножить или разделить на одно и то же отличное от нуля число, то получится уравнение, равносильное данному уравнению.
Ответ:
13. 5.
Решить самостоятельно уравнения: а)
3-2,6х = 5х+1,48; б)
1,6 ·
(х+5) = 4 ·
(4,5-0,6х); в)
9х- (6х+2,5) = — (х-5,5); 5а)
0,2; 5б)
2,5; 5в)
2; 5г)
-1. 1.
Раскрытие скобок, перед которыми стоит знак «+» или не стоит никакого знака. Если перед скобками стоит знак «+» или не стоит никакого знака, то убираем скобки, знак «+» и записываем слагаемые, стоявшие в скобках, без изменений. Примеры.
Раскрыть скобки. 1а) (-3х+4) = -3х+4; 1б) (2a-3b)+(-c-d) = 2a-3b-c-d; 1в) 7x+(-a-2b+5c-k) = 7x-a-2b+5c-k. 2.
Раскрытие скобок, перед которыми стоит знак «-». Если перед скобками стоит знак «-», то убираем скобки, знак «-» и записываем слагаемые, стоявшие в скобках, с противоположными знаками. Примеры.
Раскрыть скобки. 2а) — (4х-5) = -4х+5; 2б) - (-2a+c) — (b-3d) = 2a-c-b+3d; 2в) - (4k-m) — (-a+2b) = -4k+m+a-2b. 3.
Слагаемые, имеющие одинаковую буквенную часть, называются подобными слагаемыми
. Примеры подобных слагаемых: 5а и -а; 2с и -12с. Числовой множитель, стоящий перед буквенным множителем, называют коэффициентом
. Так, в выражении 5а коэффициент равен 5, а в выражении (-а) коэффициент равен (-1). Нахождение алгебраической суммы подобных слагаемых называется приведением подобных слагаемых
. Чтобы привести подобные слагаемые
, надо сложить их коэффициенты и полученный результат умножить на их общую буквенную часть (т.е. к полученному результату приписать их общую буквенную часть). Примеры.
Привести подобные слагаемые. 3а) 2а-7а+9а-6а = (2-7+9-6)а = -2а; 3б) -4m+6m-3m+4m = (-4+6-3+4) m = 3m; 3в) 5,2с-2,8с-6,4с+9с = (5,2-2,8-6,4+9)с = 5с. 4.
В алгебраическом выражении могут быть различного вида подобные слагаемые. В этом случае подобные слагаемые подчеркиваются одинаковыми линиями. Примеры.
Привести подобные слагаемые. 4а) -4а
+5с-11с-20а
= (-4-20)а+(5-11)с = -24а-6с; 4б) 3,2х
+5,6у-8х
-3у = (3,2-8)х+(5,6-3)у = -4,8х+2,6у; 4в) 8
m
-3k+7
m
-2k+12k+13
m
= (8+7+13) m+(-3-2+12) k = 28m+7k. 5.
Для преобразования алгебраических выражений с помощью раскрытия скобок используют распределительное свойство умножения: чтобы сумму чисел умножить на третье число, можно каждое слагаемое умножить на третье число и сложить результаты.
Примеры.
Раскрыть скобки. 5а) 2 (4х-5у) = 2 ∙
4х+2 ∙
(-5) = 8х-10у; 5б) -3 (4а+7с) = -3 ∙
4а-3 ∙
7с = -12а-21с; 5в) -6 (-а+4с) = -6 ∙
(-а) -6 ∙
4с = 6а-24с. 6.
Упростить алгебраическое выражение – это значит раскрыть скобки, выполнить указанные действия, привести подобные слагаемые. Примеры.
Упростить выражение. 6а) (3х+у) -2 (5х-у) = 3х
+у-10х
+2у = -7х+3у; 6б) 3х(а+1,5) -4ах = 3ах
+4,5х-4ах
= 4,5х-ах; 6в) -6 (х+у)+3 (2х-у) = -6х
-6у+6х
-3у = -9у. 7.
Примеры для самостоятельного решения
. Упростить: 7а) 4 (5-3а) — (11-а); 7б) 2 (3х-у) -6 (5х+3у); 7в) -2а(3с+4)+6ас; 7г) 5 (а-2с+1) -4 (-3+3с-а); 7д) –х(2у+7)+7 (х-4ху). Ответы.
7б) -24х-20у; 7г) 9а-22с+17; Вы перешли на эту страницу, чтобы получить составленный мною «Справочник по геометрии 7-9». В нём 415 пунктов (определения, теоремы и формулы с рисунками) на 48 страницах формата А4. По ссылке вы попадёте на мой ЯндексДиск , где вам будет предложено скачать (посмотреть) мой «Справочник по геометрии 7-9». Если вы распечатаете Справочник в виде книжки по 2 страницы на каждой стороне листа А4, то получится весьма компактная и удобная вещица, которая поможет вам в учёбе, в подготовке к ОГЭ или ЕГЭ. Желаю вам успехов! Не секрет, что при подготовке по математике к ОГЭ учащиеся испытывают бОльшие затруднения при решении задач модуля «Геометрия», причём не только второй части, но даже и при выполнении заданий первой части. Безусловно, чтобы чувствовать себя увереннее необходимо повторить ВЕСЬ теоретический материал геометрии 7-9. «Справочник по геометрии 7-9», несомненно, отлично вам в этом поможет! 1)
в
обычном электронном pdf файле
. Она стоит 200 рублей. Оплатить можно с помощью формы ниже. Оплата проводится самим сервисом Яндекс.Деньги, поэтому перевод денег осуществляется строго конфиденциально! После проверки получения денег я высылаю вам книгу на указанный вами электронный адрес. К книге отдельным файлом высылается памятка по решению задач на проценты. 2)
Книга «Как решать задачи на проценты» в 3d формате
. Что это за книга вы можете посмотреть в видео на этой странице ниже. Эта книга стоила 600 рублей, но теперь цена понижена в 2 раза потому что оказалось недоступным приложение к книге в виде тестов (тесты находились на иностранном сайте) — жаль, конечно, но все задачи, их решения и видео на месте, а это главное! Оплату проводит сервис Яндекс.Деньги — самый надежный и порядочный в мире. В форме оплаты вы введете свой электронный адрес, на который я и пришлю вам ссылку на скачивание книги и инструкцию. Также отдельно я пришлю вам памятку по решению задач на проценты. Если вы хотите научиться решать задачи на проценты, то полезной будет эта книга: смотрите видео ниже.
Дорогие учащиеся
, вы можете оплатить книгу и сами через уличный терминал. Далее: ВНИМАНИЕ!
Со своего компьютера отправляете мне письмо на адрес: at@сайт с какими-нибудь подробностями платежа из чека. Не забудьте написать свое имя и какую именно книгу вы оплатили. После проверки поступления денег я пришлю вам книгу в письме. С уважением Татьяна Яковлевна Андрющенко — автор сайта, на котором Вы находитесь. Чтобы решить систему линейных уравнений с двумя переменными методом сложения, надо: 1) умножить левую и правую части одного или обоих уравнений на некоторое число так, чтобы коэффициенты при одной из переменных в уравнениях стали противоположными числами;
2) сложить
почленно
полученные уравнения и найти значение одной из переменных;
3) подставить найденное значение одной переменной в одно из данных уравнений и найти значение второй переменной.
Если в данной системе коэффициенты при одной переменной являются противоположными числами, то решение системы начнём сразу с пункта 2). Примеры.
Решить систему линейных уравнений с двумя переменными методом сложения. Так как коэффициенты при у являются противоположными числами (-1 и 1), то решение начинаем с пункта 2). Складываем уравнения почленно и получим уравнение 8х = 24. Вторым уравнением системы можно записать любое уравнение исходной системы. Решаем 2–ое уравнение: 9-у = 14, отсюда у = -5. Сделаем проверку
. Подставим значения х = 3 и у = -5 в первоначальную систему уравнений. Ответ:
(3; -5). Мы получим равносильную систему уравнений, в которой 1-ое уравнение есть сумма двух уравнений прежней системы, а 2-м уравнением системы мы запишем 1-ое уравнение исходной системы (обычно записывают уравнение с меньшими коэффициентами
): Решаем последнее уравнение системы и получаем х = -2. Ответ:
(-2; 1). 3 ·
4 — 5у = 27. Упростим: 12 — 5у = 27, отсюда -5у = 15, а у = -3. Ответ:
(4; -3). Для решения системы линейных уравнений с двумя переменными методом подстановки поступаем следующим образом: 1) выражаем одну переменную через другую в одном из уравнений системы (х через у или у через х);
2) подставляем полученное выражение в другое уравнение системы и получаем линейное уравнение с одной переменной;
3) решаем полученное линейное уравнение с одной переменной и находим значение этой переменной;
4) найденное значение переменной подставляем в выражение (1) для другой переменной и находим значение этой переменной.
Примеры. Решить методом подстановки систему линейных уравнений. Мы получили уравнение: 3·
(7+у)+2у=16. Это уравнение с одной переменной у
. Решаем его. Раскроем скобки: 21+3у+2у=16. Собираем слагаемые с переменной у
в левой части, а свободные слагаемые — в правой. При переносе слагаемого из одной части равенства в другую меняем знак слагаемого на противоположный
. Получаем: 3у+2у=16-21. Приводим подобные слагаемые в каждой части равенства. 5у=-5. Делим обе части равенства на коэффициент при переменной
. у=-5:5; у=-1. Подставляем это значение у
в выражение х=7+у и находим х
. Получаем: х=7-1; х=6. Пара значений переменных х=6 и у=-1 является решением данной системы. Записывают: (6; -1). Ответ: (6; -1). Эти рассуждения удобно записывать так, как показано ниже, т.е. системы уравнений — слева друг под другом. Справа — выкладки, необходимые пояснения, проверка решения и пр. Задача 1.
Диагональ прямоугольника равна 16 и составляет со стороной угол 30°. Найти площадь прямоугольника. Решение.
Катет AD можно было найти иначе – через косинус ∠САD. Так как косинусом острого угла прямоугольного треугольника называется отношение прилежащего углу катета к гипотенузе, то отсюда следует: катет, прилежащий углу, равен произведению гипотенузы на косинус этого угла. У нас: AD=AC∙
cos30°; Подставим найденные значения в формулу площади прямоугольника. Задача 2.
Диагональ прямоугольника составляет с его стороной, равной 10 см, угол 60°. Найти периметр и площадь прямоугольника. Решение.
Задача 1.
Одна сторона прямоугольника меньше другой на 7 см, а диагональ прямоугольника равна 17 см. Найти периметр прямоугольника. AB 2 +AD 2 =BD 2 . Получаем: х 2 +(х+7) 2 =17 2 ⇒ х 2 +х 2 +14х+49=289; 2х 2 +14х-240=0; х 2 +7х-120=0, отсюда по теореме Виета х 1 =-15; х 2 =8. Следовательно, АВ=8 см, AD=8+7=15 см. Периметр прямоугольника: P□ = 2∙
(AB+AD); P□ = 2∙
(8+15); P□ = 46 см. Ответ:
46 см. Задача 2.
Периметр прямоугольника 94 см, а диагональ 37 см. Найти площадь прямоугольника. AB 2 +AD 2 =BD 2 . Получаем: х 2 +(47-х) 2 =37 2 ⇒ х 2 +47 2 -94х+ х 2 =1369; 2х 2 -94х+2209—1369=0; 2х 2 -94х+840=0. Делим обе части равенства на 2. Получаем: х 2 -47х+420=0. Найдем дискриминант. D=b 2 -4ac=47 2 -4∙1∙420=2209—1680=529=23 2 >0; 2 д.к. х 1 = (47-23)/2=12; х 2 = (47+23)/2=35. Так как АВ=х, то либо АВ=12, тогда AD=47-12=35; либо АВ=35, тогда AD=47-35=12. Таким образом, стороны прямоугольника равны 12 см и 35 см. Площадь прямоугольника S□ = AB∙
AD=12∙
35=420 (см 2). Ответ:
420 см 2 . Задача 3.
Стороны прямоугольника относятся как 3:
4, а площадь прямоугольника равна 108 см 2 . Найти диагональ прямоугольника. Так как S□ = AB∙
AD и по условию равна 108 см 2 , то можно составить уравнение: 3х∙
4х=108. Тогда 12х 2 =108, а разделив обе части равенства на 12, получаем: х 2 =9. Отсюда х=3, так как х – положительное число. Стороны прямоугольника Тогда АВ=3х=3∙
3=9 и AD=4х=4∙
3=12. Из прямоугольного треугольника BAD по теореме Пифагора найдем BD – искомую диагональ прямоугольника. BD 2 =AB 2 +AD 2 =9 2 +12 2 =81+144=225, отсюда BD=15 см. Ответ:
15 см. Задача 4.
Биссектриса одного из углов прямоугольника делит сторону прямоугольника пополам. Найдите диагональ прямоугольника, если его меньшая сторона равна 15 см. АС 2 =AB 2 +ВС 2 =15 2 +30 2 =225+900=1125, отсюда получаем: Задача 5.
В прямоугольнике точка пересечения диагоналей отстоит от меньшей стороны на 7 см дальше, чем от большей стороны. Диагональ прямоугольника равна 26 см. Найдите стороны прямоугольника. ОМ 2 +МА 2 =АО 2 или х 2 +(х+7) 2 =13 2 . Упрощаем равенство: х 2 +х 2 +14х+49=169; 2х 2 +14х-120=0; х 2 +7х-60=0. Корни этого приведенного квадратного уравнения удобно найти по теореме Виета. х 1 =-12, х 2 =5. Так как сторона выражается положительным числом, то ОМ=х=5 см. тогда ОК=5+7=12 (см). АК=ОМ=5 см и АМ=ОК=12 см – это половинки сторон прямоугольника. Тогда АВ=2∙
АК=10 см и AD=2∙
МА=24 см. Ответ:
10 см и 24 см. I.
Выражения, в которых наряду с буквами могут быть использованы числа, знаки арифметических действий и скобки, называются алгебраическими выражениями.
Примеры
алгебраических выражений: 2m -n; 3·
(2a + b); 0,24x; 0,3a -b ·
(4a + 2b); a 2 – 2ab; Так как букву в алгебраическом выражении можно заменить какими то различными числами, то букву называют переменной, а само алгебраическое выражение — выражением с переменной. II.
Если в алгебраическом выражении буквы (переменные) заменить их значениями и выполнить указанные действия, то полученное в результате число называется значением алгебраического выражения.
Примеры.
Найти значение выражения: 1) a + 2b -c при a = -2; b = 10; c = -3,5. 2) |x| + |y| -|z| при x = -8; y = -5; z = 6. Решение
. 1) a + 2b -c при a = -2; b = 10; c = -3,5. Вместо переменных подставим их значения. Получим: — 2+ 2 ·
10- (-3,5) = -2 + 20 +3,5 = 18 + 3,5 = 21,5. 2) |x| + |y| -|z| при x = -8; y = -5; z = 6. Подставляем указанные значения. Помним, что модуль отрицательного числа равен противоположному ему числу, а модуль положительного числа равен самому этому числу. Получаем: |-8| + |-5| -|6| = 8 + 5 -6 = 7. III.
Значения буквы (переменной), при которых алгебраическое выражение имеет смысл, называют допустимыми значениями буквы (переменной).
Примеры.
При каких значениях переменной выражение не имеет смысла? Решение.
Мы знаем, что на нуль делить нельзя, поэтому, каждое из данных выражений не будет иметь смысла при том значении буквы (переменной), которая обращает знаменатель дроби в нуль! В примере 1) это значение а = 0. Действительно, если вместо а подставить 0, то нужно будет число 6 делить на 0, а этого делать нельзя. Ответ: выражение 1) не имеет смысла при а = 0. В примере 2) знаменатель х — 4 = 0 при х = 4, следовательно, это значение х = 4 и нельзя брать. Ответ: выражение 2) не имеет смысла при х = 4. В примере 3) знаменатель х + 2 = 0 при х = -2. Ответ: выражение 3) не имеет смысла при х = -2. В примере 4) знаменатель 5 -|x| = 0 при |x| = 5. А так как |5| = 5 и |-5| = 5, то нельзя брать х = 5 и х = -5. Ответ: выражение 4) не имеет смысла при х = -5 и при х = 5. Пример:
5 (a – b) и 5a – 5b тожественно равны, так как равенство 5 (a – b) = 5a – 5b будет верным при любых значениях a и b. Равенство 5 (a – b) = 5a – 5b есть тождество.
Тождество
– это равенство, справедливое при всех допустимых значениях входящих в него переменных. Примерами уже известных вам тождеств являются, например, свойства сложения и умножения, распределительное свойство.
Замену одного выражения другим, тождественно равным ему выражением, называют тождественным преобразованием или просто преобразованием выражения. Тождественные преобразования выражений с переменными выполняются на основе свойств действий над числами.
Примеры.
a)
преобразуйте выражение в тождественно равное, используя распределительное свойство умножения: 1) 10·(1,2х + 2,3у); 2) 1,5·(a -2b + 4c); 3) a·(6m -2n + k). Решение
. Вспомним распределительное свойство (закон) умножения: (a+b)·c=a·c+b·c
(распределительный закон умножения относительно сложения: чтобы сумму двух чисел умножить на третье число, можно каждое слагаемое умножить на это число и полученные результаты сложить). 1) 10·(1,2х + 2,3у) = 10 · 1,2х + 10 · 2,3у = 12х + 23у. 2) 1,5·(a -2b + 4c) = 1,5а -3b + 6c. 3) a·(6m -2n + k) = 6am -2an +ak. б)
преобразуйте выражение в тождественно равное, используя переместительное и сочетательное свойства (законы) сложения: 4) х + 4,5 +2х + 6,5; 5) (3а + 2,1) + 7,8; 6) 5,4с -3 -2,5 -2,3с. Решение.
Применим законы (свойства) сложения: a+b=b+a
(переместительный: от перестановки слагаемых сумма не меняется). 4) х + 4,5 +2х + 6,5 = (х + 2х) + (4,5 + 6,5) = 3х + 11. 5) (3а + 2,1) + 7,8 = 3а + (2,1 + 7,8) = 3а + 9,9. 6) 6) 5,4с -3 -2,5 -2,3с = (5,4с -2,3с) + (-3 -2,5) = 3,1с -5,5. в)
преобразуйте выражение в тождественно равное, используя переместительное и сочетательное свойства (законы) умножения: 7) 4 ·
х ·
(-2,5); 8) -3,5 ·
2у ·
(-1); 9) 3а ·
(-3) ·
2с. Решение.
Применим законы (свойства) умножения: a·b=b·a
(переместительный: от перестановки множителей произведение не меняется). 7) 4 ·
х ·
(-2,5) = -4 ·
2,5 ·
х = -10х. 8) -3,5 ·
2у ·
(-1) = 7у. 9) 3а ·
(-3) ·
2с = -18ас. Если алгебраическое выражение дано в виде сократимой дроби, то пользуясь правилом сокращения дроби его можно упростить, т.е. заменить тождественно равным ему более простым выражением.
Примеры.
Упростите, используя сокращение дробей. Решение.
Сократить дробь — это значит разделить ее числитель и знаменатель на одно и то же число (выражение), отличное от нуля. Дробь 10) сократим на 3b
; дробь 11) сократим на а
и дробь 12) сократим на 7n
. Получаем: Алгебраические выражения применяют для составления формул. Формула – это алгебраическое выражение, записанное в виде равенства и выражающее зависимость между двумя или несколькими переменными.
Пример: известная вам формула пути s=v·t
(s — пройденный путь, v — скорость, t — время). Вспомните, какие еще формулы вы знаете.Наибольший общий делитель
Наименьшее общее кратное
Алгоритм Евклида
Решение в целых числах уравнения $px+qy=r$
Решение линейного диофантова уравнения от любого числа неизвестных
Простые числа
Бесконечность множества простых чисел
Решето Эратосфена
Основная теорема арифметики (единственность разложения на простые)
Мультипликативные функции
Определение и свойства мультипликативных функций. Свёртка Дирихле
Примеры мультипликативных функций
Функция Мёбиуса. Формула обращения Мёбиуса
Функция Эйлера
Формула включений и исключений
Ещё о мультипликативности функции Эйлера
Сравнения
Классы вычетов. Полная и приведённая системы вычетов
Сравнения и основные их свойства
Теорема Эйлера
Обратный элемент по модулю $m$
Китайская теорема об остатках
Теорема Лагранжа
Теоремы Ферма и Вильсона, символ Лежандра, критерий Эйлера
Свойства символа Лежандра. Лемма Гаусса. Квадратичный закон взаимности
Вычисление символа Лежандра. Символ Якоби
Лемма Гензеля
Первообразные корни
Существование первообразных корней по простому модулю
Первообразные корни по модулю $2^{k}$
Отсутствие первообразных корней по модулям, отличным от $2,\ 4,\ p^{k}$ и $2p^{k}$ с нечётным простым $p$
Существование первообразных корней по модулям $p^{k}$ и $2p^{k}$ с нечётным простым $p$
Нахождение первообразных корней
Решение сравнений при помощи первообразных корней
Задачи на проценты приходится решать всем учащимся с 5-го по 11 класс (а также их родителям!) не только в классе и дома, но и на экзаменах: переводных, ОГЭ и ЕГЭ. Научиться решать такие задачи вам поможет моя книга, которая так и называется: «Как решать задачи на проценты». Книга содержит теоретический материал по теме: «Проценты», более 100 задач с подробными решениями, а также 16 видео решений различных задач по данной теме. Вы можете приобрести книгу в одном из представленный форматов:
Найдём х и подставим его значение во 2-ое уравнение.
Примечание
. Проверку можно сделать устно и не записывать, если наличие проверки не оговорено в условии.
Если мы умножим 1-ое уравнение на (-2), то коэффициенты при переменной х станут противоположными числами:
Сложим эти равенства почленно.
Находим у
из 1-го уравнения и полученное значение подставляем во 2-ое.
Сделаем коэффициенты при переменной у
противоположными числами. Для этого все члены 1-го уравнения умножим на 5, а все члены 2-го уравнения на 2.
Подставим значение х=4 во 2-ое уравнение.
Выразим х
через у из 1-го уравнения. Получим: х=7+у. Подставим выражение (7+у) вместо х
во 2-ое уравнение системы.
1 способ.
Площадь прямоугольника найдем по формуле: S = ab (площадь прямоугольника равна произведению его длины на ширину). Для этого нам нужно найти стороны прямоугольника. Рассмотрим прямоугольный ∆ADC, в котором искомые стороны прямоугольника AD и CD являются катетами. Гипотенуза АС=16, острый ∠САD=30°. Катет, лежащий против угла 30°, равен половине гипотенузы. Следовательно, CD=16:2=8. Второй катет AD найдем по теореме Пифагора: AD 2 +CD 2 =AC 2 . Подставляем значения. AD 2 +8 2 =16 2 ; AD 2 +64=256; AD 2 =256-64; AD 2 =192;
2 способ.
Пусть в прямоугольнике ABCD диагональ АС составляет угол 30° со стороной AD. Мы знаем, что диагональ прямоугольника делит прямоугольник на два равных треугольника. Рассмотрим один из этих треугольников – прямоугольный ∆ ADC (∠ADC=90°) CD – катет, противолежащий углу 30°, поэтому этот катет равен половине гипотенузы, т.е. CD = АС :
2 = 16 :
2 = 8 (см). Второй острый угол рассматриваемого прямоугольного ∆ ADC – угол AСD равен 60° (90°-30°=60°). Площадь треугольника ADC равна половине произведения двух его сторон АС и CD на синус угла между ними. Тогда площадь прямоугольника равна произведению АС и CD на синус угла между ними:
3 способ
основан на том, что площадь прямоугольника можно найти как половину произведения его диагоналей на синус угла между ними
. Проведем вторую диагональ BD и обозначим точку пересечения диагоналей через О. Углом между двумя пересекающимися прямыми считают меньший из образовавшихся углов.
У нас это угол АОВ. Обозначим его через α. Найдем градусную меру угла α. Так как диагонали прямоугольника равны и точкой пересечения делятся пополам, то ∆АОВ – равнобедренный с углами при основании по 60°. На самом деле: ∠ОАВ=90°-∠САD=90°-30°=60°. Третий угол треугольника АОВ, т.е. угол α также равен 60° (считали: 180°-60°-60°). Площадь прямоугольника:
Периметр прямоугольника P□ = 2 (a+b), S□ = ab, где a и b – стороны прямоугольника. Нам известна лишь одна сторона: а = 10. Найдем вторую сторону, как неизвестный катет прямоугольного треугольника, противолежащий углу 60°. Так как тангенс острого угла прямоугольного треугольника равен отношению противолежащего катета к прилежащему
, то b = a ∙ tg60°. Подставляем значения и получаем:
Решение.
Пусть АВ=х. Тогда AD=х+7. Зная, что диагональ BD=17, используем теорему Пифагора и составим уравнение:
Решение.
Периметр прямоугольника P□ = 2∙
(AB+AD) = 94, следовательно, (AB+AD)=47. Пусть АВ=х. Тогда AD=47-х. Зная, что диагональ BD=37, используем теорему Пифагора и составим уравнение:
Решение.
Обозначим одну часть через х. Тогда АВ=3х. Тогда AD=4х.
Решение.
Итак, в прямоугольнике ABCD биссектриса АК делит сторону ВС пополам. АВ=15 см. Требуется найти диагональ АС прямоугольника. В прямоугольном треугольнике АВК один из острых углов равен 45° (биссектриса АК делит прямой угол пополам: ∠ВАК=∠КАD=45°). Тогда и второй острый угол треугольника АВК равен 45°, т.е. ∠АКВ=45°. Углы при основании ∆АВК равны, следовательно, ∆АВК – равнобедренный. Это означает, что ВК=АВ=15 см. А так как биссектриса АК по условию разделила сторону ВС пополам, то ВС=2∙
ВК=30 см. Стороны прямоугольника 15 см и 30 см. Из прямоугольного треугольника АВС по теореме Пифагора найдем АС – искомую диагональ прямоугольника.
Решение.
Пусть точка О – пересечение диагоналей прямоугольника ABCD отстоит от стороны AD на х см, тогда от стороны АВ точка О будет отстоять на (х+7) см, т.е ОМ=х и ОК=х+7. Так как диагонали прямоугольника равны и точкой пересечения делятся пополам, то АО=АС:
2=26:
2=13 (см). Заметим, что МА=ОК. На основании теоремы Пифагора из прямоугольного треугольника АМО получаем равенство:
IV.
Два выражения называются тождественно равными, если при любых допустимых значениях переменных соответственные значения этих выражений равны.
(а-b)·c=a·с-b·c
(распределительный закон умножения относительно вычитания: чтобы разность двух чисел умножить на третье число, можно умножить на это число уменьшаемое и вычитаемое отдельно и из первого результата вычесть второй).
(a+b)+c=a+(b+c)
(сочетательный: чтобы к сумме двух слагаемых прибавить третье число, можно к первому числу прибавить сумму второго и третьего).
(a·b)·c=a·(b·c)
(сочетательный: чтобы произведение двух чисел умножить на третье число, можно первое число умножить на произведение второго и третьего).