Дискретно-непрерывная математика (стр. 24 )

Задача 54. Сформулировать получаемые из об­щего признака равноостаточности Паскаля признаки равноостаточности при делении:

а) на 2, 5 и 10;

б) на 4, 20 и 25;

в) на 3 и 9;

г) на 11;

д) на 7.

Задача 55. Пусть в последовательности (12)

r1 есть остаток от деления 100 на т,

r2 » » » 100 r1 на т,

r3 » » » 100 r2 на т

и т. д.

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

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

Задача 57. Убедиться в том, что процесс построения чисел

А0=А, А1=f (А0), А2 =f(А1)…

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

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

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

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

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

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

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

а) φ (т)= 10;

б) φ (т)= 8.

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

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

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

Задача 67. Функция

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

Проверить это обстоятельство.

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

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

Задача 70. Доказать, что (п13 — п) 2730.

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

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

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

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

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

а) 5х + 7у = 9;

б) 25х + 13 у = 8.

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

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

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

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

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

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

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

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

Решение тестовых задач

1. 0 = а∙0 при любом а.

2. а = 1∙а, значит, а 1.

3. Пусть 1а. Это значит, что 1 = ас при неко­тором целом с. Отсюда следует, что |a|≤l. А так как а ≠ 0, должно быть а = 1.

4. Достаточно взять любое с > 1 и положить b = ас.

5. В качестве такого b можно взять, например, 2а. Пусть при этом для некоторого с и 2а с и с а. Это значит, что найдутся такие d1 и d2, что 2а = d1c и с = d2a. Отсюда следует, что 2а = d1d2a или после сокращения на а,

2 = d1d2.

Но при целых d1 и d2 такое равенство возможно лишь в случае, когда одно из этих чисел равно 1, а другое 2. Если d1 = 1, то с = 2а = b; если же d2= 1, то с = а.

6. Доказательства ничем не отличаются от доказательств в случае обычной делимости

7. Пусть п — некоторое фиксированное число, большее единицы. Положим , если найдется такое целое с, что а = bс и с ≤ п Справедливость теорем, аналогичных теоремам 1, 3 и 4, проверяется без труда. Однако если мы возьмем а = пb и b = пс, то . В этом случае а = п2с, а так как п2 > п, делимостьне имеет места Точно также не имеет места делимость

8 а) Пусть имеются два минимальных числа а1 и а2. В силу дихотомичности либо а1 ≥ a2, либо а2 ≥ а1. Если а1 ≥ а2, то из минимальности a1 следует, что а1 = а2. Если же а2 ≥ а1, то а1 = а2 следует из минимальности а2.

б) Пусть а — некоторое число, a b1 и b2 — два непосред­ственно предшествующих ему числа По дихотомичносги должно быть либо b1 ≥ b2, либо b2 ≥ b1. Пусть, для определенности, b1 ≥ b2. Мы имеем а так как число b2 непосредственно предшествует числу а, должно быть либо b1= а, либо, b1 = b2. Но по условию b1 ≠ а; значит, b1 = b2, и требуемая единственность доказана.

в) Непосредственно следующим за а числом называется такое b, что а следует либо с = b, либо с = а

Предположим, что некоторое а не имеет непосредственно следующего за ним числа. Это значит, что для любого ап ≥ а и отличного от а найдется такое an+1, отличное как от ап, так и от а, что an≥an+1≥a. Возьмем теперь произвольное а1 ≥ а и отличное от а (в силу 2° это сделать можно) и, исходя из него построим бесконечную последовательность различных чисел

Существование же этой последовательности противоречит 4° Следовательно, непосредственно следующее число существует. Единетвенность его устанавливается при помощи дихотомичности подобно тому как это делалось в пп а) и б)

9. Остается в силе транзитивность (3°), неограниченности множества чисел (5°), свойство 4° и существование непосредственно предшествующего числа (6°) Дихотомичность заменяется трихотомичностыо (либо а > b, либо b > a, либо а = b.

Становится неверным свойство рефлексивности (1°), ибo а> а всегда неверно.

Что же касается, наконец, утверждения 2°, то формально онo остается в силе (хотя, быть может, и выглядит несколько пародоксально)

В самом деле, говоря строго, это утверждение в нашем случае формулируется так: для любых натуральных чисел а и b из а > b и b > а следует а = b

Предположим, что это высказывание неверно. Тогда найдутся такие натуральные числа а и b, что одновременно будет и а>b и b> а, и а≠ b, а этого не может быть Полученное противоречие доказывает истинность нашего утверждения

10. Пусть множество упорядочено отношением , обладающим свойствами 1° — 7°. Как уже было установлено, оно обладает минимальным элементом. Обозначим этот элемент через a0. Из результатов задачи 8 следует, что каждый элемент обладает непосредственно следующим. Обозначим непосредственно следующий за a0 элемент через a1, непосредственно следующий за a1 через а2 и т. д. В итоге мы получаем последовательность