Задача на нахождение НОД

[xyzman]

Необходимо доказать, что НОД чисел вида a^7 - a равен 42.

Ход решения:
Попробовать посмотреть каким числам a^7 - a кратно (они будут присутствовать в виде множителей во всех числах заданного вида). Разложим на множители:
a^7 - a = a(a^6 - 1) = a(a^3 - 1)(a^3 + 1) = a(a-1)(a^2 + a + 1)(a + 1)(a^2 - a + 1).

Т.к. a^2 + a + 1 = (a^2 + a - 6) + 7 \equiv a^2 + a - 6 = (a-2)(a+3) (mod 7)
И a^2 - a + 1 \equiv a^2 - a - 6 = (a + 2)(a-3) (mod 7), то
a^7 - a \equiv a(a-1)(a-2)(a+3)(a+1)(a+2)(a-3) (mod 7)

Получилось произведение семи последовательных целых чисел => оно кратно 1, 2, 3, 4, 5, 6, 7.
Следовательно НОД = 1\cdot2\cdot3\cdot5\cdot7, что не равно 42. В чем ошибка?

[AD]

$2^7-2$ не делится на $5$.

Добавлено спустя 1 минуту 41 секунду:

xyzman в сообщении #186735 писал(а):

Получилось произведение семи последовательных целых чисел => оно кратно 1, 2, 3, 4, 5, 6, 7.

Они только по модулю 7 последовательные.

[xyzman]

Хм...Как же доказать тогда?

[gris]

xyzman писал(а):

a^7 - a \equiv a(a-1)(a-2)(a+3)(a+1)(a+2)(a-3) (mod 7)

Этим Вы доказали, что любое число такого вида делится на 7.
А выше доказали, что оно делится на 6, так как имеет сомножители $(a-1)a(a+1)$
Достаточно рассмотреть $a=2$ и $a=3$, чтобы убедиться, что других сомножителей в НОД нет.

[xyzman]

Цитата:

Достаточно рассмотреть $a=2$ и $a=3$, чтобы убедиться, что других сомножителей в НОД нет.

А можно доказать без рассмотрения непосредственных значений $a$? Ведь степень может быть и трехзначным числом. Просто так не возвести и тем более не разложить.

[gris]

Вам надо доказать, что 42 это НОД вообще всех таких чисел.
У конкретной пары может быть и больший НОД. Ну, например, возьмите $a=5$ и $a=15$.

[xyzman]

Мы доказали, что 2, 3, 7 являются делителями всех чисел вида $a^7-a$. Но ведь ни кто не обещал, что какие-то другие простые числа не будут так же делителями всех чисел вида $a^7-a$. Для того, что бы убедиться в обратном gris предложил рассмотреть $a = 2$ и $a = 3$. Действительно $2^7 - 2 = 2*3^2*7$, $3^7 - 3 = 2^3*3*7*13$ => $gcd(2^7 - 2, 3^7-3) = 2*3*7$, а значит и НОД всех таких чисел будет равен 42.

Вопрос 1: можно убедиться "в обратном" без подстановки конкретных значений?

[gris]

Для опровержения какого-либо утверждения достаточно одного контрпримера. Мы опровергли предположение, что НОД больше 42.

[xyzman]

Все верно, но как Вам удалось с первого раза подобрать нужные числа? Что это - простое везение или тонкий расчет?

[gris]

Я взял самые первые значения.
Я понимаю, что Вас смущает. В в этой задаче контпример подбирается легко, но в другой задаче может понадобиться тупой перебор тысяч пар. То есть метод подбора контрпримера нельзя считать универсальным.
Но очень часто для прояснения ситуации вполне можно вручную (на компьютере) посчитать несколько членов ряда, несколько значений функции, какие-то частные случаи.
Часто помогает.