2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

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

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение16.06.2012, 12:59 


26/08/11
1681
alexo2 в сообщении #585654 писал(а):
Кстати, по многим задачам из списка - элементарно решаются с применением МТФ.
11-ая кажется не совсем тривиальная (или я упускаю очень простое доказательство). Можно свести к "доказать, что для любого простого $N \ne 2, \ne 5$, существует натуральное число, состоящее только из троек, делящееся на N. Тут МТФ конечно годится, но интересно есть ли более простой способ.

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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение16.06.2012, 13:11 


03/02/12

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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение16.06.2012, 13:23 


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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение24.11.2012, 12:15 
Аватара пользователя


01/12/11
6198
Нацерет-Иллит
Shadow в сообщении #585722 писал(а):
Так это понятно. 1 и 7 увеличивают на единичку остаток по модулю 3, так что их можно применить только 1 раз. И осталось рассмотреть добавление одних троек. И как без МТФ?

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

-- 24.11.2012, 12:28 --

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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение21.04.2017, 00:34 
Аватара пользователя


01/12/11
6198
Нацерет-Иллит
ZARATUSTRA в сообщении #585306 писал(а):
8. Найдите три попарно взаимно простых числа таких, что сумма любых двух из них делится на третье.

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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение21.12.2017, 10:20 
Аватара пользователя


01/12/17
87
Мельбурн
Ktina в сообщении #1211195 писал(а):
ZARATUSTRA в сообщении #585306 писал(а):
8. Найдите три попарно взаимно простых числа таких, что сумма любых двух из них делится на третье.

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


Еще один пример: любые два нечетных простых числа и число 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.

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение21.12.2017, 11:23 
Аватара пользователя


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


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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение21.12.2017, 11:53 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение21.12.2017, 12:06 
Аватара пользователя


01/12/17
87
Мельбурн
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.

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение23.12.2017, 11:10 
Аватара пользователя


01/12/17
87
Мельбурн
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 вперемежку. Это усложнило бы задачу.

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение23.12.2017, 12:15 
Аватара пользователя


01/12/17
87
Мельбурн
pcyanide в сообщении #1277926 писал(а):
Однако не скажу, чтобы мне это очень нравилось :-) Не выглядит достаточно убедительно

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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение23.12.2017, 13:27 


26/08/11
1681
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... Так, что в рассуждении есть явный изъян.
Точно. Не только "неподвижный" остаток плохой.
А значит по конкретному модулю (модулям) задачу не решить.

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение23.12.2017, 14:38 
Аватара пользователя


01/12/17
87
Мельбурн
Shadow в сообщении #1277954 писал(а):
Правильно, это решение уравнения $3a+1=p$, если $p\equiv 1 \pmod 3$, и $3a+1=2p$, если $p \equiv 2 \pmod 3$


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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение31.01.2018, 13:05 
Аватара пользователя


01/12/17
87
Мельбурн
Поставим, все точки над 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.

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

 Профиль  
                  
 
 Re: Помогите разобраться, как решать такие задачи. Делимость mod
Сообщение31.01.2018, 14:16 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group