Каталог по темам

Задачи

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 48]

Задача 60786

[Числа Кармайкла]

Тема:

[

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

]

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

Докажите, что для составного числа 561 справедлив аналог малой теоремы Ферма: если (a, 561) = 1, то a⁵⁶⁰ ≡ 1 (mod 561).

Решение

Так как 561 = 3·11·17, то достаточно доказать, что a⁵⁶⁰ ≡ 1 (mod p), где p принимает значения 3, 11, 17. Каждое такое сравнение выполняется по малой теореме Ферма.

Прислать комментарий

Задача 30681

Тема:

[

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

]

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

Пусть p и q – различные простые числа. Докажите, что
а) p^q + q^p ≡ p + q (mod pq);

б) – чётное число, если p, q ≠ 2.

Подсказка

Докажите, что p^q + q^p – p – q делится и на p, и на q.

Решение

а) По малой теореме Ферма p^q ≡ p (mod q), q^p ≡ q (mod p). Следовательно, p^q + q^p – p – q делится и на p, и на q.

б) p + q < pq, поэтому Числитель полученной дроби чётен, а знаменатель нет, следовательно, частное чётно.

Прислать комментарий

Задача 60741

Темы:	[	Малая теорема Ферма	]
	[	Индукция (прочее)	]
	[	Треугольник Паскаля и бином Ньютона	]

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

С помощью индукции докажите следующее утверждение, эквивалентное малой теореме Ферма: если p – простое число, то для любого натурального a справедливо сравнение a^p ≡ a (mod p).

Решение

При a = 0 утверждение очевидно. Предположим, что оно доказано для некоторого a ≥ 0. Из задачи 60668 следует, что (a + 1)^p ≡ a^p + 1 (mod p). Применяя предположение индукции, приходим к нужному сравнению.

Прислать комментарий

Задача 60780

Тема:

[

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

]

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

Докажите, что 7⁵¹ – 1 делится на 103.

Решение

25² = 625 ≡ 7 (mod 103), следовательно, 7⁵¹ ≡ 25¹⁰² ≡ 1 (mod 103).

Прислать комментарий

Задача 60783

Темы:	[	Малая теорема Ферма	]
Темы:	[	Арифметика остатков (прочее)	]

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

Докажите, что при любом целом a
a) a⁵ – a делится на 30;
б) a¹⁷ – a делится на 510;
в) a¹¹ – a делится на 66;
г) a⁷³ – a делится на 2·3·5·7·13·19·37·73.

Решение

a) Делимость на 2 очевидна, делимость на 5 следует из малой теоремы Ферма. Кроме того, a⁵ = a³·a² ≡ a·a² = a³ ≡ a (mod 3).

б) Делимость на 2 очевидна, делимость на 17 следует из малой теоремы Ферма, делимость на 3 доказывается аналогично а). Кроме того,
a¹⁷ = (a⁵)³·a² ≡ a³·a² = a⁵ ≡ a (mod 5).

в) Доказывается аналогично а).

г) Делимость на 2, 3, 5, 73 доказывается аналогично б); a⁷³ = (a⁷)¹⁰·a³ ≡ a¹⁰·a³ = a⁵·a⁶ ≡ a·a⁶ = a⁷ ≡ a (mod 7),
a⁷³ = (a¹³)⁵·a⁸ ≡ a⁵·a⁸ = a¹³ ≡ a (mod 13), a⁷³ = (a¹⁹)³·a¹⁶ ≡ a³·a¹⁶ = a¹⁹ ≡ a (mod 19), a⁷³ = a³⁷·a³⁶ ≡ a·a³⁶ = a³⁷ ≡ a (mod 37).

Прислать комментарий

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 48]