Задача по теории чисел и на оптимизацию перебора.

[Sonic86]

Найти все решения уравнения $n-\varphi(n)=402$, где $\varphi(n)$ - функция Эйлера.

Извините, если это уже было.
Тут понятно, что перебором можно, но как перебором лучше всего?
Или может быть можно как-то красиво решить?
Ну и в общем виде: $an-b\varphi(n)=M$

Я исправил - тут просто какой-то комп дурацкий был без слэша.

Не - а Вы попробуйте - эту задачу на олимпиаде давали детям без компьютеров

[ИСН]

Обычно всё-таки $\varphi(n)$.
Красиво не будет. Кроме почти очевидного соображения, что $n$ чётно, но не делится на 4, тут как-то ничего и не всплывает...

[bot]

Дык и перебор-то небольшой:

$$p_1^{k_1-1}p_2^{k_1-1}\dots p_s^{k_s-1} (p_1p_2\dots p_s-(p_1-1)(p_2-1)\dots (p_s-1))=2\cdot 3\cdot 67$$

[bot]

Дома глянул, превозмогая лень. Как и ожидал олимпиадного ничего не нашёл, а за учебную сойдёт. Разбор случаев и в самом деле небольшой.

Простые числа, за исключением быть может 2,3 и 67, входят в каноническое разложение $n$ однократно. Двойка, как уже сказал ИСН, входит однократно. Отсюда сразу всплывает наибольшее решение $n=802$.

1. Пусть $67^2|n.$ Тогда $n=2\cdot 3\cdot 67^2\cdot p_1p_2\dots p_s,\ 67\ne p_i>3$ и равенство $n-\varphi (n)=402 $ превращается в очевидно невыполнимое $67p_1\dots p_s-22(p_1-1)\dots (p_s-1)=1.$

2. Пусть $n=2\cdot 3^2\cdot p_1p_2\dots p_s,\ p_i>3. $ Тогда $3p_1\dots p_s-(p_1-1)\dots (p_s-1)=67.$ Сравнение по модулю 3 приводит к противоречию.

3. Пусть $n=2\cdot 3\cdot p_1p_2\dots p_s,\ p_i>3. $ Тогда $3p_1\dots p_s-(p_1-1)\dots (p_s-1)=201,\ p_i>3. $
В случаях $s=0,1$ невыполнимость равенства очевидна, при $s\geqslant 3$ минимум левой части достигается в случае $s=3,\ p_1=5,\ p_2=7,\ p_3=11$, но этот минимум больше 201.
При $s=2$ равенство преобразуется к виду $(2p+1)(2q+1)=405,\ 5\leqslant p < q$. Отсюда имеем единственное подходящее разложение $(2p+1)(2q+1)=15\cdot 27$, которое даёт решение $\fbox{n=546.}$

4. Пусть $n=2\cdot p_1p_2\dots p_s,\ p_i>3. $ Тогда $2p_1\dots p_s-(p_1-1)\dots (p_s-1)=402,\ 3<p_i\equiv -1\pmod 6$. Сравнением по модулю 3 получаем, что $s$ нечётно. Случай $s=1$ даёт решение $\fbox{n=802}$ , а при $s\geqslant 3$ минимум левой части $2\cdot 5 \cdot 11\cdot 17 - 4 \cdot 10\cdot 16 > 402$.

[Sonic86]

Я решал почти так же, только я еще число различных простых делителей учитывал.
Наверное, тут просто никак.

Пусть $n - \varphi (n) = 402 = 2 \cdot 3 \cdot 67$.
Можно видеть, что из $n - \varphi (n) = 402$ следует, что n на куб простого не делится.
При $n \neq 1;2 \varphi (n)$ делится на 2.
Пусть $n=2^vm, 2 \not |m$, тогда $ord_2(n - \varphi (n)) = m$ или $m-1$, причем последнее возможно только для $n=2^vm$. $ord_2(402)=1$, значит $v=1$ или $v=2$. Случай $v=2 \Leftrightarrow n=4$ - не подходит. Значит $v=1$.

$v=1 \Rightarrow n=2m, m$ - нечетно. Тогда
$n - \varphi (n) = 402 \Leftrightarrow 2m - \varphi (m) = 402$.
Оценка снизу: $2m > 2m - \varphi (m) = 402, m > 201$.
$m < 2m - \varphi (m) = 402$. Получили ограничение сверху - можно уже решить тупо перебором - 202 варианта.
Получим более сильную оценку снизу, исходя из оценки сверху.
$m < 402, m$ - нечетно, значит m имеет не более 3-х различных простых делителей, так как $3 \cdot 5 \cdot 7 \cdot 11 = 1155 > 402$.
$\varphi (m) \geq m(1- \frac{1}{p_1})(1- \frac{1}{p_2})(1- \frac{1}{p_3}) \geq m(1-1/3)(1-1/5)(1-1/7)= \frac{8m}{35}$
То есть $\varphi (m) \geq \frac{8m}{35}$. Значит
$402 = 2m - \varphi (m) \leq 2m - \frac{8m}{35} = \frac{62m}{35}$, то есть
$402 \cdot 35 \leq 62m \Leftrightarrow m \geq 226,93, m \geq 227$.
Таким образом $227 \leq m \leq 402$ - всего 176 вариантов.

Рассмотрим случай, когда есть 3 простых делителя:
$3 \cdot 5 \cdot 7 = 105 < 227$
$3 \cdot 5 \cdot 11 = 165 < 402$
$3^2 \cdot 5 \cdot 11 = 495 > 402$
$5 \cdot 7 \cdot 11 = 395 < 402$

Проверим $m=3 \cdot 5 \cdot 7 = 105: \varphi (n) = 2 \codt 4 \cdot 6 = 48$, тогда $2m - \varphi (m) = $.

Если m - простое, то $2m - \varphi (m) = m+1 = 402 \Leftrightarrow m = 401$ - простое. Значит $n=802$ - корень.
Если $m = p^k, k \geq 2$, то $402 = 2m - \varphi (m)=p^{k-1}(2p-1)$ имеет максимальным делителем $p=67$, откуда получаем противоречие $2 \cdot 67 - 1 = 6$.
Таким образом, m имеет 2 либо 3 простых делителя.
m не может делится на куб простого числа.
Если m делится хотя бы на квадрат простого p, то р делит 402, причем р - нечетное. Значит $p=3$ или $p=67$.
Проверяем:
1. $p=3, m=9k, 2m- \varphi (m) = 18k - 6 \varphi (k) = 402, 3k - \varphi (k) = 67$. $k- \varphi (k) >0$, значит $2k<67, k \leq 33, k$ - нечетно и свободно от квадратов. Используем оценку $227 \leq m \leq 402$:
$227 \leq 9k \leq 402 \Leftrightarrow 25,2 \leq k \leq 44,5, 26 \leq k \leq 44$. Всего 9 нечетных вариантов (еще исключим с квадратами). Тупо проверим:
$k=27$ - с квадратом
$k=29 \Rightarrow 3 \cdot 29 - 28 = 55 \neq 67$,
$k=31 \Rightarrow 3 \cdot 31 - 30 = 63 \neq 67$,
$k=33 \Rightarrow 3 \cdot 33 - 20 = 73 \neq 67$,
$k=35 \Rightarrow 3 \cdot 35 - 24 = 81 \neq 67$,
$k=37 \Rightarrow 3 \cdot 37 - 36 = 75 \neq 67$,
$k=39 \Rightarrow 3 \cdot 39 - 24 = 93 \neq 67$,
$k=41 \Rightarrow 3 \cdot 41 - 40 = 83 \neq 67$,
$k=43 \Rightarrow 3 \cdot 43 - 42 = 87 \neq 67$.
Решений нет. (можно было рассмотреть случай k - простое)
2. $p=67, m=67^2k, 2m- \varphi (m) = 2 \cdot 67^2k - 67 \cdot 66 \varphi (k) = 402, 67k - 33 \varphi (k) = 3$.
$k- \varphi (k) >0$, значит $34k \leq 3$, откуда $k \in \empty$.
Остается рассмотреть случай, когда m свободно от квадратов. Он делится на 2 случая: m имеет 2 делителя и m имеет 3 различных делителя.
1. $m=pq, 2m- \varphi (m) = 2pq - (p-1)(q-1) = pq+p+q-1=402 \Leftrightarrow pq+p+q+1=404$.
$\Leftrightarrow (p+1)(q+1)=404=4 \cdot 101$, но $101-1=100$ - непростое. Решений нет.
2. $m=pqr$. Тут их проще все найти и проверить. Оценим наибольший простой делитель:
$402 \geq m=pqr \geq 3 \cdot 5r=15r \Rightarrow r \leq 26$, значит $p,q,r \in 3;5;7;11;13;17;19;23 $. Если отобрать произведения, которые меньше 403 и больше 228, то это будут 345;285;399 ($r=19;23$) и 255;231;273;357;385. Тут все понятно, а писать долго. Проверяем:
$m=345: 2m- \varphi (m)=690-96=596$
$m=285: 2m- \varphi (m)=570-136=434$
$m=399: 2m- \varphi (m)=798-240=558$
$m=255: 2m- \varphi (m)=510-128=382$
$m=231: 2m- \varphi (m)=462-120=342$
$m=273: 2m- \varphi (m)=546-144=402$ (ура, блин!)
$m=357: 2m- \varphi (m)=714-192=522$
$m=385: 2m- \varphi (m)=770-240=530$
Надо же! Еще одно решение нашли: $n=546 = 2 \cdot 3 \cdot 7 \cdot 13$.

Таким образом, 2 решения: 546 и 802.

З.Ы. Найдите ошибку

[bot]

Sonic86 писал(а):

З.Ы. Найдите ошибку

Я нашёл две.

Цитата:

$m=273: 2m- \varphi (m)=546-144=402$ (ура, блин!)

- а это и даёт n=546, которое Вы зачем то пропустили (?)

Цитата:

Таким образом, 2 решения: 456 и 802.

В первом числе надо переставить первые две цифры.

[Sonic86]

Пардон, исправляю.

[maxal]

Вот еще задачка на "оптимизацию перебора":
найти число $n$, для которого существуют взаимно простые числа $s,r$ такие, что $0<r<s<n<s^3$ и существует 7 различных делителей числа $n$, сравнимых с $r$ по модулю $s$.
(Ответ науке неизвестен)

[Руст]

Семь - уже слишком. Можно решать с 4-мя вместо семи и показать, что их конечное число. Дальше показать, что не существует для этих решений даже 5 делитей с указанными свойствами.

[maxal]

Руст писал(а):

Семь - уже слишком. Можно решать с 4-мя вместо семи и показать, что их конечное число. Дальше показать, что не существует для этих решений даже 5 делитей с указанными свойствами.

Здесь ты не прав.
Вот примерчик числа с 6 такими делителями: 245784 (для $s=65$, $r=1$ или $r=19$)
И вообще для шести делителей доказано, что таких чисел бесконечно много. А вот для семи делителей не известно даже ни одного примера.

[bot]

Sonic86 в сообщении #156128 писал(а):

Надо же! ...

А-а-а, до жирафа дошёл смысл сказанного. Это было типа просто удивления, а не признание пропуска. То-то я недоумевал, как можно было умудриться его пропустить, если оно было в рассмотрении?

В общем, неправильно я отвечал - на "надо же" правильно было отвечать "ну дык".

Впрочем сбивало и до сих пор сбивает продолжение

Цитата:

... Еще одно решение нашли: $n=546$

[Руст]

maxal писал(а):

Руст писал(а):

Семь - уже слишком. Можно решать с 4-мя вместо семи и показать, что их конечное число. Дальше показать, что не существует для этих решений даже 5 делитей с указанными свойствами.

Здесь ты не прав.
Вот примерчик числа с 6 такими делителями: 245784 (для $s=65$, $r=1$ или $r=19$)
И вообще для шести делителей доказано, что таких чисел бесконечно много. А вот для семи делителей не известно даже ни одного примера.

Если делители $d_i=k_is+r,0\le k_1<k_2<...$, то $(d_i,d_j)=(d_i,s(k_j-k_i))=(d_i,k_j-k_i)|k_j-k_i$.
Так как

$$n\ge lcm(d_1,d_2,...)\ge \prod_i\frac{d_i}{\prod_{j<i}(d_j,d_i)}.$$

На первый взгляд из этих соображений уже для 4 делителей получается конечное число решений с условием $n<s^3$.
$245784=19\mod 65$, поэтому достаточно проверить, что имеется по 3 делителя меньше $\sqrt n=495,...$ с остатком 1 и 19 при делении на 65 они $1,19,66, 84, 456$, что то не нашёл ещё одного делителя.

[maxal]

Делители числа 245784 сравнимые с 1 по модулю 65:
1, 66, 196, 456, 2926, 12936
Делители числа 245784 сравнимые с 19 по модулю 65:
19, 84, 539, 1254, 3724, 245784

А вообще A146544 - это как раз последовательность чисел, подобных 245784 (то есть с 6-ю делителями указанного вида).

[Sonic86]

bot! Прошу прощенья, я просто эту задачу давно решал, тоже очень скучно, и тогда нашел только одно решение. А вот когда сейчас решал - нашел второе.
А сообщение я писал пока не сюда - черновик писал на работе и писал не на форум, а пока писал сам себе. Потом, неожиданно, Вы все же решили, и я решил быстро ответ скинуть, и еще забыл, что там писал. Вот так и вышло. Короче говоря, не обращайте внимания. Я эту надпись сотру, чтоб недоумения не вызывала.

В принципе еще вопрос остался:
Уравнение $an+b \varphi (n) = A, a,b,A \in \mathbb{Z}$ имеет бесконечно много решений только при $a=1,b=-1,A=1$ или еще есть другие варианты?

maxal! А где-нибудь такие числа встречаются (в смысле зачем они?)?

[ИСН]

Sonic86 писал(а):

Уравнение $an+b \varphi (n) = A, a,b,A \in \mathbb{Z}$ имеет бесконечно много решений только при $a=1,b=-1,A=1$ или еще есть другие варианты?

Ну здрасте. Как простые числа Вам дают эту бесконечную серию, так числа вида $2p$ дадут другую ($b=-2$), и так далее...
Возможно, для любого $|a|<|b|$ будет то же самое.