Задача 60821

Темы:    [ Китайская теорема об остатках ] [ Малая теорема Ферма ] [ Теорема Эйлера ]

Сложность: 4- Классы: 9,10,11

Условие

Найдите остатки от деления:  а) 19¹⁰ на 6;   б) 19¹⁴ на 70;   в) 17⁹ на 48;   г) 14¹⁴¹⁴ на 100.

Решение

  а)  19¹⁰ ≡ 1 (mod 2),  19¹⁰ ≡ 1¹⁰ = 1 (mod 3).  Кроме того, по малой теореме Ферма  19¹⁰ ≡ 1 (mod 11).

  б)  19¹⁴ ≡ 1 (mod 2),  19¹⁴ ≡ (–1)¹⁴ = 1 (mod 5),  19¹⁴ ≡  19² ≡ (–2)² = 4 (mod 7).

  в)  17⁹ ≡ 1⁹ = 1 (mod 16),  17⁹ ≡ (–1)⁹ = –1 (mod 3).

  г)  ¹⁴¹⁴ ≡ 0 (mod 4).
  φ(25) = 20,  14¹⁴ ≡ 0 (mod 4),  14¹⁴ ≡ (–1)¹⁴ = 1 (mod 5),  значит,  14¹⁴ ≡ 16 (mod 20).
  14¹⁴¹⁴ ≡ 14¹⁶ = (196)⁸ ≡ (–4)⁸ = (16)⁴ ≡ (–9)⁴ ≡ (6)² = 36 (mod 25).

Ответ

а) 1;  б) 11;  в) 17;  г) 36.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	6
Название	Китайская теорема об остатках
Тема	Деление с остатком. Арифметика остатков
задача
Номер	04.195