Делимость на 7

[Ian]

Пусть [math]3^n+4^n делится на n, n>1. Доказать что n делится на 7
Самому как-то не верится....

[zykov]

Эта сумма делится на 7 при нечётных n, т.к. по модулю 7 число "4" равно числу "-3".
Эта сумма нечётная (как сумма чётного и нечётного), значит она не делится на n, если это n чётно.

Т.е. если сумма делится на n, то это n нечётно. А раз нечётно, значит сумма делится на 7.
Осталось доказать, что именно n делится на 7 (а не сумма делённая на n).

Попробовал численно проверить до 150000.
Сумма делится на n, если n имеет в разложении только 7 (степени 1 и выше) и может иметь 379.
Может выше ещё какие множители вылезут...
(Почему именно 379 - не ясно... Может из-за того что [math]379=7^3+6^2.)

[Ian]

Вот и меня достало, хотя кроме n=7 , других n, удовлетворяющих условию задачи, я не успел найти. А у Вас какие?
Возможно, преподаватель ошибся и имел в виду такое решение [math](3^n-3)+(4^n-4) якобы тоже делится на n по теореме Эйлера, значит 7 делится на n, n=7 , но это Вы уже опровергли. На n делится не [math]3^n-3, а [math]3^{\varphi (n)+1}-3, что при n не простом не одно и то же

[zykov]

Проверил до 300k нечётные и до 3M кратные 7.
В этом диапазоне сумма делится на n только для n вида [math]7^k \, 379^m, где [math]k \geq 1, \, m \geq 0. Причём на все такие, без пропусков.
Значит похоже верно, что любое такое n делится на 7. Но как доказать, пока не вижу.

Ещё пробовал по биному Ньютона разложить [math]3^n+(7-3)^n.
Для нечётных n там [math]3^n сокращается. Остаётся [math]7^n и сумма с биномиальными коэффициентами более 1.
Отсюда например следует, что если n - простое неравное 7, то эта сумма на n не делится.

[zykov]

Source of the post Почему именно 379 - не ясно...

Понял, почему. Потому что [math]3^7+4^7 = 7^2 \cdot 379.

Думаю, можно обобщить задачу так - если для двух натуральных [math]a и [math]b, таких что [math]a+b=p, где [math]p простое, верно что [math]a^n+b^n делится на [math]n, то это [math]n делится на [math]p.

Посмотрел аналогичную задачу (размером поменьше), где [math]2^n+3^n делится на [math]n.
Тут [math]n может быть степенями 5, потом может быть 5 в степени 1 и выше умноженное на степень 11, ещё может быть 5 в степени 2 и выше умноженное на степень 1201, ещё может быть 5 в степени 3 и выше умноженное на степень 251, ещё может быть 5 в степени 3 и выше умноженное на степень 1201*251.
11 возникает потому что [math]2^5+3^5=5^2 \cdot 11.
1201 возникает потому что [math]2^{25}+3^{25}=5^3 \cdot 11 \cdot 1201 \cdot 513101. Кстати 513101 на 5 в степени 2 и выше тоже подходит.
251 возникает потому что [math]2^{125}+3^{125}=5^4 \cdot 11 \cdot 251 \cdot 1201 \cdot 513101 \cdot 27884532843001 \cdot 14726555364585012892444440090751.

Отсюда можно предположить, что для 3 и 4 будут и другие кроме 379.
Например [math]3^{49}+4^{49}=7^3 \cdot 379 \cdot 74163546829 \cdot 32871239562379. Т.е. ещё пара чисел возникла.

[zykov]

Есть вот такая идея, правда не до конца доводит.
Пусть [math]n=m\cdot p, где [math]p простое (другое, не то что в предыдущем).
Тогда [math](a^m+b^m)^p=a^n+b^n+P(a^m,b^m), где [math]P(a,b) - полином из биномиальных коэффициентов более 1. Т.к. [math]p простое, то все эти биномиальные коэффициенты делятся на [math]p, значит и сумма делится на [math]p.

Получается, что "[math]a^m+b^m делится на [math]p" эквивалентно "[math]a^{m p}+b^{m p} делится на [math]p".

Например [math]3^7+4^7 делится на 379, значит [math]3^{7\cdot 379}+4^{7\cdot 379} делится на 379.
Ещё оно делится на 7, значит [math]3^{7\cdot 379}+4^{7\cdot 379} делится на [math]7\cdot 379.

Нужно подумать, как это обобщить на случай, если [math]p не простое, а степень простого.

[zykov]

Source of the post Нужно подумать, как это обобщить на случай, если p не простое, а степень простого.

Не совсем ясно как.
Например [math](a+b)^9=b^9+9 a b^8+36 a^2 b^7+84 a^3 b^6+126 a^4 b^5+126 a^5 b^4+84 a^6 b^3+36 a^7 b^2+9 a^8 b+a^9.
Тут 9, 36, 126 делятся на 9, а вот 84 не делится на 9 (только на 3).
Правда [math]84 a^3 b^6+84 a^6 b^3=84 a^ 3 b^3 (a^3+b^3) и это [math](a^3+b^3) должно делится на 3, если [math](a+b) делилось на 9.

[Ian]

если для двух натуральных [math]a и [math]b, таких что [math]a+b=p, где [math]p простое, верно что [math]a^n+b^n делится на [math]n, то это [math]n делится на [math]p.

Красивая теорема. А это ведь в обычном вузе предложено студентам среди простых задач. И я думаю - по ошибке, что не противоречит интересности вопроса)

[zykov]

Самый маленький размер - доказать, что если [math]1+2^n делится на [math]n, то это [math]n делится на 3 (обратное не верно).
Может там студентов учили теории чисел и там какая-то теорема есть...
Может что из теории групп подойдёт.

[Ian]

Самый маленький размер - доказать, что если [math]1+2^n делится на [math]n, то это [math]n делится на 3

А может, в этом случае n - степень тройки? Что -то других не видно

[zykov]

Source of the post А может, в этом случае n - степень тройки? Что -то других не видно

Как минимум [math]3^2 \cdot 19 ещё подходит.

[math]1+2^3=3^2
[math]1+2^9=3^3 \cdot 19
[math]1+2^{27}=3^4 \cdot 19 \cdot 87211
[math]1+2^{81}=3^5 \cdot 19 \cdot 163 \cdot 87211 \cdot 135433 \cdot 272010961

Так что для [math]n подходят ([math]k_i целые от нуля и выше):
[math]3 \cdot 3^{k_1}
[math]3^2 \cdot 3^{k_1} \cdot 19^{k_2}
[math]3^3 \cdot 3^{k_1} \cdot 19^{k_2} \cdot 87211^{k_3}
[math]3^4 \cdot 3^{k_1} \cdot 19^{k_2} \cdot 87211^{k_3} \cdot 163^{k_4} \cdot 135433^{k_5} \cdot 272010961^{k_6}

Ещё [math]1+2^{9 \cdot 19} = 3^3 \cdot 19^2 \cdot 571 \cdot 174763 \cdot 160465489 \cdot 19177458387940268116349766612211.
Так что для [math]n подходят [math]3^2 \cdot 19 \cdot 3^{k_1} \cdot 19^{k_2} \cdot 571^{k_3}.

Вобщем тенденция ясная.
Это [math]n должно строиться из множителей, которые сами являются делителям таких чисел [math]1+2^n, начиная с самого первого [math]1+2^1=3.
Я тут подумал, что в той формулировке обобщения не требуется простота для суммы [math]a+b.
Например если рассмотреть [math]2^n+4^n, то для [math]n подходят степени 2 и степени 3 (т.к. 6 раскладывается на 2 и 3). Правда должны быть либо 2, либо 3. Вместе они не смешиваются. Так что для простой суммы это [math]n обязано делиться на это простое. Тут же [math]n обязано делится либо на 2, либо на 3.

[Ian]

Рассмотрим уравнение относительно k: [math]a^k+b^k=0 в кольце остатков по модулю n. Мы можем ограничиться случаем a,b взаимно просты с n (в смысле - n таково, что взаимно просто с a и c b ). Тогда a и b принадлежат Н - группе относительно умножения, состоящей из всех остатков, взаимно простых с n. Н не содержит нуля, содержит 1, и вместе с любым элементом содержит противоположный ему. Порядок группы Н равен [math]\varphi (n). Все степени [math]a^k,b^k в отдельности -принадлежат H. Порядки a и b делят порядок H. Из того, что уравнение имеет решение, следует, что a и b принадлежат одной и той же циклической подгруппе группы Н, являются (по модулю n) степенями некоторй образующей d. И все еще не использовано, что одно из решений уравнения это k=n. А надо доказать, что сумма a+b=p не принадлежит H, это и будет означать что n делится на p.
Далее для a=2 b=1 p=3 я могу доказать. Пусть [math]k_0- наименьшее решение уравнения (например для Вашего n=171 [math]k_0=9)
[math]n=k_0(2m+1) (n принадлежит общему решению уравнения), тогда из [math]2^{k_0}+1 делится на n следует что оно делится на [math]k_0, значит, при подстановке [math]k_0 вместо n предположение теоремы тоже верно, и так спустимся к n=3 для которого проверено

Интересно, как с этим связана теорема Зигмонди https://ru.wikipedia.org/wiki/%D0%A4%D1 ... 0%B2%D0%B0

[zykov]

Что-то дальше не идёт.
Там решение не выкладывали?

[Ian]

Ну для [math]a=2, b=1 все сделано, но это потому что мы знаем [math]2^n=-1(\mod n), а в общем случае хотелось бы знать общее значение [math]a^n=(-b)^n(\mod n). Вы свои эксперименты для [math]a=3,b=4 не могли бы уточнить - выяснить для найденных [math]n, удовлетворяющих условию, порядки [math]a и [math]b по модулю [math]n. Порядком элемента [math]a называется наименьшее [math]k>0, для которого [math]a^k=1(\mod n)
Предположительно , общее значение [math]a^n=(-b)^n(\mod n) так и окажется [math]\pm 1 а порядки будут отличаться ровно в 2 раза, причем будут максимальные (один из них равен [math]\varphi (n)). И наверное в этом причина что такие [math]n - подходящие , а другие нет

[zykov]

Да, по крайней мере для этих значений порядок 3 в два раза больше чем порядок 4.
Для 4 будет:

Source of the post И наверное в этом причина что такие n - подходящие , а другие нет

Вот это не понятно.

[Ian]

zigm.jpg (213.35 KiB) 10692 просмотра

Для a=3,b=4 переобозначим [math]p_0=p_0(n) то простое, которое существует по теореме Зигмонди, p=7 уже занято
Мне нужна табличка (только без долларов пожалуйста)
(n,удовлетворяющее условию)-(разложение n на простые множители)- (порядок числа 3 по модулю n)- (порядок числа 4 по модулю n)- [math](p_0(n))
У меня сегодня нет времени выкладывать части доказательства для произвольных a и b
Схема такая. Если n оказалось простое, доказать легко 2) n - степень простого. 3) если теорема верна для двух взаимно простых [math]n_1,n_2 и любых a,b, сумма которых проста, и [math]n=n_1n_2 удовлетворяет условиям теоремы, то и для n теорема верна (использовать мультипликативность функции Эйлера и возможно-Зигмонди).
Ясно что разные строчки Вашей будущей таблички-иллюстрация к разным случаям тут

[zykov]

Код: Выбрать все

7^1: 3
7^2: 21
7^3: 147
7^4: 1029
7^5: 7203
7^6: 50421
7^1  379: 189
7^2  379: 189
7^3  379: 1323
7^4  379: 9261

Это порядок для 4. Для 3 он в два раза больше.
Слева разложение n.

[Ian]

я опять не понял. Вы письмом можете выслать?

[zykov]

10 случаев n: 6 вариавнтов "степеней 7" и 4 варианта "степень 7 на 379".
Справа порядок для 4 по этому n. Порядок для 3 будет в два раза больше.

[Ian]

Да, спасибо, я перепутал с другими результатами для 2+1. где было n с тремя простыми делителями, интересно 3й этап доказательства проследить для него. Двойка это исключение в теореме Зигмонди, для нее и должно идти по-другому и уже сделано