Упражнения

Раздел 2.1.1

1. Завершите доказательство предложения 2.1.2.

2. Пусть А, В и С обозначают множества.

a. Покажите, что (объединение дистрибутивно относительно пересечения).

b. Покажите, что .

c. Покажите, что множества попарно не пересекаются .

3. (Индукция.) Пусть утверждение о натуральном числе п. Допустим, что любое непустое множество натуральных чисел имеет наименьший элемент (это принцип полной упорядоченности, доказательство которого дано в разд. 2.2.1). Покажите, что если справедливо и из справедливости вытекает справедливость то справедливо для любого . [Указание. Если нет, то множество не выполняется} имеет наименьший элемент

4. (Законы Де Моргана.) Для данного множества положим . Пусть А, В - два подмножества множества S. Докажите, что имеют место следующие равенства множеств:

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

a. Докажите, что .

b. Чему равно для произвольного множества А?

c. Докажите, что для любых множеств А, В и С.

6. (Принцип включения и исключения.) Если S - конечное множество, то число элементов множества S обозначается Покажите, что для конечных множеств А и В имеем По индукции это соотношение может быть распространено на случай

7. (Парадокс Рассела.) Множества могут содержать множества в качестве элементов. Пусть В — множество — множество и Приведите рассуждения, показывающие, что В истинно (см. также Историческое замечание 1).

аздел 2.1.2

1. Завершите доказательство предложения 2.1.4.

2. а. Покажите, что является отношением эквивалентности на Z и что классом эквивалентности целого числа а служит множество

b. Покажите, что множество классов эквивалентности равно

3. Для различных множеств S (определенных ниже), проверьте следующие бинарные отношения на рефлексивность, симметричность и транзитивность:

a. тогда и только тогда, когда .

b. тогда и только тогда, когда нацело делится на 5.

c. тогда и только тогда, когда четно.

d. тогда и только тогда, когда нечетно.

4. Определите, какие из бинарных отношений в упр. 3 являются отношениями эквивалентности, если такие среди них есть, и опишите соответствующие классы эквивалентности.

5. Пусть Проверьте следующие бинарные отношения на рефлексивность, симметричность и транзитивность:

6. Дано разбиение множества Перечислите упорядоченные пары в соответствующем отношении эквивалентности.

7. Вычислите число всех возможных разбиений -элементного множества; -элементного множества.

Раздел 2.1.3

Обозначение в упр. 2 и 3: для натурального числа положим — множество из элементов;

1. Завершите доказательство предложения 2.1.9.

2. Покажите по индукции, что множество всех биекций множества из элементов содержит элементов.

3. Покажите по индукции, что множество всех подмножеств имеет элементов.

4. Покажите, что логарифм по любому основанию — R является биекцией. Чему равна функция

5. Найдите бесконечное множество S и функцию такую, что

a. взаимно однозначна, но не на.

отображает на, но не взаимно однозначна.

6. Пусть — функция Покажите, что для всех подмножеств А к В множества S и,

в частности, тогда и только тогда, когда взаимно однозначна.

7. Пусть — функции.

a. Докажите, что если функция взаимно однозначна, то взаимно однозначна и .

b. Найдите пример, когда взаимно однозначна, но таковой не является.

c. Докажите, что если функция отображает на, то этим свойством обладает и .

d. Найдите пример, когда до отображает на, но этим свойством не обладает.

8. Пусть — функция Определим бинарное отношение q на S правилом: тогда и только тогда, когда Докажите, что является отношением эквивалентности.

Раздел 2.2.1

1. Покажите, что не каждое непустое подмножество вещественных чисел имеет минимальный и максимальный элемент.

2. Покажите, что если то

3. Покажите, что если , то для любых .

4. Покажите, что если а то . (Указание. Используйте теорему 2.2.3.)

5. Покажите, что если а и b оба ненулевые, то — наименьшее общее кратное чисел а и b.

6. Докажите часть b теоремы 2.2.4. (Указание. Сначала покажите, что любое решение однородного уравнения имеет вид для некоторого .)

7. Покажите, что для всякого целого

8. Докажите, что если то

9. Пусть — целые числа. Покажите, что уравнение имеет целое решение тогда и только

тогда, когда b, где .

10. Воспользуемся рядами Фарея для доказательства частного случая теоремы 2.2.3. А именно если , то целые числа удовлетворяющие соотношению могут быть получены из ряда Фарея

a. Определение. Ряд Фарея порядка N, обозначаемый это множество всех приведенных дробей между 0 и 1, знаменатели которых N, расположенных в порядке возрастания. приведена, если Например, ряд Фарея порядка 3 равен

b. Построение рядов Фарея. Для получения в общем случае начинаем с и повторяем следующую операцию столько раз, сколько потребуется (все знаменатели должны быть меньше или равны ):

Вставить между двумя соседними дробями (Новая дробь называется медиантой дробей Например, чтобы вычислить первый шаг дает нам один новый элемент между и 1/1:

а следующий (последний) дает еще два:

Отметим, что для получения из мы вставляем дробь (а между двумя соседними дробями ряда знаменатели которых в сумме дают N. Например, чтобы получить из элементов ряда мы просто вставляем 1/4 и 3/4 (почему не ) в соответствии со сформулированным Правилом:

c. Проверьте, что если и если все значения неотрицательны, то

d. Докажите по индукции, что если — две соседние дроби (на любом шаге построения), то

(Указание. Изначально это верно; посмотрите, что случится, когда вставляется новая медианта, и проверьте, что получен инвариант для всех шагов построения.)

e. Постройте F? и получите два решения уравнения

Раздел 2.2.2

1. Последовательность Фибоначчи определяется равенствами Сколько операций нужно выполнить, чтобы вычислить Чему равен

2. (Теорема Лукаса.) Покажите, что (Указание. Примените алгоритм Евклида кшипи используйте следующее соотношение (которое доказывается по индукции):

3. а. Докажите, что для остатков, получающихся при выполнении алгоритма Евклида, выполняется неравенство

Другими словами, остатки не просто убывают, но убывают достаточно быстро. (Указание. Рассмотрите два возможных неравенства, связывающих .)

b. Вместо теоремы Ламе воспользуйтесь результатом для получения функции времени вычислений алгоритма Евклида ЕА.

4. Для каждой из следующих пар целых чисел найдите наибольший общий делитель, пользуясь алгоритмом Евклида:

5. Часто алгоритм Евклида удается немного ускорить, если разрешить выполнять деление с отрицательными остатками, т.е. наравне с и выбирать наименьшее Таким образом, мы всегда получаем Выполните четыре примера упр. 4, пользуясь этим методом.

6. Рассмотрим следующий рекурсивный алгоритм вычисления где a и b положительны. (Мы можем считать без потери общности, поскольку, как нам известно, )

[1] Если то положить и закончить работу.

[2] Если a и b оба четные, то положить

[3] Если одно из двух чисел, например а, четно, то положить

[4] Если оба числа нечетны и не равны, например, то положить

Чему равно время вычислений этого алгоритма?

7. Разработайте алгоритм Евклида, который находит наибольший общий делитель двух гауссовых целых чисел. Нужно принять во внимание следующие факты. Гауссовы целые числа — это комплексные числа, вещественная и мнимая части которых являются целыми числами. Если а и два целых гауссовых числа, то мы говорим, что если существует гауссово число 7 такое, что . (Напомним, что поскольку вещественное число, мы можем выполнить деление, написав Мы определим как гауссово число 6 с максимальным абсолютным значением, которое делит как а, так и 0. (Напомним, что абсолютное значение это его расстояние до О, т.е. квадратный корень из суммы квадратов вещественной и мнимой частей.) Отметим также, что определен неоднозначно, поскольку мы всегда можем умножить его на ±1 или и получить другое 6 с тем же самым абсолютным значением, которое также делит и а, и 0. Любое из этих четырех возможных значений рассматривается как Наконец, заметим, что любое комплексное число может быть записано в виде суммы гауссова целого числа и комплексного числа, вещественная и мнимая части которого расположены каждая между —1/2 и 1/2, вследствие чего мы можем делить одно гауссово число а на другое и получать в частном гауссово число, а остаток будет меньше, чем по абсолютной величине.

Используйте полученный алгоритм для вычисления (См. также упр. 4 разд. 3.2.1.)

8. Пусть — последовательные члены последовательности Фибоначчи. Покажите, что

9. Функция является бинарной операцией на Z; покажите, что она коммутативна и ассоциативна.

10. Покажите, что если то (Указание. Примените алгоритм Евклида, чтобы найти и чтобы найти . Например, пусть остаток, полученный после первого деления на , в предположении, что . Как связано

11. Пользуясь тем, что вычислите вероятность, с которой два, четыре, шесть и восемь (соответственно)

случайно выбранных чисел взаимно просты. (См. также упр. 1 по программированию разд. 2.2.2; также представляет интерес статья:

Раздел 2.2.3

1. Примените к паре 217, 413.

2. Найдите целые числа такие, что

3. Пусть , где — целые числа; верно ли, что ? Существует ли какая-либо взаимосвязь между d и ?

4. Найдите все решения приведенных выше упр. 2а и 2b.

5. Для каждого из следующих уравнений найдите целочисленное решение или докажите, что такового не существует:

6. Почему алгоритм, описанный в упр. 6 разд. 2.2.2, не всегда предпочтителен по отношению к алгоритму Евклида? (Указание. Можно ли выразить d как целую комбинацию а и b?)

7. Разработайте расширенный алгоритм Евклида для гауссовых целых чисел и примените его к

Раздел 2.2.4

1. Завершите доказательства теорем 2.2.12 и 2.2.13.

2. Завершите пример, следующий за теоремой 2.2.15.

3. Покажите, что разложение числа в цепную дробь имеет вид [Указание. Заметим, что в нашем случае

4. а. Разложите рациональные дроби 14/3 и 3/14 в конечные цепные дроби.

b. Преобразуйте в рациональные числа (2; 1,4) и (0; 1,1,100).

5. Даны положительные целые числа причем -Покажите, что для любого целого

6. Пусть — положительные вещественные числа. Докажите, что неравенство

истинно, если нечетно, и ложно, если четно.

7. Пусть — положительные целые числа. При каких условиях истинно неравенство

8. Найдите квадратичные иррациональные числа, соответствующие бесконечным цепным дробям

9. Докажите, что для . Найдите и докажите аналогичное разложение в цепную дробь для в предположении, что .

10. Разложите каждое из следующих чисел в бесконечную цепную дробь:

11. Дано, что для двух иррациональных чисел подходящие дроби совпадают по включительно. Докажите, что их разложения в цепные дроби совпадают по с включительно.

12. Докажите, что

Раздел 2.3.1

1. Покажите, что для любого существует простое , такое, что

2. Докажите, что для проверки простоты достаточно показать, что никакое не делит .

3. Пусть — простые числа в порядке возрастания. Покажите, что

a. [Указание. Используйте постулат Бертрана, который утверждает, что для любого существует простое , такое, что его доказательство можно найти в (Niven, Zuckerman, 1980).]

b. для любого

4. Покажите, что квадратный корень из простого числа никогда не является рациональным числом, т.е.

5. Для каких значений функция Эйлера нечетна?

6. Если то что можно сказать о числе ?

7. Докажите, что для любой степени простого числа

8. Найдите для всех от 70 до 80.

9. Составьте список, содержащий все целые числа , для которых и докажите, что ваш список полон.

10. Предположим, что где и g - два различных простых числа. Докажите, что знание двух простых чисел р, q эквивалентно знанию в том смысле, что мы можем вычислить по и q и можем вычислить по используя только «малое» число арифметических операций и операцию извлечения квадратного корня из целого числа. Этот факт подчеркивался также в разделе 4.2.2.

Упр. 11-15 имеют дело с простыми числами в кольце гауссовых чисел (См. также упр. 7 разд. 2.2.2.)

11. Докажите, что если z — гауссово целое число (т.е. ) и его норма — простое число в 2, то z — простое в . {Напомним, что если то Проверьте, что и простые числа в

12. Покажите, что если z — простое число в то существует простое число в Z, такое, что

13. Докажите, что если — простое число в Z, то либо — простое в либо где и и v — сопряженные простые числа в (Следовательно, разлагается ли на множители в зависит от того, может ли быть записано в виде суммы двух квадратов целых чисел. Следующие два упражнения помогают нам определить их.)

14. Покажите, что если — простое число в Z и то просто в

15. (Ферма) Покажите, что если — простое число в Z и то — целые числа, т.е. не является простым в (Указание. Воспользуйтесь теоремой Вильсона из следующего раздела.)

См. также упр. в упражнениях для разд.

Раздел 2.3.2

1. Завершите доказательство теоремы 2.3.7.

2. Завершите доказательство теоремы 2.3.8.

3. Покажите, что если 5 не делит , то 5 делит

4. Найдите используйте теорему Ферма.

5. Покажите, что для любого число делится на 2, 3, 6 и 7.

6. Используя два способа, которые обсуждались в тексте, вычислите мультипликативные обратные к числам 7, 8 и 9 по модулю 19. [Указание. Используйте алгоритм

7. Покажите, что мультипликативный обратный к в кольце равен

8. Пусть G — группа и а — ее элемент порядка s; покажите, что порядок элемента равен

9. Найдите все примитивные корни по модулю 27.

10. Используйте теорему 2.2.4 для доказательства того, что система сравнений имеет решение тогда и только тогда, когда . Если решение существует, то оно единственно по модулю наименьшего общего кратного чисел (Обобщите это утверждение на случай произвольного числа уравнений. Для доказательства единственности покажите, что ) тогда и только тогда, когда

11. Докажите теорему 2.3.25.

12. (Никомах; см. также историческое замечание 6.) Решите следующую систему уравнений:

13. а. Покажите, что существует бесконечно много чисел, свободных от квадратов.

b. Покажите, что всякое положительное целое число представляется единственным образом в виде произведения квадрата и числа, свободного от квадратов.

14. Докажите, что десятичное целое число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3, и что оно делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.

15. а. Пусть Докажите, что любое решение системы сравнений является также решением сравнения и обратно. (Обобщите этот результат на сравнения высших степеней и покажите, что если

обозначает число решений сравнения где — данное выше число, то

b. Покажите, что для тогда и только тогда, когда где, как вы помните, обозначает наименьшее общее кратное чисел, заключенных в скобки.

16. а. Сколько решений имеет сравнение

если два решения считаются совпадающими, если (Указание. Сначала докажите, что если имеет вид или для обоих случаев, то сравнение имеет два решения ). Затем докажите, что если имеет вид 2, к 3, то существуют четыре решения, Что случится при Наконец, воспользуйтесь тем, что тогда и только тогда, когда для всех простых чисел у которых в полном разложении m на множители, и скомбинируйте полученные результаты, чтобы показать, что если имеет ровно различных простых делителей, то общее число решений равно Т, с корректировкой для четных То есть в общем случае точное число равно где равно 1, если и 0 в противном случае.)

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

c. Сколько -значных чисел удовлетворяет сравнению Обобщите свой ответ.

17. Покажите, что сравнение , где — простое число, имеет решения тогда и только тогда, когда или (Указание. Воспользуйтесь теоремой Вильсона и тем, что если не сравнимо с 1 по модулю 4, то )

18. а. Докажите, что если — простое число и то сравнение имеет решений или не имеет решений в зависимости от того,

. (Указание. Воспользуйтесь малой теоремой Ферма, чтобы показать, что сравнение не имеет решений, если . Для доказательства обратного утверждения воспользуйтесь следующей информацией: должен существовать образующий по модулю такой, что , а значит, исходная проблема может быть сведена к сравнению ; затем воспользуйтесь тем, что линейное сравнение общего вида имеет решений по модулю m (теорема )

b. Критерий Эйлера. Используйте (а), чтобы показать, что если — нечетное простое число и то сравнение имеет два решения или не имеет ни одного в зависимости от того, или . (Величина играет важную роль в теории чисел; см. упр. 9 разд. 2.3.3, утверждающее, что ее значение равно значению символа Лежандра по определению равного 1, если а — квадратичный вычет по модулю , и равного —1, если а — квадратичный невычет по модулю . Существует также символ Якоби: для т.е. когда равно произведению s не обязательно различных простых чисел, он определяется как — символ

Лежандра. Ясно, что но неверно, что из равенства следует, что а является квадратичным вычетом по модулю q, например но сравнение не имеет решений.)

19. Найдите наименьшее положительное число, дающее остаг ток 2 при делении на 11, остаток 3 при делении на 12 и остаток 4 при делении на 13.

20. Расширьте алгоритм возведения в степень Е так, чтобы он вычислял в общем случае (т.е. для любых значений ), и воспользуйтесь этим расширенным алгоритмом, чтобы вычислить

21. Как указано в тексте, если то является обратным к а по модулю . Предположим, что — очень большое число. Скомбинируйте бинарный алгоритм

возведения в степень с расширенным алгоритмом Евклида, чтобы получить эффективный метод вычисления ), когда (а) а имеет столько же цифр, сколько и когда а гораздо меньше .

22. Предположим, что -значное (десятичное) положительное целое число, дающее остаток 2 при делении на 11, остаток 9 при делении на 12 и остаток 11 при делении на 13, является делителем шестизначного натурального числа, дающего остаток 5 при делении на 11, 9 при делении на 12 и 8 при делении на 13. Найдите частное. (Указание. Имеется два возможных ответа.)

23. (Обращение теоремы Ферма.) Покажите, что если не сравнимо с 1 по модулю для всех простых , таких, что то — простое число. (Указание. Покажите, что если это условие выполнено, то числа различны для

24. а. Пользуясь малой теоремой Ферма, докажите, что если а не делится на простое число то

Используйте (а), чтобы вычислить последнюю цифру по основанию 7 числа

25. Пользуясь греко-китайской теоремой об остатках, покажите, что - функция Эйлера мультипликативна, т.е. покажите, что если только

26. Пользуясь теоремой Эйлера (теорема 2.3.14), докажите, что если то тогда и только тогда, когда (Этот результат будет использован в разд. 4.2.2.)

27. а. Покажите, что в теореме Эйлера (теорема 2.3.14), если — не простое число и не четное число вида , где — простое число, то существует меньшая (чем ) степень числа а, гарантированно дающая 1 по модулю а именно наименьшее общее кратное степеней, дающих а — наибольшее целое, такое, что Например, пусть , где в этом случае для некоторого а; заметим, что также , потому что 12 — это наименьшее общее кратное чисел 3-1, 5-1 и 7-1.

b. Пользуясь (а), вычислите Получите то же самое решение, пользуясь греко-китайской теоремой об остатках.

28. Найдите -значное (десятичное) число (две возможности), дающее остаток 4 при делении на 5, 7 или 13.

29. Рассмотрим систему сравнений

где не являются взаимно простыми. Приведите пример чисел для которых нет решения. Для каких эта система имеет решение?

Раздел 2.3.3

1. Покажите, что если — нечетное составное число, то имеет место следующее:

a. Если делится на полный квадрат то не является кармайкловым числом.

b. Если свободно от квадратов, тот — кармайкл число тогда и только тогда, когда для каждого простого числа , такого, что

(В качестве примера рассмотрите делится на .)

2. Используйте упр. 1, чтобы доказать, что кармайклово число должно быть произведением не менее трех различных простых чисел.

3. а. Найдите все основания 6, по которым 15 — псевдопростое число (не включайте тривиальные основания ±1.)

b. Покажите, что если и простые числа и , то — псевдопростое число для 50% возможных оснований b, т.е. для всех b, которые являются квадратичными вычетами по модулю

4. Пусть m — положительное нечетное составное число, и пусть

Покажите, что если — простое число, псевдопросто по основанию b, то , где

Покажите, что никакое целое число вида — простое число) не может быть псевдопростым по основанию 2, 5 или 7.

c. Покажите, что никакое целое число вида простое число) не может быть псевдопростым по основанию 2, 3 или 7.

d. Покажите, что — наименьшее псевдопростое число по основанию 3.

5. Чему равно наименьшее псевдопростое число по основанию 2? по основанию 5?

6. Докажите, что если — простое число, то псевдопросто по основанию 6 тогда и только тогда, когда

7. Пусть — произведение двух различных простых чисел. Положим Докажите, что псевдопросто по основанию 6 тогда и только тогда, когда . Сколько, в терминах d, существует оснований, относительно которых псевдопросто? Сколько существует оснований, относительно которых псевдопросто, если Перечислите все такие основания в терминах . (См. также упр. 19 ниже.)

8. Покажите, что если псевдопросто по основанию 6 и если то целое число псевдопросто по основанию b. Приведите пример, показывающий, что это может быть не так, если мы опустим условие

9. а. Воспользуйтесь малой теоремой Ферма, чтобы показать, что если — нечетное простое число и то

(См. определение символа в упр. 18 разд. 2.3.2.)

Мы покажем, что если — нечетное составное число, то сравнение ложно по крайней мере для 50% всех b, для которых

b. Покажите, что если сравнение истинно для и ложно для 62, то оно ложно для произведения Используйте этот результат, чтобы доказать, что если сравнение ложно хотя бы для одного 6, то число значений 6, для которых оно ложно, по крайней мере так же велико, как число значений 6, для которых оно истинно.

c. Если делится на квадрат простого числа , покажите, как найти целое число такое, что .

d. Покажите, что если — произведение различных простых чисел, — одно из этих простых чисел и

таково, что , то сравнение для b ложно. Затем покажите, что такое b всегда существует.

10. Если — нечетное составное число и b — целое число такое, что и имеет место сравнение то называется псевдопростым числом Эйлера по основанию b.

Если — псевдопростое число Эйлера по основанию b, то оно псевдопросто по основанию b. (Отметим, что обратное утверждение неверно; например, псевдопросто по основанию 3, но )

11. Предположим, что — положительное целое число, такое, что — простые числа. Докажите, что ) — кармайклово число. (Существует также много кармайкловых чисел не такого вида.)

12. Проверьте, что все следующие числа кармайкловы:

13. а. Покажите, что для любого фиксированного простого числа существует только конечное число кармайкловых чисел вида (, q — простые числа).

b. Найдите все кармайкловы числа вида (, q — простые числа).

c. Найдите все кармайкловы числа вида (р, q — простые числа).

с. Покажите, что для любого фиксированного простого числа существует только конечное число кармайкловых чисел вида (, q — простые числа).

14. Покажите, что 561 — наименьшее кармайклово число.

15. Рассмотрим 561, наименьшее кармайклово число.

а. Найдите число оснований (обратимые по модулю 561 элементы), для которых 561 — псевдопросто число Эйлера.

b. Найдите и перечислите основания, по которым 561 строго псевдопросто.

16. Покажите, что если где — простое число, то строго псевдопросто по основанию b тогда и только тогда, когда оно псевдопросто по основанию 6.

17. Проверьте, что 65 строго псевдопросто по основанию 8 и по основанию 18, но не по основанию 14, которое равно произведению 8 и 18 по модулю 65.

18. Покажите, что если то строго псевдопросто по основанию 6 тогда и только тогда, когда оно — псевдопростое число Эйлера по основанию 6.

19. Покажите, что если мы найдем основание b, такое, что псевдопросто, но не строго псевдопросто по основанию b, то мы можем быстро найти нетривиальный сомножитель числа т. Объясните, как бороться с этим при выборе в RSA-криптосистеме, обсуждаемой в разд. 4.2.2; см. также выше упр. 7.

Раздел 2.3.4

1. а. Докажите, что для любого целого числа b и любого положительного целого числа число делится на и частное равно

b. Заменив b на мы видим, что делится на с соответствующим образом измененным частным. Чему равны два легко вычисляемых сомножителя числа ?

2. Докажите, что если нечетно, то делится на и частное равно .

3. а. Докажите, что если простое число (Мерсенна), — простое число, и что если — простое число (Ферма), — степень числа 2. (Указание. Докажите это методом от противного, используя упр. 1 и 2.)

b. Используйте малую теорему Ферма (и несколько десятков умножений), чтобы доказать, что — не простое число.

4. Предположим, что и что а и с — положительные целые числа. Докажите, что если , то , где

5. Используйте упр. 4, чтобы доказать, что если — простое число, делящее , то либо для некоторого

собственного делителя d числа , либо . Если нечетно, то в случае мы имеем

Приведенные выше упражненья используются далее в упр. 6-9:

6. а. Разложите на множители .

b. Разложите на множители .

7. Разложите на множители

8. Разложите на множители .

9. Разложите на множители и .

Разложение на множители методом Ферма (обоснование метода, описанного в тексте).

10. а. Покажите, что если m — положительное нечетное

то существует взаимно однозначное соответствие между разложениями на множители вида и представлениями в виде где — неотрицательные целые числа. Это соответствие задается уравнениями

b. Используя (а), мы можем разложить на множители, вычисляя для числа к и проверяя, является ли полным квадратом (где, разумеется и ),

c. Пользуясь описанной в процедурой, разложите на множители 91, 323.

Метод цепных дробей; этот метод отличается от обсуждаемого в тексте только тем, что величины а выбираются с применением цепных дробей (также здесь используются системы множителей). Он основан на двух следующих упражнениях.

11. Покажите, что если — вещественное число, разложение которого в цепную дробь имеет подходящие дроби то для всех

12. а. Покажите, что если — положительное целое число, не являющееся полным квадратом, и — подходящие дроби в разложении в цепную дробь, то наименьший по абсолютной величине вычет меньше, чем (Указание. Воспользуйтесь упр. 11.)

b. Часть (а) является ключевой в методе цепных дробей; она утверждает, что, перебирая числители подходящих дробей в разложении в цепную дробь, мы

можем найти последовательность чисел квадраты которых имеют малые вычеты. (Отметим, что нам нужны только числители т.е. нам не нужно находить точное значение подходящей дроби.) Процедура разложения на множители аналогична процедуре, описанной в тексте, и детали мы оставляем читателю (просмотрите еще раз разд. 2.2.4).

с. Пользуясь методом цепных дробей, разложите на множители 899 и 1443.

Раздел 2.4

1. Докажите теорему 2.4.1.

2. Пусть d — наибольший общий делитель целых чисел . Покажите, что полином является наибольшим общим делителем полиномов над любым полем.

3. Используя многомодульную арифметику с вектором оснований вычислите а где

4. Используя тот же вектор оснований найдите многомодульное представление следующих целых чисел как для симметричной системы остатков, так и для системы наименьших неотрицательных остатков: (а)

5. Пусть — вектор оснований. Каков знак числа