Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

§ 5. Делимость степеней

1. Начнем с описания процесса, который можно было бы назвать "очень общим признаком равно-остаточности".

Пусть k - некоторое натуральное число и r есть остаток от деления tk на m:

tk = mq + r (0 ≤ r < m).

По следствию теоремы 20 (см. п. 3 § 2) при любом n числа rn и tkn при делении на m также должны быть равно-остаточными.

Составим теперь для произвольного числа А его разбиение на k-значные "грани" справа налево, т. е. представим его в виде


где

0 ≤ ai < tk при i = 0, 1,..., n

и положим


Ясно, что, как и ранее в аналогичных случаях, процесс построения чисел

A0 = A, A1 = f(A0), A2 = f(A1),...

является признаком равно-остаточности.

Задача 57. Убедиться все-таки в том, что это действительно так.

Задача 58. Полагая t = 10 и k = 2, найти остаток от деления числа 1 048 576 на 7.

Задача 59. Убедиться в том, что только что описанный признак равноостаточности является лишь более явной формой того обобщения признака Паскаля, которое было упомянуто в задаче 56.

2. Говоря формально, при составлении в п. 1 общего признака равноостаточности мы пользовались свойствами степеней, относящимися к их делимости. Однако вопрос о делимости степеней по существу является вопросом о делимости некоторых произведений. Поэтому и решить этот вопрос в принципе удалось на основе результатов § 2. Вместе с тем практическая реализация полученного признака равно-остаточности для тех или иных комбинаций значений чисел t и m может приводить к крупным значениям k и r, так что вычисление значений функции f может потребовать выполнения значительных вычислений, возможно даже превосходящих по объему выкладки по непосредственному делению на m.

Ясно, что вычисление значений функции f оказывается тем проще, чем меньшими будут значения чисел k и r. Разумеется, наиболее удобным оказывается в этом отношении тот случай, когда r - 1. Тогда значение f получается в результате выполнения наименее трудоемкого действия: сложения.

Согласно теореме 22 этот случай (r = 1) имеет место тогда и только тогда, когда (tk - 1) m или, иными словами, когда tk при делении на m дает в остатке 1. Встает вопрос: найдется ли при данных t и m такое k, что (tk - 1) m?

Все сказанное приводит к необходимости заняться изучением делимости степеней несколько более подробно.

3. Расширим несколько наши познания в области теории чисел.

Теорема 24 (теорема Ферма).Если число р простое, то разность ар - а делится на р.

Не следует путать эту так называемую "малую теорему Ферма" с "великой теоремой Ферма". Последняя утверждает, что при целом n > 2 не существует таких целых а, b и с, что аn + bn = cn. Несмотря на многочисленные попытки, великая теорема Ферма до сих пор не доказана и не опровергнута.

Следствие. Если р - простое и а не делится на р, то ар-1 - 1 делится на р.

Задача 60. Привести пример, показывающий, что как теорема 24, так и ее следствие для составного р, вообще говоря, неверны.

Задача 61. Доказать теорему Ферма, опираясь на результат задачи 26.

Пусть натуральное число m имеет каноническое разложение:


положим


Формулы (5.1) и (5.2) ставят в соответствие каждому натуральному числу m некоторое вполне определенное число φ(m). Это значит, что мы можем говорить о функции φ от натурального аргумента.

Определение. Определенная выше функция φ называется функцией Эйлера.

Функция Эйлера играет исключительно важную роль во многих вопросах теории чисел. Даже в этой книжке будет указано несколько применений этой функции.

Теорема 25. При взаимно простых m1 и m2 имеет место равенство

φ(m1m2) = φ(m1)φ(m2).

Задача 62. Вычислить φ(12), φ(120), φ(1000).

Задача 63. Определить все числа m, для которых:

а) φ(m) = 10;

б) φ(m) = 8.

Задача 64. Доказать, что не существует такого m, для которого φ(m) = 14.

Задача 65. Показать, что φ(m) равно числу натуральных чисел, взаимно простых с m и меньших m. Это свойство функции Эйлера является чрезвычайно важным. Его часто принимают за определение этой функции.

Теорема 26 (теорема Эйлера). Если числа а и m взаимно просты, то аφ(m) - 1 делится на m.

Остатки при делении одного и того же делимого на различные делители связаны между собой достаточно сложным образом. Из теоремы Эйлера можно получить принципиально важную для нас зависимость остатков от деления на взаимно простые множители и от деления на их произведение.

Задача 66. Пусть (m1,m2) = 1, а a1 и а2 - числа, равно-остаточные с А при делении соответственно на m1 и m2. Тогда равно-остаточным с А при делении на m1m2 будет число


4. На основании установленных фактов мы можем сформулировать общий признак равно-остаточности для произвольного делителя т в произвольной системе счисления t в той явной и достаточно удобной форме, о которой говорилось в п. 1.

Напомним снова, что всякий признак равноостаточности есть алгорифм, т. е. некоторый процесс, и потому всякое его описание должно носить характер развивающегося повествования.

Итак, пусть нам даны числа m и t. Представим m в виде такого произведения m = m1m2, что (m1,t) = 1, и для некоторого показателя k имеет место делимость tk m2. Согласно теореме 18 такое представление возможно. В силу задачи 66 вопрос о равно-остаточности при делении на m1m2 может быть сведен к аналогичным вопросам для деления на m1 и m2. Но признак равно-остаточности на m2 содержится в теореме 21, а признак равно-остаточности на m1 - в теореме 22. После применения этих признаков равно-остаточности следует воспользоваться результатом задачи 66.

Например, в случае нахождения признака равно-остаточности при делении на 12 в десятичной системе счисления, очевидно, m1 = 3, m2 = 4 и k = 2.

Описанный процесс является общим признаком равно-остаточности в том смысле, что по любому m он выдает некоторый конкретный признак равно-остаточности. Это вытекает из алгорифмичности предоставления числа m в форме, указываемой в теореме 18, а сама эта алгорифмичность следует из алгорифмичности построения канонического разложения чисел (см. п. 9 § 3) .

Нам остается сформулировать в явном виде указанный признак равно-остаточности при делении на m1, пользуясь возможностью определить показатель k на основании теоремы Эйлера.

5. Применяя доказанные теоремы, построим несколько общих признаков делимости и равно-остаточности.

Фиксируем натуральное m и представим число А в виде


где

0 ≤ a0, a1, a2, ...., ak ≤ 10φ(m)

т. е. все ai (i = 0, 1, ..., k) являются φ(m)-значными числами.

Функция


определяет, как нетрудно проверить, некоторый общий признак равно-остаточности.

Задача 67. Проверить это обстоятельство.

Теорема 27. Если числа а и m взаимно просты, а числа k1 и k2 равно-остаточны при делении на φ(m), то числа ak1 и ak2 равно-остаточны при делении на m.

Задача 68. Сформулировать получаемые на основе этого общего признака равно-остаточности конкретные признаки равно-остаточности при делении на 7, 11 и 13.

Задача 69. Сформулировать аналогичный общий признак равно-остаточности для произвольной Личной системы счисления. Убедиться в том, что получаемый так общий признак равно-остаточности по своей формулировке не зависит от основания системы счисления t.

Задача 70. Доказать, что (n13 - n) 2730.

6. Построенный общий признак равно-остаточности не является во многих случаях, так сказать, "достаточно экономным", так как число φ(m) может, вообще говоря, оказаться довольно большим.

Поэтому, с одной стороны, при пользовании этим признаком приходится складывать большие числа, а с другой стороны, φ(m)-значные числа при этом приходится делить на т непосредственно (или же пользоваться каким-нибудь другим признаком делимости и равно-остаточности). Желательно поэтому попытаться взять вместо φ(m) другой, меньший показатель. В ряде случаев это удается сделать. Например, при m = 37 вместо φ(m) = 36 можно взять показатель 3, ибо 1000 при делении на 37 дает в остатке единицу; при m = 11 вместо φ(m) = 10 можно взять показатель 2 и т. д.

Определение. Наименьшее число δ, для которого аδ при делении на m с остатком дает в остатке 1, называется показателем, которому принадлежит число а при делении на m с остатком.

Чаще это число принято называть показателем, которому принадлежит число а по модулю m.

Очевидно, каковы бы ни были взаимно простые числа а и m, показатель δ, которому принадлежит а при делении на m, не превосходит φ(m). Этот показатель и можно взять вместо φ(m) в формулировке общего признака равно-остаточности из п. 5.

Задача 71. Модифицировать построенный общий признак делимости, используя вместо φ(m) показатель, которому принадлежит 10 при делении на m с остатком.

Задача 72. То же для t-ичной системы счисления.

7. Показатель, которому принадлежит число а при делении на m, может, вообще говоря, быть и равным φ(m). Например, последовательностью остатков от деления степеней числа 2 на 11 будет

2, 4, 8, 5, 10, 9, 7, 3, 6, 1,

так что при делении на 11 число 2 принадлежит показателю 10. Значит, для применения признака равноостаточности из п. 5 в этом случае приходится брать k = 10 = φ(11).

Однако во многих случаях удается обходиться показателем 1/2φ(m). Пусть, например, m есть степень простого числа: m = pα и р ≠ 2. Тогда φ(m) = pα-1 (р - 1), и теорема Эйлера приобретает вид: для (а, р) = 1 должно быть (аpα-1(p-1) - 1)

рα. Так как число pα-1(р - 1) четное, последнее делимое есть разность квадратов, и мы имеем


Так как р ≠ 2, оба сомножителя одновременно на р делиться не могут. Значит, на рα делится либо


либо


В первом случае мы оказываемся в условиях теоремы 23 с k = 1/2φ(m), а во втором - в условиях теоремы 22 с тем же k = 1/2φ(m).

8. Применения функции Эйлера и теоремы Эйлера не ограничиваются признаками делимости. Например, при их помощи можно решать уравнения в целых числах.

Теорема 28.Если числа а и b взаимно просты, то уравнение

ax + by = c (5.3)

всегда разрешимо в целых числах, и целыми его решениями будут все пары чисел (xt,yt), где



(t - любое целое число).

Задача 73. Доказать теорему, аналогичную теореме 28, не предполагая взаимной простоты чисел а и b.

Задача 74. Найти способ решения уравнений вида (5.3) в целых числах на основе результата задачи 29, б).

Задача 75. Решить в целых числах уравнения:

а) 5x + 7y = 9;

б) 25x + 13y = 8.

9. Теорема 29.Пусть m взаимно просто с 10 и k равно-остаточно с 10φ(m)-1 при делении на m. Тогда числа

10а + b и a + kb

равно делимы на m.

Опираясь на эту теорему, можно построить следующий общий признак делимости. Обозначим через k остаток от деления 10φ(m)-1 на m с остатком, представим произвольное число А в виде

10а + b (0 ≤ b < 10)

и положим


Если k велико (близко к m), то вместо него в формулировке соответствующего признака целесообразно брать k - m.

Задача 76. Проверить для функции F выполнение условий а)-в) из п. 10 § 3 и г*) из п. 15 § 3.

Задача 77. На основании только что построенного общего признака делимости вывести признак делимости на числа 17, 19, 27, 29, 31 и 49.

Задача 78. Построить аналогичный общий признак делимости, представляя произвольное натуральное число в виде

100а + b (0 ≤ b < 100),

и вывести из него признаки делимости на 17, 43, 49,67, 101, 199.

Задача 79. Построить аналогичный общий признак делимости в t-ичной системе счисления.

Задача 80. На основании построенного общего признака делимости вывести конкретные признаки делимости:

а) на число 21 в восьмеричной системе счисления;

б) на число 31 в двенадцатеричной системе счисления.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Зачем математики ищут простые числа с миллионами знаков?

Задача построения новых оснований математики - унивалентные основания

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru