Условие
Для натурального n положим P=n⁵−n. а) Докажите, что P делится на 30. б) Найдите все остатки n modulo 77, при которых P делится на 2310. в) Найдите наименьшее n≥250, для которого P делится на 2310.
Подсказка
Шаг 1 для варианта 3: Разложите n⁵−n=n(n−1)(n+1)(n²+1) и отдельно докажите делимость на 2, 3 и 5.
Шаг 2 для варианта 3: Для дополнительных множителей 7 и 11 исследуйте n≡0, ±1 и возможность n²≡−1; затем совместите условия по китайской теореме.
Показать ответ
а) делится; б) 0, 1, 21, 22, 34, 43, 55, 56, 76; в) 252
Пошаговое решение
- Намечаем ход решения
Разложите n⁵−n=n(n−1)(n+1)(n²+1) и отдельно докажите делимость на 2, 3 и 5. Для дополнительных множителей 7 и 11 исследуйте n≡0, ±1 и возможность n²≡−1; затем совместите условия по китайской теореме.
- Пункт а
а) Среди n−1,n,n+1 есть множитель 2 и множитель 3, поэтому P делится на 6.
- Выполняем преобразование
По малой теореме Ферма n⁵−n делится на 5.
- Выполняем преобразование
Значит, P делится на 30.
- Пункт б
б) Для делимости на 2310=30·7·11 нужны ещё множители 7 и 11.
- Выполняем преобразование
По каждому из модулей n(n−1)(n+1)(n²+1)≡0.
- Выполняем преобразование
Число −1 не является квадратом ни modulo 7, ни modulo 11, поэтому n≡0,±1 по каждому модулю.
- Выполняем преобразование
Девять сочетаний дают по модулю 77 остатки 0, 1, 21, 22, 34, 43, 55, 56, 76.
- Пункт в
в) Перебираем только эти классы в периоде 77.
- Выполняем преобразование
Первое допустимое число не меньше 250 равно 252; непосредственная подстановка подтверждает делимость.
Ответ: а) делится; б) 0, 1, 21, 22, 34, 43, 55, 56, 76; в) 252