Бесконечная последовательность семерок

[Gepidium]

Здраствуйте.
Застряла я на хитрой задаче из сборника

Collection of problems in advanced mathematics, Technion, 2011 писал(а):

Problem 7.11
Prove that in the sequence of numbers $7, 77, 777, 7777,... $ there is one that is divisible by $9589$.

Я уже решала похожие задачи. Понимаю, что надо проанализировать остатки по $\mod{9589}$. Но остатки от деления каких чисел? Ведь последовательность дана бесконечная. И я в затруднении.

[Drimacus]

Gepidium в сообщении #1626631 писал(а):

Здраствуйте.
Застряла я на хитрой задаче из сборника

Collection of problems in advanced mathematics, Technion, 2011 писал(а):

Problem 7.11
Prove that in the sequence of numbers $7, 77, 777, 7777,... $ there is one that is divisible by $9589$.

Я уже решала похожие задачи. Понимаю, что надо проанализировать остатки по $\mod{9589}$. Но остатки от деления каких чисел? Ведь последовательность дана бесконечная. И я в затруднении.

Нет, задача в том, чтобы доказать, что какое-то число вида $111111$ делится на любое заранее фиксированное нечетное число, не кратное 5. А это легко следует из теоремы Эйлера для числа $10$ (берете ваше нечетное число $n$, пишете теорему Эйлера $10^{\phi(n)} = 1 \mod n$).
Никакие остатки анализировать, естественно, не нужно, вместо вашего числа могли написать условно $7^{9999^{9999}}+13^{5000!}+1$.

[Gepidium]

Drimacus
Немного не поняла, вы сначала сказали, что использовать малую теорему Ферма, а теперь - теорему Эйлера. Поясните, пожалуйста.

[Drimacus]

Gepidium в сообщении #1626638 писал(а):

Drimacus
Немного не поняла, вы сначала сказали, что использовать малую теорему Ферма, а теперь - теорему Эйлера. Поясните, пожалуйста.

Не буду вам ничего пояснять, и так решение написал. Если непонятно как дальше, то что тут сказать - печально быть вами.
Малая теорема ферма это частный случай теоремы Эйлера для простого числа, так что сути не меняет, но с Эйлером будет проще и быстрее.
Да, еще будет мелкая деталь с дополнительной делимостью на 9, тоже сами с ней справляйтесь.

[TOTAL]

Gepidium в сообщении #1626631 писал(а):

Понимаю, что надо проанализировать остатки по $\mod{9589}$. Но остатки от деления каких чисел?

Правильно, анализируйте остатки. Числа через запятую даны в условии.

[Gagarin1968]

Gepidium в сообщении #1626631 писал(а):

Понимаю, что надо проанализировать остатки по $\mod{9589}$

Drimacus в сообщении #1626633 писал(а):

Никакие остатки анализировать, естественно, не нужно

TOTAL в сообщении #1626649 писал(а):

Правильно, анализируйте остатки

Остатки анализировать таки нужно плюс принцип Дирихле.
Задача, похоже, олимпиадная.

[Drimacus]

Gagarin1968
А что, теорема Эйлера не решает задачу, по-вашему? А если решает, то какой смысл придумывать дополнительные искусственные трюки, теорема сама фундаментальна и элементарна, трюки все равно будут сведением или к ней, или к нахождению обратимых элементов кольца вычетов.
(Как доказать ТЭ - вопрос другой, и прямым перебором остатков это не лучший способ, слишком много придется фильтровать, а через мультипликативность почти очевидно).

[Null]

(Оффтоп)

Drimacus в сообщении #1626657 писал(а):

А что, теорема Эйлера не решает задачу, по-вашему?

Принцип Дирихле проходиться в математическом кружке раньше теоремы Эйлера и, когда я учился, оба метода не входили в стандартный школьный курс. И придумать его самостоятельно проще.

[iifat]

Gagarin1968 в сообщении #1626656 писал(а):

Остатки анализировать таки нужно

А что там анализировать? Остатки не превышают 9589, вот и весь необходимый анализ.

Drimacus в сообщении #1626657 писал(а):

теорема Эйлера не решает задачу, по-вашему?

Ну, скажем так, не бросающимся мне в глаза способом.

[Drimacus]

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

[Gepidium]

Gagarin1968 в сообщении #1626656 писал(а):

плюс принцип Дирихле.

Во, как упомянули принцип Дирихле, так на меня сразу просветление нашло.
Берем первые $9589$ чисел данной последовательности.
Если предположить, что ни одно из этих чисел не делится на $9589$, то по принципу Дирихле по крайней мере два из них имеют одинаковые остатки от деления на $9589$.
Значит их разность $777\ldots 777000\ldots 000$ делится на $9589$.
А вот дальше ступор. Не могу сообразить.

-- 21.01.2024, 12:41 --

Drimacus в сообщении #1626670 писал(а):

надо было подождать, пока тс напишет хоть что-то вразумительное, а не писать решение и еще и получать хамство в ответ.

Drimacus
Я хамила? Когда?? Где???

[Null]

$777770000=77777\times 10000$

[Gepidium]

Null в сообщении #1626677 писал(а):

$777770000=77777\times 10000$

Null
Спасибо, наконец-то дошло.
Поскольку $9589$ не делится ни на $2$, ни на $5$, то оно взаимно просто со второй частью разности (степени десятки), которая является сомножителем.
И значит, что на $9589$ делится первая ("семерочная") половина.
Так?

[Ende]

Drimacus
Спокойнее, пожалуйста. Никакого хамства со стороны ТС я не усматриваю, а вот с Вашей усмотреть легко. Будьте добры соблюдать вежливость.

[iifat]

Gepidium в сообщении #1626678 писал(а):

Так?

Так.