2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача на нахождение НОД
Сообщение16.02.2009, 14:40 
Необходимо доказать, что НОД чисел вида 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. В чем ошибка?

 
 
 
 
Сообщение16.02.2009, 14:51 
$2^7-2$ не делится на $5$.

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

xyzman в сообщении #186735 писал(а):
Получилось произведение семи последовательных целых чисел => оно кратно 1, 2, 3, 4, 5, 6, 7.
Они только по модулю 7 последовательные.

 
 
 
 
Сообщение16.02.2009, 15:08 
Хм...Как же доказать тогда?

 
 
 
 Re: Задача на нахождение НОД
Сообщение16.02.2009, 15:17 
Аватара пользователя
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$, чтобы убедиться, что других сомножителей в НОД нет.

 
 
 
 Re: Задача на нахождение НОД
Сообщение16.02.2009, 16:18 
Цитата:
Достаточно рассмотреть $a=2$ и $a=3$, чтобы убедиться, что других сомножителей в НОД нет.


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

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

 
 
 
 
Сообщение17.02.2009, 14:30 
Мы доказали, что 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: можно убедиться "в обратном" без подстановки конкретных значений?

 
 
 
 
Сообщение17.02.2009, 14:58 
Аватара пользователя
Для опровержения какого-либо утверждения достаточно одного контрпримера. Мы опровергли предположение, что НОД больше 42.

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

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group