Доказать, что для любых натуральных $% a $% и $% b $% существует бесконечно много целых чисел $% n $% таких, что $% a^{n}+1 $% не делится на числа $% n^{b}+1$%.

Для начала положим, что $%a$% - четно. Тогда для любого нечетного $%n$% выполняется требуемое. Пусть тогда $%a$% нечетно. Предположим противное: пусть существует конечное количество чисел $% a^{n}+1 $%, которые не делятся на числа $% n^{b}+1$%. Пусть число $% a^{n-1}+1 $% последнее из таких. Все остальные числа $% a^{n+i}+1 $% делятся на соответствующие им числа $% (n+i)^{b}+1 $%, $% i=0,1,2... $% Рассмотрим два числа: $% a^{n}+1 $% и $% a^{n+k}+1 $%, где $%k$% - нечетное число. Тогда НОД этих двух чисел равен 2, поскольку показатели степени разной четности. По предположению $% a^{n}+1 \; \vdots \; n^{b}+1 $% и $% a^{n+k} +1 \; \vdots \; (n+k)^{b}+1 $%.

Пусть число $% n+k $% оканчивается на 2, а число $% n $% оканчивается на 3 (этого возможно добиться при бесконечном количестве $%k$%). Значит существует бесконечно много значений таких, что $%(n+k)^{b}+1$% и $%n^{b}+1$% имеют по крайней мере один общий делитель, равный 5. Тогда и числа $% a^{n}+1 $% и $% a^{n+k}+1$% имеют общий делитель 5. Но НОД этих чисел равен 2. Противоречие. Значит существует бесконечно много чисел $% a^{n}+1 $%, которые не делятся на числа $% n^{b}+1$%, что и требовалось.

задан 7 Авг 1:54

изменен 7 Авг 22:30

@guerrino: откуда взялся вывод, что НОД двух чисел равен 2? Ведь дальнейшие рассуждения это опровергают.

(7 Авг 13:46) falcao
1

@falcao, я так понимаю, что молодой человек предлагает следующий план: существует много пар разной четности $%(n_1, n_2)$% таких, что $%\gcd(n_1^b+1, n_2^b+1) = 5d$% (в своем доказательстве, правда, он неявно предполагает b=2). А для таких чисел $%\gcd(a^{n_1}+1, a^{n_2}+1) = 2$% (а - нечетно). Последнее утверждение кажется весьма смелым, но ни доказать, ни привести контрпример у меня сходу не получается. Возможно только лишь из-за нехватки времени. Эта задача не выглядит сложной.
А второй НОД должен делиться на первый в предположении противного.

(7 Авг 17:21) spades

@spades: да, Вы правы. Но факт насчёт НОД=2 надо всё-таки сопроводить доказательством. Хотя я сейчас прикинул -- это действительно верно (там алгоритм Евклида работает достаточно понятным образом).

(7 Авг 21:21) falcao

Утверждение верное, причем довольно тривиально. Ведь если $%x^n \equiv -1 \pmod p$%, то $% ord(x)$% в $% \mathbb Z_p^*$% чётен.

(8 Авг 10:38) spades
1

@spades: аргумент с порядками я понимаю так. Пусть d=НОД двух чисел. Тогда x^{2k}=-1(mod d) и x^m=-1(mod d), где m нечётно. Тогда x^{2km} сравнимо как с -1, так и с 1, откуда d делит 2.

(8 Авг 14:09) falcao

@falcao, так действительно совсем просто и понятно.

(8 Авг 14:39) spades
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
1

Перед тем, как спрашивать о правильности решения, надо правильно сформулировать условие задачи. В задаче говорится: "Для любых натуральных $%a,b$%, и для любого целого $%n$% доказать, что существует бесконечно много чисел $%a^n+1$% ...". У вас в условии фиксированными являются все три числа $%a,b,n$%. О какой бесконечности может идти речь? Для любых натуральных $%a,b$%, и для любого целого $%n$% существует ровно одно число вида $%a^n+1$%. Но догадатся можно, что вы хотели сказать. Вам надо было спросить: "Доказать, что для любых $%a,b$% найдется бесконечно много $%n$% таких, что ...". Хотя откуда мне это знать? Может у вас наоборот фиксированное $%n$%, а $%a,b$% - нет. Вы не написали условия задачи. Поэтому нечего обсуждать.

ссылка

отвечен 7 Авг 12:23

Доказать, что для любых а и в, найдется бесконечно много n таких, что... — это имелось ввиду

(7 Авг 12:27) guerrino

@guerrino - так отредактируйте условие...

(7 Авг 21:52) knop
10|600 символов нужно символов осталось
0

@guerrino, в последнем абзаце у вас ошибка. То, что вы пишете, справедливо для $%b$% вида $%4d+2$%. Можно также подобрать n для $%b=4d \pm1$%. Но вот для $%b=4d \quad n^b+1$% не делится на 5 ни при каком $%n$% .

ссылка

отвечен 8 Авг 15:06

изменен 8 Авг 15:07

Будем рассматривать нечетные $%n$%.Рассмотрим число $%n^{b}$%.Пусть это число дает остаток $%q-1$% при делении на $%q$% и $%qx=2^{b}-1$% при некотором x(Полагаем,что $%q$%-нечетно).Из вышесказанного:$%n^{b}\equiv q-1\;mod\;q$%.()Пусть $%k=(2m-1)n$%,причем $%m^{b}\equiv 1\;mod\;q$%.Итак:$%n+k=2mn$%;Домножив обе части в () на $%(2m)^{b}$% получаем $%(2mn)^{b}\equiv (2m)^{b}(q-1)\;mod\;q$%.С учетом вышесказанного $%(2mn)^{b}\equiv q-1\;mod\;q$%, что равнозначно $%(n+k)^{b}\equiv q-1\; mod\;q$%;Значит числа $%n^{b}+1$% и $%(n+k)^{b}+1$% делятся на q, но в силу разной четности q>2 Теперь верно?

(9 Авг 1:04) guerrino

@guerrino,когда вы выбираете числа по некоторым условиям, необходимо первым делом проверить, что это возможно.
В данном случае, предъявите n и q для b=4

(9 Авг 10:45) spades

Поправка к моему предыдущему комментарию: правильнее считать $% (2m)^{b} \equiv 1\;mod\;q$% Отсюда при b=4: $%16m^{4}=qx+1$%; Пусть n=19 и q=17; Тогда n+k=76 или 304 или 342. Тогда числа $%19^{4}+1$% и $%(19+57)^{4}+1$% имеют общий делитель 17. Также и для n+k=304 и 342

(11 Авг 1:15) guerrino

у вас $%qx=2^b-1=15$%. Как оказалось, что $%q=17$%?

(11 Авг 11:09) spades

Тогда я считал, что $%m^{b}$% дает остаток 1 при делении на q. Оказалось, что при b=4 достичь желанного нельзя и поэтому в предыдущем комментарии я отказался от этого и положил, что число $%(2m)^{b}$% дает остаток 1. Равенство $%qx=2^{b}-1$% следует именно когда остаток от деления m^b на q равен 1, то есть это равенство уже не актуально

(11 Авг 17:36) guerrino
1

Ну так запишите свое доказательство заново.
В доказательстве надо также показать, что все случаи реализуемы. Например, не очевидно, что есть число (2m)^b дающее остаток 1.

(12 Авг 8:35) spades
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,021

задан
7 Авг 1:54

показан
167 раз

обновлен
12 Авг 8:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru