Помогите разобраться, как решать такие задачи. Делимость mod

[Shadow]

alexo2 в сообщении #585654 писал(а):

Кстати, по многим задачам из списка - элементарно решаются с применением МТФ.

11-ая кажется не совсем тривиальная (или я упускаю очень простое доказательство). Можно свести к "доказать, что для любого простого $N \ne 2, \ne 5$, существует натуральное число, состоящее только из троек, делящееся на N. Тут МТФ конечно годится, но интересно есть ли более простой способ.

Я имею ввиду оригинальную задачу. Ведь всех остальных можно решить и без МТФ

[alexo2]

По 11-ой задаче - да, можно решить проще - из возможных приписываемых цифр подходят только 1, 3 и 7, все остальные сразу дают составное число.

[Shadow]

Так это понятно. 1 и 7 увеличивают на единичку остаток по модулю 3, так что их можно применить только 1 раз. И осталось рассмотреть добавление одних троек. И как без МТФ?

[Ktina]

Shadow в сообщении #585722 писал(а):

Так это понятно. 1 и 7 увеличивают на единичку остаток по модулю 3, так что их можно применить только 1 раз. И осталось рассмотреть добавление одних троек. И как без МТФ?

Опять сводится к задаче "первоклассник Петя знает только цифру 1".

-- 24.11.2012, 12:28 --

Смотрите:
С некоторого момента Вы станете приписывать только троечки. Рассмотрите число, получившееся после приписывания первой из этих троечек. Если оно составное, то задача решена. Если простое -- значит, взаимопросто с 2, 3 и 5. Далее, приписываем репдиджит из троечек, делящийся на это число (а он существует, см. задачу "первоклассник Петя знает только цифру 1"). После этого получаем составное число!

[Ktina]

ZARATUSTRA в сообщении #585306 писал(а):

8. Найдите три попарно взаимно простых числа таких, что сумма любых двух из них делится на третье.

Например, 1, 2 и 3.
А можно ещё проще: 1, 1 и 1. Ведь не сказано, что одинаковых чисел быть не должно

[pcyanide]

Ktina в сообщении #1211195 писал(а):

ZARATUSTRA в сообщении #585306 писал(а):

8. Найдите три попарно взаимно простых числа таких, что сумма любых двух из них делится на третье.

Например, 1, 2 и 3.
А можно ещё проще: 1, 1 и 1. Ведь не сказано, что одинаковых чисел быть не должно

Еще один пример: любые два нечетных простых числа и число 2. Кстати, если в условии заменить «взаимно простые» на «простые», тоже подойдет. Можно обойтись и простыми нечетными, напр 11, 3, 7.

Кстати, не кажется кому-нибудь, что слишком много решений?

-- 21.12.2017, 17:29 --

Задача 9. Неужели до сих пор не решена? Или я не заметил. Дело в том, что 1 и 5 — это единственные остатки, взаимно простые с 6. Для всех остальных число делится на 2 и/или на 3.

-- 21.12.2017, 17:44 --

ZARATUSTRA в сообщении #585306 писал(а):

7. Шестизначное число делится на 7. Докажите, что, если последнюю его цифру переставить в начало, то полученное число тоже будет делиться на 7.

$a$ - последняя цифра, $b$ - число составленное из предыдущих цифр.

До перестановки: $M=10b+a$ делится на 7 по условию.

После перестановки: $N=10^5a+b$.

$$ 10N=10^6a+10b=(10^6-1)a+a+10b=999999a+(10a+b)=7\cdot142957a+M $$

.

Таким образом $10N$ делится на 7. Т.к. 10 и 7 взаимно простые, $N$ также делится на 7.

-- 21.12.2017, 17:54 --

ZARATUSTRA в сообщении #585306 писал(а):

10. Докажите, что если сумма квадратов двух чисел делится на 3, то и каждое из этих чисел тоже делится на 3

Если $a=3k \pm1 $ то $a^2=3(3k^2 \pm 2k)+1$, т.е. $a^2\equiv 1 \mod 3$, если $a$ не делистся на 3. Если одно из чисел не кратно 3, то суммарный остаток на 3 будет либо 1, либо 2, так что сумма не кратна 3.

[pcyanide]

Ktina в сообщении #648851 писал(а):

С некоторого момента Вы станете приписывать только троечки. Рассмотрите число, получившееся после приписывания первой из этих троечек. Если оно составное, то задача решена. Если простое -- значит, взаимопросто с 2, 3 и 5. Далее, приписываем репдиджит из троечек, делящийся на это число (а он существует, см. задачу "первоклассник Петя знает только цифру 1"). После этого получаем составное число!

На 5 и на 2 число не разделится, сколько ни дописывай троек! На 3 или 9 оно разделится только если изначально делилось на 3, что совсем интересно. Смотрел я задачу про первоклассника Петю. Ну нашли мы два числа из единиц с одинаковыми остатками, а дальше? Если дописывать, остаток ведет себя совершенно непредсказуемо. (Это ведь на деление на 3 или 9!) С 11 тоже не получается, так как разность чисел на четных и нечетных местах будет колебаться среди двух значений. Или я что-то не улавливаю?

[Deggial]

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

[pcyanide]

ZARATUSTRA в сообщении #585306 писал(а):

5. Докажите, что если целочисленная арифметическая прогрессия содержит квадрат целого числа, то она содержит бесконечно много квадратов целых чисел.

Мне пришло замечание за выкладывание решений. По-моему, здесь далеко не все тривиально, иначе бы не писал. Пишу в последний раз и по-английски. Во-первых не придется переключать регистры (какое облегчение!). Во-вторых, авось обойдется:

Analysis. Assume for some $n$, $a+dn=p^2$. Then $p^2-a$ is a multiple of $d$. We need to increase $p$ by some $q$, so that $(p+q)^2-a$ is also a multiple of $d$. So, we have

$$ \frac{(p+q)^2-a}{d} = \frac{p^2+2pq+q^2-a}{d} = \frac{p^2-a}{d} +\frac{q(2p+q)}{d} $$

Let $q=kd$, where $k>1$ then the new index $m = n+k(2p+kd)$

Solution. If $a+dn=p^2$, take member with index $m = n+k(2p+kd)$, where $k>1$. Then

$$ a+dm = a+d[n+k(2p+kd)] = a+dn+2dpk+d^2k^2 = p^2+2dpk+d^2k^2=(p+dk)^2 $$

q.e.d.

[pcyanide]

Shadow в сообщении #585722 писал(а):

Так это понятно. 1 и 7 увеличивают на единичку остаток по модулю 3, так что их можно применить только 1 раз. И осталось рассмотреть добавление одних трое

Пришел к довольно интересному выводу (проверьте логику на отсутствие ошибок). Не решает (но и не опровергает), поэтому выкладываю без опасений:

Для любого простого p>3 существует единственный положительный остаток при делении на p, сохраняемый при дописывании 3.

Доказательство. $a$ - исходное число, $b=10a+3$ – число после дописывания. Разность $9a+3$. Надо найти a, такое, что 0<a<p и 9а+3 кратно p. Так как 9 и p — взаимно прстые, то набор чисел $\{9a\}_{a=1}^{p-1}$, дает полную систему вычетов по модулю $p$. Следовательно для некоторого ( и единственного) $a \in [1,p-1]$, $9a \equiv (p-3) \mod (p)$, откуда $9a+3$ кратно $p$.

Примеры это подтвержают. Вот вычеты по модулю 7 для $a$ и $10a+3$: 1-6, 2-2, 3-5, 4-1, 5-4, 6-0.
То же по модулю 13: 1-0, 2-10, 3-7, 4-4, 5-1, 6-11, 7-8, 8-5, 9-2, 10-12, 11-9, 1-6.
(Закономерность хорошо видна, так что на самом деле не обязательно искать остатки).

Проблему создает число, которое при делении на 7 и 13 дает остатки 2 и 4 соответственно.

Решая целочисленное уравнение $7x+2=13x+4$ находим $x=13t+4; y=7t+2$, откуда искомое число $a=91t+30$.

Далее находим «неприятный» остаток $q$ для 17 и решаем: $91t+30=17u+q$ и т.д. процесс, который не может продолжаться бесконечно.

Однако не скажу, чтобы мне это очень нравилось Не выглядит достаточно убедительно.

К тому же (как мне кажется) такое рассуждение могло бы работать и для дописывания девяток. Тем не менее автор задачи 9 исключил, а 3 оставил. С чего бы это?

PS. Вероятно 9 исключено, чтобы не было возможности дописывать 3 и 9 вперемежку. Это усложнило бы задачу.

[pcyanide]

pcyanide в сообщении #1277926 писал(а):

Однако не скажу, чтобы мне это очень нравилось Не выглядит достаточно убедительно

Могут быть бесконечные циклы. Например, для 13: 2-10-12-6-11-9-2 или для 11: 1-2-1-2... Так, что в рассуждении есть явный изъян.

[Shadow]

pcyanide в сообщении #1277926 писал(а):

Для любого простого p>3 существует единственный положительный остаток при делении на p, сохраняемый при дописывании 3.

Правильно, это решение уравнения $3a+1=p$, если $p\equiv 1 \pmod 3$, и $3a+1=2p$, если $p \equiv 2 \pmod 3$

pcyanide в сообщении #1277938 писал(а):

Могут быть бесконечные циклы. Например, для 13: 2-10-12-6-11-9-2 или для 11: 1-2-1-2... Так, что в рассуждении есть явный изъян.

Точно. Не только "неподвижный" остаток плохой.
А значит по конкретному модулю (модулям) задачу не решить.

[pcyanide]

Shadow в сообщении #1277954 писал(а):

Правильно, это решение уравнения $3a+1=p$, если $p\equiv 1 \pmod 3$, и $3a+1=2p$, если $p \equiv 2 \pmod 3$

Так, действительно, гораздо проще. И не приходится делать перебор.

[pcyanide]

Поставим, все точки над i по поводу задачи 11.


Пусть $p$ - первоначальное простое число.

Для $p=2,3,5$ имеем

$$ \begin{matrix} 233333=353 \cdot 661 \\ 33=3 \cdot 11 \\ 533=13 \cdot 41 \end{matrix} $$

(Спасибо Divisor's Calculator за помощь.)

Поэтому будем считать $p$ отличным от этих чисел.

Добавляя $n$ троек получаем: $10^{n}p+\frac{10^n-1}{3}$. Если мы докажем, что $10^n-1$ кратно $p$ для некоторого $n$, то поскольку $p$ и $3$ взаимно простые, тем самым будет доказано, что $\frac{10^n-1}{3}$ а вместе с этим и все число делится на $p$. Факт делимости вытекает из МТФ, учитывая, что 10 и p — взаимно простые.

Как видим, и здесь не обошлось без МТФ. Впрочем, можно и без нее. Рассмотрим $p+1$ чисел, составленных из одних троек. Согласно принципу Дирихле, среди них найдутся равно-остаточные по модулю $p$. Разность 333..300...00 также делится на $p$, причем нули можно отбросить, благо $p$ взаимно просто с 2 и 5.

Увы, заслуга не моя. Вот источник.

[grizzly]

pcyanide в сообщении #1288810 писал(а):

Поставим, все точки над i по поводу задачи 11.

Ну раз все точки расставлены (а лишние запятые не убраны :) я задам пару вопросов, а то я не совсем понял решение.
Вопросы 1. Почему так важно в условии, что среди приписываемых цифр не должно быть цифры 9? Как это было использовано в решении?
Вопрос 2. Где в условии сказано, что каждый раз приписывается одна и та же цифра?