Конспект курса арифметики

Как показал опыт предыдущих лет, курс арифметики хорошо подходит для разнородно подготовленной аудитории Летней школы. Хорошо работает метод преподавателя МГУ Александра Васильевича Михалёва: простые вещи надо рассказывать подробно, так, чтобы все поняли, а сложные быстро: всё равно не поймут. Объём материала рассчитан на восемь лекций и семь семинаров. Темы лекций:

• Записи чисел
• Операции над числами, замыкания относительно операций, счётность, теорема Кантора
• Уравнения в целых числах: пифагоровы тройки, уравнение Маркова, арифметика точек эллиптических кривых
• Теорема Евклида о бесконечности числа простых чисел, основная теорема арифметики
• Совершенные числа, Теорема Гаусса
• Малая теорема Ферма, теорема Дирихле
• Теорема Ферма-Эйлера о представлении чисел в виде суммы квадратов
• Практические применения (шифрование)
• Разбор задач

Содержание

• Разгоночная контрольная
• Конспект лекций
• Задачи по курсу
• Литература

Разгоночная контрольная

Запишите первые две буквы Вашего имени и первые две буквы фамилии, используя 33-ёх буквенный русский алфавит. Вычислите сумму порядковых номеров (в алфавите) этих букв. Обозначьте полученное число через N.

• Вычислите сумму цифр Ц(N) записи числа N в десятичной системе.
• Разложите число N - Ц(N) на простые множители.
• Найдите сумму делителей σ(N) числа N.
• Найдите наибольший общий делитель НОД(N, σ(N)) чисел N и σ(N).
• Найдите наименьшее общее кратное НОК(N, Ц(N)) чисел N и Ц(N).

Для последней контрольной в качестве числа N берётся сумма двух двузначных чисел в 33-ичной системе счисления: первых двух букв имени и первых двух букв фамилии.

Проверка

Имя Фамилия

Конспект лекций

Априорное знание о натуральном ряде

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

Автор эпиграфа из Калининграда. Это категорический императив Иммануила Канта, умершего более двухсот лет назад. Помимо нравственных законов, Кант философствовал на тему математики. В частности, из всей математики Кант выделял геометрию и арифметику тем, что познание этих двух наук даётся человеку априорно в его чувствах пространства и времени. «Арифметика создает свои понятия чисел посредством последовательного добавления единиц во времени», — пишет Иммануил Кант. Если ему верить, то знание этого курса уже существует внутри Вас, и до него надо лишь докопаться. 1, 2, 3, ... — натуральный, самый естественный ряд чисел, где каждое следующее число получается из предыдущего добавлением единицы. В переводе — «природный» ряд.

История записи

1	I	unus
5	V	quinque
10	X	decem
50	L	quinquaginta
100	C	centum
500	D	quingenti
1000	M	mille

Calculus — маленький камень. Фигурные числа — пример записи числа: треугольные, квадратные, пятиугольные. Складывая последовательные нечётные числа, мы получаем квадраты. Чётные, нечётные числа. Примеры других аддитивных записей: X = 10, IV = 4, XLVI = 46, I = 10, Д = 4, ДI = 14. Линия над словами (титло) служит для выделения чисел в тексте. Вавилонские клинышки.

Вычисления

Сложение = прибавление, вычитание = отнимание, коммутативность сложения, ассоциативность сложения. Может ли большее, делённое на меньшее, быть равно меньшему, делённому на большее? Уже Диофант знал, что минус на минус даёт плюс. Сколько это будет, три раза заплатить штраф по 15 рублей? Но ещё в XVII веке парадокс Арно препятствовал повсеместному принятию отрицательных чисел. Что такое отрицательные числа? Например, лучи в N². Зачем они нужны? Замыкание множества натуральный чисел по вычитанию. Замкнутость множества чётных чисел. Умножение, деление, коммутативность и ассоциативность умножения.

Сколько будет 3 × 5? Почему 3 × 5 = 5 × 3?

(a_n...a₁a₀)_k = a_nkⁿ + ... a₁k¹ + a₀k⁰. Запись числа в разных системах счисления, перевод из десятичной системы счисления в другую с помощью цепочки последовательных делений с остатком. Операции «в столбик». Фиббоначиева система счисления: нет двух рядом стоящих единиц. 9 = (10001)_F. Какие числа возникнут, если замкнуть множество целых чисел относительно деления? Добавить корни всех многочленов? Ещё записи чисел: периодическая дробь, ряд Зенона, цепная дробь [1, 1, 1, ...]. Квадратичная иррациональность — связь с уравнением Пелля и цепной дробью. Самое большое число: гугол, гуголплекс, ∞ и ℵ₀. Действительные числа. Однозначна ли запись действительных чисел? Теорема Кантора.

Магические квадраты

Магические квадраты: в каждом столбце, каждой строчке и диагонали — сумма совпадает. Существует всего лишь один магический квадрат размера 3. Сначала устанавливается, что в центре находится 5, затем от противного показывается, что 9 не может находиться в углу. На картинке слева — репродукция магического круга Бенджамина Франклина. Оригинал, выполненный в цвете, продан частному коллекционеру.

Пифагоровы тройки и рациональная параметризация окружности

Делимость

НОД, НОК, взаимно-простые числа, простые числа. Открытая проблема Гольдбаха: каждое чётное число представляется в виде суммы двух простых. Неизвестно, бесконечно ли много простых чисел-близнецов. Эратосфен Киренский (из города Кирены), сменивший своего учителя на посту заведующего александрийской библиотекой, известен своей эрудицией в множестве областей, и, в том числе, своими трудами по математике: решением задачи удвоения куба и способом поиска простых чисел. Теорема Евклида. Простых чисел бесконечно много. Доказательство. Предположим, что их конечное число, и рассмотрим число p₁ × p₂ × p₃ × ... × p_n + 1. Оно делится на какое-то p_k — противоречие.

Основная теорема арифметики

Алгоритм Евклида даёт наибольший общий делитель. То, что наибольший, получаем прямым проходом алгоритма, то что делитель — обратным. Лемма Евклида. Если (a, b) = 1 и a | bc, то a | c. Следует из алгоритма Евклида, а именно из существования p, q: ap + bq = (a, b). Существование разложения доказывается по индукции. Однозначность разложения следует из леммы Евклида, а именно: если произведение делится на простое p, то какой-то сомножитель делится на p. Следовательно, два несовпадающих разложения можно сократить. Однозначность разложения возникает не во всех алгебраических структурах. 2 Z = {..., −4, −2, 0, 2, 4, 6, ...}: 36 = 6 × 6 = 2 × 18 (нет единицы), Z[√−5] = { a + b √−5 }: 6 = 2 × 3 = (1 + √−5) × (1 − √−5) (необходима упорядоченность, используем норму для доказательства простоты).

Совершенные числа

Дружественные числа, общественные числа.

Теорема Эйлера. Все чётные совершеные числа имеют вид Евклида 2^{p − 1} (2^p − 1), где 2^p − 1 — простое число Мерсенна. Доказательство. Без ограничения общности, n = 2^{p − 1} m, где m — нечётно и p ≥ 2. Тогда σ(n) = 2^p m = (2^p − 1) σ(m). Отсюда сумма делителей σ(m) = m + m / (2^p − 1). Заметим, что m / (2^p − 1) — целое, а следовательно входит в сумму σ(m) делителем m, отличным от m. Учитывая, что на этом сумма σ(m) исчерпывается, m / (2^p − 1) = 1.

Бесконечно ли много ли простых чисел вида 4k − 1? Пусть их конечное число. Рассмотрим произведение чисел 4 p₁ × p₂ × p₃ × ... × p_n − 1: у него есть простой делитель вида 4k − 1.

Теорема Дирихле. В арифметической прогрессии со взаимно простыми основанием и разностью простых чисел бесконечно много. Доказательство. Харди и Райт в своей книге пишут, this theorem is too difficult for insertion in this book. Элементарное доказательство в книге Хинчина очень хорошо посмотреть, чтобы понять значение слова «элементарное».

Теорема Гаусса

Ферма: за простоту чисел F_n = 2^{2^n} + 1 ручаюсь. Такой сложный вид показателя Ферма выбрал не случайно: число 2^k + 1 при k != 2ⁿ является составным.

Малая теорема Ферма

Функция Эйлера φ(n) = n П_p (1-1/p). Любой остаток по простому модулю встречается в каждой строчке таблицы умножения, составленной из чисел, взаимно простых с модулем, ровно один раз. Умножение на число переставляет остатки местами.

Теорема Ферма—Эйлера о представлении чисел в виде суммы квадратов

Зачем изучать суммы квадратов? Связаны с умножением. Теорема. Если каждое из числе представлется в виде суммы квадратов, то и их произведение представляется в виде суммы квадратов. Доказательство. (a² + b²)(x² + y²) = (ax - by)² + (ay + bx)². Теорема. Если сумма квадратов a² + b² целых чисел a и b делится на простое число p вида p = 4n + 3, где n — целое неотрицательное число, то числа a и b делятся на p. Доказательство. Пусть a не делится на p. Тогда и b не делится на p. Возведем обе части сравнения a² = -b² (mod p) в (2n+1)-ю степень: a⁴ⁿ⁺² = -b⁴ⁿ⁺² (mod p). В силу малой теоремы Ферма a⁴ⁿ⁺² = 1 = −b⁴ⁿ⁺² (mod p), поэтому 1 = −1 (mod p) что невозможно при p > 2. Теорема Ферма—Эйлера. Любое простое число p=4n+1, где n — натуральное число, представимо в виде суммы квадратов двух натуральных чисел. Доказательство. Разобьём множество «крылатых квадратов», соответствующих решениям уравнения a² + 4bc = p на пары: крылатому квадату (a, b, c) поставим в соответствие {(a+2b, c-a-b, b), если a+b < c, (a-2c, c, a+b-c), если c < a+b и 2c < a, (2c-a, a+b-c, c), если c < a+b и a < 2c}. Останется один непарный квадрат. Значит общее число решений нечётно, следовательно у преобразования (a, b, c)->(a, c, b) есть неподвижная точка.

Задачи по курсу

Магические квадраты

1. Докажите, что сумма чисел в строке магического квадрата со стороной n равна n(n²+1)/2.
2. Альбрехт Дюрер хотел поместить год написания гравюры 1514 в нижнюю строчку изображенного на ней магического квадрата. Мог ли Дюрер использовать вместо своего квадрата какие-либо другие квадраты, в которых тот же год фигурировал таким же образом? Указание. Соберите квадрат из строчек оригинального квадрата.
3. Дюрер прожил до 1528 года. Смог ли он датировать какую-нибудь из своих более поздних картин таким же образом?

Фигурные числа

4. Докажите, что n-ное треугольное число t_n задается формулой t_n = n (n+1) / 2.
5. Докажите, что n-ное пятиугольное число p_n задается формулой p_n = n (3n-1) / 2.
6. Докажите, что n-ное k-угольное число t_{k, n} задается формулой t_{k, n} = k (n²-n) / 2 – n² + 2 n.

Десятичная система счисления

7. Докажите, что число 444...44 не делится на 8 ни при каком количестве четверок.
8. Докажите признак делимости на 5: число делится на 5 тогда и только тогда, когда последняя цифра его записи в десятичной системе счисления делится на 5.
9. Докажите, что число и сумма цифр в его записи в десятичной системе счисления дают одинаковые остатки при делении на 3 и 9.
10. К числу 15 припишите слева и справа по одной цифре так, чтобы полученное число делилось на 15.
11. К числу 10 припишите слева и справа по одной цифре так, чтобы получилось число, кратное 72.
12. Найдите наибольшее натуральное число, делящееся на 36, в записи которого участвуют все 10 цифр по одному разу.
13. На какие цифры может оканчиваться квадрат целого числа?
14. К трехзначному числу приписали рядом его же (например, 548 548) и разделили полученное шестизначное число на 13. Частное разделили на 11, а новое частное – на 7. Что получилось?
15. Написали подряд три раза двузначное число (например, 59 59 59). Докажите, что полученное число делится на 3, 7, 13 и 37.
16. Докажите, что число, записанное шестью одинаковыми цифрами, делится на 3, 7, 11, 13 и 37.
17. Найдите закономерность, облегчающую возведение в квадрат чисел, оканчивающихся на 5.
18. Найти трехзначные числа, которые в 25 раз больше суммы своих цифр.
19. Какие трехзначные числа в 11 раз больше суммы своих цифр?
20. Трехзначное число начинается цифрой 4. Если ее перенести в конец числа, то полученное число будет составлять ? исходного. Найдите исходное трехзначное число.
21. Что больше, 20042004 • 200520052005 или 20052005 • 200420042004?
22. Придумайте шестизначное число, которое при умножении на 2, 3, 4, 5, 6 дает числа, записанные теми же цифрами, что и само число, но в другом порядке. Указание. Найдите период десятичных дробей 1/7, 2/7, ..., 6/7.
23. Число, уменьшается в n раз при переносе первой цифры в конец числа. Чему равно n?
24. Натуральное число умножили на каждую из его цифр. Получилось 1995. Найдите исходное число.
25. Возьмем произвольное натуральное число и построим последовательность чисел следующим образом. Каждое следующее число положим равным сумме квадратов цифр предыдущего числа. Докажите, что в любой такой последовательности встретится 1 или 145.
26. Найдите цифры a и b такие, что v0,aaaaa.... = 0,bbbbb...
27. В строку написано несколько восьмёрок. Кое-где между ними вставлены знаки «+», причём полученная сумма равна 1000. Приведите пример с наименьшим числом слагаемых.
28. Укажите все целые числа, которые увеличиваются на 20%, если их цифры записать в обратном порядке.
29. Решите арифметические ребусы ААА + БББ = АААВ, 1АБВГД x 3 = АБВГД1 (одинаковым буквам соответствуют одинаковые цифры, разным — разные).
30. Решите арифметические ребусы SEND + MORE + GOLD = MONEY, HOCUS + POCUS = PRESTO, FORTY + TEN + TEN = SIXTY, ADAM + AND + EVE + A = RAFT, SEE + SEE + SEE + YES = EASY.

Признак делимости на девять

31. В стране Анчурии в обращении имеются купюры следующих достоинств: 1 анчур, 10 анчуров, 100 анчуров, 1000 анчуров. Можно и отсчитать миллион анчуров так, чтобы получилось ровно полмиллиона купюр?
32. Найти двухзначное число, первая цифра которого равна разности между этим числом, и числом, записанным теми же цифрами, но в обратном порядке.
33. Верно ли, что если записать в обратном порядке цифры любого целого числа, то разность исходного и нового чисел будет делиться на девять?
34. Найдите все двузначные числа, сумма цифр которых не меняется после умножения этого числа на 2, 3, ..., 9.
35. Незнайка перемножил все числа от 1 до 100 и посчитал сумму цифр произведения. У полученного числа он снова посчитал сумму цифр, и так далее. В конце концов, Незнайка получил однозначное число. Какое?
36. У каждого из чисел от 1 до 1 000 000 000 подсчитывается сумма его цифр, у каждого из получившегося милиарда чисел снова подсчитывается сумма его цифр, и так далее до тех пор, пока не получится миллиард однозначных чисел. Каких чисел получится больше всего?
37. Сумма цифр числа x равна y, а сумма цифр числа y равна z. Найдите x, если x + y + z = 60.
38. Обозначим через s(n) сумму цифр числа n. Решите уравнения: а) x + s(x) = 1 000 000 000, б) x + s(x) + s(s(x)) = 1993, в) x + s(x) + s(s(x)) + s(s(s(x))) = 1993.

Системы счисления

39. Переведите в десятичную систему счисления: а) 1234₅, б) 111111₃.
40. Представьте числа 362, 1969, 10000 в системах при основаниях 2, 6, 17.
41. В какой системе счисления 10 • 10 = 10 + 10?
42. Докажите, что количество нетривиальных умножений в системе с основанием b равно (b-1) (b-2) / 2.
43. Чему равна сумма всех элементов в таблице умножения?
44. Число называется числом Ферма, если оно представимо в виде 2^{2^t} + 1. Найдите двоичное представление чисел Ферма.
45. Найдите двоичные представления четных совершенных чисел.

Разбиения и диаграммы Юнга

46. Изобразите на клетчатой бумаге 22 разбиения числа 8 на слагаемые. Сколько получилось разбиений на нечётные слагаемые? Сколько получилось разбиений на различные слагаемые?
47. Почему количество разбиений числа на разные слагаемые равно количеству разбиений этого числа на нечётные слагаемые?

Деление с остатком

48. Построим следующую последовательность цифр. Выпишем цифры 2 x 3. Будем обозначать крестиком, что эти цифры впоследствии надо перемножить. На каждом шаге построения сотрем первый крестик, и перемножим стоявшие  вокруг него цифры. Цифры результата допишем к последовательности, разделяя их крестиком. 2 3 x 6 2 3 6 x 1 x 8 2 3 6 1 x 8 x 6 2 3 6 1 8 x 6 x 8 Докажите, что в этой последовательности никогда не встретятся цифры 5, 7, 9.
49. Какое частное, и какой остаток получатся при делении 6! + 1 на 5?
50. Сколько воскресений может быть в году?
51. Может ли быть в одном месяце пять воскресений?
52. В некотором месяце три воскресенья пришлись на четные числа. Какой день недели был 20 числа этого месяца?
53. Напишите общий вид чисел, дающих при делении на 4 остаток а) 1, б) 2, в) 3.
54. Когда солдаты строились в колонну по 4, 5 или по 6, каждый раз один оставался лишним, а когда построились в колонну по 7, лишних не осталось. Сколько было солдат?
55. На поле растут деревья с золотыми монетами. (На разных деревьях может быть разное число монет!) Каждую ночь на каждом дереве вырастает одна монета. Первого марта на деревьях было всего 1000 монет. В марте Буратино посадил еще одно дерево, и 31 марта на деревьях оказалось всего 1993 монеты. В какой день Буратино посадил дерево?

Пифагоровы треугольники

56. Найдите какое-нибудь решение уравнения Пифагора x² + y² = z² в целых числах.
57. Попытайтесь найти решения уравнения Пифагора, в котором гипотенуза на единицу больше, чем больший из двух катетов.
58. Найдите все пифагоровы треугольники, у которых длина гипотенузы не превосходит 100.
59. Найдите все такие треугольники Пифагора, у которых длина одной из сторон равна а) 50, б) 22.
60. Могут ли быть треугольниками Пифагора треугольники с площадями а) 78, б) 120, в) 1000?
61. Найдите все треугольники Пифагора с периметрами а) 88, б) 110.
62. Треугольник имеет целые длины сторон x, y, z, причем известно, что длина одной из его высот равна сумме двух других. Докажите, что x² + y² + z² — квадрат целого числа.
63. Треугольник Герона — это треугольник с целочисленными сторонами, площадь которого выражается целым числом. Найдите треугольник Герона, не являющийся прямоугольным.

Уравнения в целых числах

64. Эллиптическая кривая. Найдите 7 решений в целых числах уравнения y² = 6(x³ - x). Найдите 4 решения этого уравнения в рациональных числах.
65. Уравнение Пелля. Решите уравнение x² - 2y² = 1 в целых числах.
66. Уравнение Маркова. Решите уравнение x² + y² + z² = 3xyz в целых числах.
67. Решите уравнение x² - xy - y² = 1 в целых числах.

Простые числа

68. Какие из следующих чисел являются простыми: а) год вашего рождения, б) год, в котором вам исполнится 20 лет, в) номер вашей квартиры?
69. Найдите простое число, следующее за простым числом 1973.
70. Числа от 90 до 96 включительно являются семью последовательными составными числами. Найдите девять последовательных составных чисел.
71. Докажите, что в натуральном ряду встречаются сколь угодно длинные отрезки, состоящие из составных чисел.
72. Верно ли, что многочлен P(n) = n² + n + 41 при всех n принимает простые значения?
73. Найдите наименьшее составное число, которое остается составным, если в нем произвольно заменить одну из цифр.
74. Составьте таблицу первых 200 простых чисел.
75. Определите количество простых чисел в диапазоне от 300 до 400.

Разложение чисел на множители

76. Разложите на простые множители числа 120, 365, 1970.
77. Разложите на простые множители а) год вашего рождения, б) год, в котором вам исполнится 20 лет, в) номер вашей квартиры.
78. Четно-простое число – это четное число, которое нельзя разложить в произведение четных чисел. Запишите все разложения числа 360 на четно-простые числа.
79. В каких случаях четные числа обладают единственным разложением на четно-простые множители?
80. Сколько делителей имеет простое число?
81. Сколько делителей имеет степень простого числа pⁿ?
82. Найдите количество делителей чисел 60, 366, 1970, года вашего рождения.
83. Представьте число 203 в виде суммы нескольких натуральных чисел, произведение которых тоже равно 203.
84. Какое натуральное число, не превосходящее 100, имеет наибольшее количество делителей?
85. Взвод из 12 солдат может маршировать 6-ю различными способами: 12x1, 6x2, 4x3, 3x4, 2x6, 1x12. Какую наименьшую численность должны иметь группы людей, которые могут маршировать 8, 10, 12 и 72 способами?
86. Найдите натуральные числа, имеющие: а) 14 делителей, б) 18 делителей.
87. Охарактеризуйте все натуральные числа, количество делителей которых является произведением двух простых чисел.
88. Зная, что четвертое число Мерсенна равно M₇ = 127, найдите четвертое совершенное число.

Наибольший общий делитель и наименьшее общее кратное

89. Найдите наибольший общий делитель и наименьшее общее кратное пар чисел: a) 360 и 1970, б) 30 и 365, в) номера вашей квартиры и года рождения.
90. Найдите НОД(99!+100!, 101!), НОД(2n–17, n–8) при всех n.
91. Докажите, что НОД(a,b) НОК(a,b) = ab.
92. Найдутся ли 3 натуральных числа таких, что ни одно из них не делится на другое, а произведение любых двух из них делится на третье?
93. Докажите, что в вершинах любого многогранника можно расставить натуральные числа так, чтобы числа в вершинах связанных ребром имели общий делитель больше 1, а не связанные ребром не имели.
94. Докажите, что v2 иррационально.
95. Какие числа взаимно просты с числом 2?
96. Почему НОД(n, n+1) = 1?
97. Найдите наибольший общий делитель и наименьшее общее кратное  для каждой из следующих пар дружественных чисел (220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368), (10744, 10856), (12285, 14595), (17296, 18418).
98. Верно ли, что если произведение двух взаимно простых чисел является n-ной степенью некоторого числа, то каждое из этих чисел является n-ной степенью?
99. Каким количеством нулей оканчивается число n! = 1 • 2 • 3 • ... • n?
100. Найдите наибольший общий делитель и наименьшее общее кратное пар многочленов: a) x²-1 и x³-1, б) (x+1)² и x³+1.

Сравнения

101. Найдите остатки а) 111 (mod 37), б) -37 (mod 7), в) -111 (mod 11), г) -365 (mod 30).
102. Разложите на множители а) x² - 1, б) x² + 1 (mod 2), в) x³ + 1 (mod 3).
103. Докажите, что ни при каком целом k число k² + k + 1 не делится на 5, 11, или 17.
104. Докажите, что ни при каком целом k число k² + k + 1 не делится на 6m – 1, где m – произвольное натуральное число.
105. Докажите, что если число a = 2^2k + 2^k + 1 не является делителем числа 2^{2^k+1} – 1, то a – составное.
106. Укажите хотя бы одно шестизначное число, являющееся точным кубом, такое, что все числа, получающиеся из него циклической перестановкой цифр (abcdef – bcdefa – cdefab – defabc – efabcd – fabcde) делятся на кубический корень из этого числа.
107. Докажите, что при любом натуральном k число 5^5k+1 + 4^{5k + 2} + 3^5k делится на 11.
108. Докажите, что число 3¹⁰⁵ + 4¹⁰⁵ делится на 13, 49, 181, 379 и не делится на 5 и 11.
109. В стаде 51 корова с целыми массами. Если вывести любую корову из стада, то оставшихся коров можно разделить на две группы равной массы. Докажите, что все коровы весят одинаково.

Теорема Ферма о суммах двух квадратов

110. Докажите, что сумма квадратов двух чисел делится на 3 тогда и только тогда, когда каждое из слагаемых делится на 3.
111. Определите, какие из чисел 100, 101, ..., 110 могут быть представлены в виде суммы двух квадратов. Найдите все такие представления.
112. Изобразите в виде диаграмм все решения в натуральных числах уравнения a² + 4bc = 17.
113. Докажите, что число представляется в виде суммы двух квадратов тогда и только тогда, когда каждое простое число вида 4n + 3 входит в разложение этого числа в четной степени.

Теорема Гаусса

Правильный n-угольник с нечетным числом сторон может быть построен с помощью циркуля и линейки тогда, и только тогда, если число n является простым числом Ферма или произведением нескольких различных простых чисел Ферма.
114. Найдите все нечетные числа n < 50, для которых можно с помощью циркуля и линейки построить правильный n-угольник.
115. Как можно построить правильный 51-угольник, имея правильный 17-угольник?
116. Если не существует простых чисел Ферма, кроме известных пяти, то сколько существует нечетных n таких, что правильный n-угольник может быть построен с помощью циркуля и линейки?

Литература

1. Н. Б. Алфутова, А. В. Устинов. Алгебра и теория чисел. М.: МЦНМО, 2009.
2. Арифметика в Википедии.
3. И. М. Гельфанд, А. Шень. Алгебра. М.: Фазис, 1998.
4. О. Оре. Приглашение в теорию чисел. М.: Наука, 1980. Библиотечка «Квант», вып. 3.
5. Г. Штейнгауз. Сто задач. М.: Наука, 1982.
6. А. В. Спивак. Математический праздник. М.: МЦНМО, 1995.
7. А. В. Спивак. Суммы квадратов.
8. Журнал Квант 5/1992, 7/1992.
9. H. B. Meyer. Перечисление магических квадратов.