Взаимно простые в арифметической прогрессии

[Padawan]

Задача. Даны целые числа $n, a, d$, причём $(a,d)=1$. Доказать, что найдётся число $m$ такое, что $m\equiv a\pmod d$ и $(m,n)=1$.

Решение. Можно считать, что $n>0$. Применим индукцию по $n$. При $n=1$ доказывать нечего. Пусть утверждение верно для всех натуральных чисел, меньших $n$. Докажем для $n$. Если $(d,n)=1$, то числа вида $a+kd$ пробегают все классы вычетов по модулю $n$, когда $k=0,1,\ldots n-1$. В частности, эти числа попадают и в классы вычетов, взаимно простые с $n$. Пусть $\delta=(d,n)>1$. Тогда числа $a+kd$ при $k\in\mathbb Z$ пробегают по модулю $n$ те же классы вычетов, что и числа $a+k\delta$ при $k\in\mathbb Z$. Так как $(a,d)=1$ и $\delta|d$, то и $(a,\delta)=1$. Обозначим $n_1=n/\delta$, $n_1<n$. По предположению индукции существует $k\in\mathbb Z$ такое, что $(a+k\delta,n_1)=1$. Тогда $(a+k\delta,n)=(a+k\delta,n_1\delta)=(a+k\delta,n_1)=1$, поскольку $(a+k\delta,\delta)=(a,\delta)=1$. Для некоторого $l$ число $a+ld$ по модулю $n$ попадает в тот же класс вычетов, что и $a+k\delta$. Следовательно, $(a+ld,n)=1$. Значит, утверждение верно и для $n$. $\square$

Прошу проверить решение, нет ли неточностей или логических ошибок. И нет ли более простого доказательства, без индукции?

[nnosipov]

Padawan в сообщении #1514238 писал(а):

Прошу проверить решение, нет ли неточностей или логических ошибок.

Не нашел.

Padawan в сообщении #1514238 писал(а):

И нет ли более простого доказательства, без индукции?

Без индукции --- есть. Идея такая: рассмотреть число $n'$ --- произведение всех простых делителей числа $n$, которые не являются делителями числа $d$.

Эта теорема доказывается в брошюре: Арнольд В. И. Группы Эйлера и арифметика геометрических прогрессий. М.: МЦНМО, 2003. Но доказательство (см. стр. 9 и далее) занудно длинное, поэтому в свое время сочинил что-то покороче.

Да, разумеется, ссылка на теорему Дирихле (о простых числах в арифметических прогрессиях) была бы здесь неуместной, хотя и мгновенно решает вопрос.

[vpb]

nnosipov в сообщении #1514241 писал(а):

Но доказательство (см. стр. 9 и далее) занудно длинное,

То доказательство и есть по индукции, как у ТС. Я думаю, уместно не предагать коллеге придумать что-то другое (ибо имея одно доказательство, другое придумывается плохо; сие есть общая психологическая закономерность), а прямо это альтернативное доказательство и изложить.

А именно, разложим $n=n'n''$, где $n'$ содержит те простые множители, которые не входят в $d$, а $n''$ --- те, что входят. То, что прогрессия $a+kd$ содержит число, взаимно простое с $n'$, уже доказано. А кроме того, $a+kd$ не может делиться на простое число, делящее $d$. Т.е. с $n''$ все члены прогрессии уже взаимно просты, с самого начала. Вот как бы и всё.

[nnosipov]

vpb в сообщении #1514243 писал(а):

прямо это альтернативное доказательство и изложить

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

vpb в сообщении #1514243 писал(а):

ибо имея одно доказательство, другое придумывается плохо; сие есть общая психологическая закономерность

Ну, как сказать ... Ради спортивного интереса как-то написал 8 решений одной задачи. Если сюжет не слишком сложный, то такие методические экзерсисы имеют смысл.

[Padawan]

vpb в сообщении #1514243 писал(а):

А именно, разложим $n=n'n''$, где $n'$ содержит те простые множители, которые не входят в $d$, а $n''$ --- те, что входят. То, что прогрессия $a+kd$ содержит число, взаимно простое с $n'$, уже доказано. А кроме того, $a+kd$ не может делиться на простое число, делящее $d$. Т.е. с $n''$ все члены прогрессии уже взаимно просты, с самого начала. Вот как бы и всё.

Да, так гораздо проще. Спасибо!

[lel0lel]

Без индукции легко доказывается. Выберем из арифметической последовательности бесконечную подпоследовательность попарно взаимнопростых чисел. Например $a, d+a, d(d+a) + a, \ldots$. Конечное число $n$ может иметь общие делители только с конечным числом элементов этой последовательности.