алгебра — Теория чисел
@guru, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).
1 ответ
1) Здесь 30 можно заменить на -1, а 239 на 22 (по модулю 31). Тогда первое слагаемое равно -1, а второе равно $%22^<30>$%, что сравнимо с единицей ввиду малой теоремы Ферма. В сумме получается ноль.
2) Случай $%p=3$% проверяется непосредственно: 216 делится на 18. Пусть $%p > 3$%. Тогда достаточно отдельно проверить делимость на $%6$% и на $%p$% по отдельности.
По модулю 6 заменим 7 на 1, а 5 на -1. Эти числа возводятся в нечётную степень, и разность равна $%1-(-1)=2$%. Вычитаем 2, и получается 0.
Применяя малую теорему Ферма, получаем, что $%7^p$% сравнимо с 7 по модулю $%p$%, а $%5^p$% сравнимо с 5. Итогом будет $%7-5-2=0$% по модулю $%p$%.
4. Теоремы Ферма и Эйлера
4.108. Найдите такое n, чтобы число 10 n − 1 делилось на а) 7; б) 13; в) 91; г) 819.
4.109. Докажите, что
Малая теорема Ферма. Пусть p — простое число и p — a. Тогда
4.110. Докажите теорему Ферма, разлагая (1 + 1 + . . . + 1) p посредством полиномиальной теоремы.
4.111. Пусть p — простое число, p 6= 2, 5. Докажите, что существует число вида 111 . . . 11, кратное p.
Придумайте два решения этой задачи: одно, использующее теорему Эйлера, и второе — принцип Дирихле.
4.112. Для каких n число n 2001 − n 4 делится на 11?
4.113. Докажите, что для любого натурального числа найдется кратное ему число, десятичная запись которого состоит только из 0 и 1.
4.114. Дано простое p и целое a, не делящееся на p. Пусть k — наименьшее натуральное число, такое что a k ≡ 1 (mod p). Докажите, что p − 1 делится на k.
4. Теоремы Ферма и Эйлера
4.115. С помощью индукции докажите следующее утверждение, эквивалентное малой теореме Ферма: если p — простое число, то для любого натурального a справедливо сравнение
4.116. Известно, что
a 12 + b 12 + c 12 + d 12 + e 12 + f 12 . 13.
Докажите, что abcdef . 13 6 .
4.117. Геометрическое доказательство малой теоремы Ферма. Пусть p > 2 — простое число. Сколько существует способов раскрасить вершины правильного p-угольника в a цветов? (Раскраски, которые можно совместить поворотом, считаются одинаковыми.) Получите формулу и выведите из нее малую теорему Ферма.
4.118. Найдите остатки от деления на 103 чисел а) 5 102 ; б) 3 104 .
4.119. Докажите, что число 30 239 + 239 30 — составное.
4.120. Будет ли простым число 257 1092 + 1092?
4.121. Докажите, что если p — простое число, p 6= 2, 5, то длина периода разложения 1/p в десятичную дробь делит p − 1. Приведите пример, когда длина периода совпадает с p − 1.
4.122. Пусть p — простое число. Докажите, что любой простой делитель числа 2 p − 1 имеет вид 2kp + 1.
4.123. Пусть n — натуральное число, не кратное 17. Докажите, что либо n 8 + 1, либо n 8 − 1 делится на 17.