Функция Эйлера.

[whitefox]

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

В принципе можно обойтись:

for(n=1;n!=100500a^2;++n){
  if(varphi(n)==a){
    AddSolution(n);
  }
}

Не, не, код не верный. Должно быть так:

Используется синтаксис C++

for(int n=1;n!=100500*a*a;++n){
  if(varphi(n)==a){
    AddSolution(n);
  }
}

[Батороев]

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

Т.е. если $p$ - максимальный простой делитель $a$, то $p|n$, и тогда $p-1|a$. Перебирая простые $b$ находим $b$ такое, то $b-1 \nmid a$, тогда $b\perp n$. Потом можно вычислить 2 таких $b$ и вычислить $\gcd$.

Я предлагал отталкиваться не от всевозможных простых, а только от тех простых и их функций Эйлера, которые присутствуют в вышеприведенной из Википедии формуле числа $a$ в качестве натуральных делителей или могли бы присутствовать, если бы не сократились.

[PWT]

venco в сообщении #1139102 писал(а):

$n$ должно быть делителем $2936=2^3\cdot 367$, ни один делитель не подходит.

Спасибо, но почему $n$ обязано быть делителем $2936$?

[Sonic86]

PWT в сообщении #1139197 писал(а):

Спасибо, но почему $n$ обязано быть делителем $2936$?

Вы теорему Эйлера о фи-функции знаете? погуглите. А потом то, что я писал в шутку - через $\gcd$.

В случае $a=122$ Вам проще заметить, то $61|122\Rightarrow 61|n\Rightarrow$ решений нет.

[venco]

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

В случае $a=122$ Вам проще заметить, то $61|122\Rightarrow 61|n\Rightarrow$ решений нет.

Это не всё. Надо ещё проверить что делитель 61 не может получиться из другого, т.е. ни один делитель 122 кратный 61 не является простым без единицы. В данном случае $122+1=123$ не является простым.

[Sonic86]

venco в сообщении #1139365 писал(а):

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

В случае $a=122$ Вам проще заметить, то $61|122\Rightarrow 61|n\Rightarrow$ решений нет.

Это не всё. Надо ещё проверить что делитель 61 не может получиться из другого, т.е. ни один делитель 122 кратный 61 не является простым без единицы. В данном случае $122+1=123$ не является простым.

Да, спасибо. Значит не все так просто.

[PWT]

Спасибо, кажется начал что-то понимать, вспомнив теорему Эйлера.

Попробую решить $\varphi(n)=98$.

$\operatorname{gcd}(3;98)=\operatorname{gcd}(5;98)=1$

$\operatorname{gcd}(3^{98}-1;5^{98}-1)=8$

Так как $8$ не делится на $98$, значит таких $n$ нет... Верно?

Из таблицы википедии возьму тогда $60$.

Попробую решить $\varphi(n)=60$.

$\operatorname{gcd}(7;60)=\operatorname{gcd}(11;60)=1$

$\operatorname{gcd}(7^{60}-1;11^{60}-1)=1681477200$

Так как $1681477200$ делится на $60$, тут не нашли противоречия.

Значит нужно искать такие $n$. Только перебором тогда?

(Оффтоп)

Знаю из википедии, что должны подойти, как минимум $n=99$, $n=61$

[Батороев]

(Оффтоп)

PWT в сообщении #1139410 писал(а):

Знаю из википедии, что должны подойти, как минимум $n=99$, $n=61$

А также $77, 124$ и все удвоенные нечетные.

[whitefox]

Уравнение $\varphi(n)=a$ может иметь следующие решения:

• если $a=1,$ то 1 — решение;
• если число $(a+1)$ простое, то $(a+1)$ — решение;
• пусть $p$ наибольший простой делитель числа $a,$ тогда если $a=p^m(p-1)$ для некоторого $m,$ то $p^{m+1}$ — решение;
• пусть $(a_1,a_2)$ пара чётных чисел таких, что $a=a_1\cdot a_2$ и пусть $n_1$ решение уравнения $\varphi(n_1)=a_1,$ а $n_2$ пусть решение уравнения $\varphi(n_2)=a_2$ взаимно простое с $n_1$ (то есть $\gcd(n_1,n_2)=1$), тогда $n_1\cdot n_2$ — решение исходного уравнения;
• если $n$ есть нечётное решение, то $2n$ — решение.

Других решений уравнение $\varphi(n)=a$ не имеет.

Пример 1. Решить $\varphi(n)=122.$

• Так как число $122+1=123$ не простое, то оно — не решение.
• Так как $61$ есть наибольший простой делитель числа $122$, но $61\cdot60\ne122,$ то $61\cdot60=3660$ — не решение.
• Так как число $122$ не возможно представить в виде произведения пары чётных чисел, то уравнение решений не имеет.

Пример 2. Решить $\varphi(n)=4.$

• Так как число $4+1=5$ простое, то оно решение.
• Так как число $2$ есть наибольший простой делитель $4$ и $4=2^2(2-1),$ то $2^3=8$ — решение.
• Так как $4=2\cdot2$ и $\{3,4,6\}$ суть решения $\varphi(n)=2,$ то $3\cdot4=12$ — решение.
• Так как $5$ есть нечётное решение, то $2\cdot5=10$ — решение.

[whitefox]

Пример 3. Решить $\varphi(n)=60.$

• Так как $60+1=61$ простое, то $61$ — решение.
• Так как $5$ есть наибольший простой делитель числа $60,$ но $60\ne5^m(5-1)$ ни для какого $m,$ то решения вида $5^{m+1}$ нет.
• Так как $60=2\cdot30=6\cdot10,$ то потребуются решения уравнений:
  
  • $\varphi(n)=2$
  • $\varphi(n)=6;$
  • $\varphi(n)=10;$
  • $\varphi(n)=30.$
  Применяя этот алгоритм рекурсивно, найдём:
  
  • $\varphi^{-1}(2)=\{3,4,6\};$
  • $\varphi^{-1}(6)=\{7,9,14,18\};$
  • $\varphi^{-1}(10)=\{11,22\};$
  • $\varphi^{-1}(30)=\{31,62\}.$
  Из чего заключаем, что решениями являются также $3\cdot31=93,$ $3\cdot62=186,$ $4\cdot31=124,$ $6\cdot31=186,$ $7\cdot11=77,$ $7\cdot22=154,$ $9\cdot11=99,$ $9\cdot22=198,$ $14\cdot11=154,$ $18\cdot11=198.$
• Так как $\{61,77,93,99\}$ суть нечётные решения, то $\{122,154,186,198\}$ тоже решения.

Объединив все эти решения, получим $\varphi^{-1}(60)=\{61,77,93,99,122,124,154,186,198\}.$

[PWT]

whitefox в сообщении #1139449 писал(а):

Уравнение $\varphi(n)=a$ может иметь следующие решения:

• если число $(a+1)$ простое, то $(a+1)$ — решение;
• пусть $p$ наибольший простой делитель числа $a,$ тогда если $a=p^m(p-1)$ для некоторого $m,$ то $p^{m+1}$ — решение;
• пусть $(a_1,a_2)$ пара чётных чисел таких, что $a=a_1\cdot a_2$ и пусть $n_1$ решение уравнения $\varphi(n_1)=a_1,$ а $n_2$ пусть решение уравнения $\varphi(n_2)=a_2$ взаимно простое с $n_1$ (то есть ), тогда $n_1\cdot n_2$ — решение исходного уравнения;
• если $n$ есть нечётное решение, то $2n$ — решение

Других решений уравнение $\varphi(n)=a$ не имеет.

Спасибо, попробую прогнать несколько уравнений по вашему алгоритму!

Пример 4. Решить $\varphi(n)=12$

• Так как число $12+1=13$ простое, то оно решение.
• Так как число $3$ есть наибольший простой делитель $12$ и $12=3^m(3-1),$ не выполняется ни для какого целого $m$. Или $m$ в виде логарифма подойдет?)
• Так как $12=6\cdot2$ и $\varphi(3)=2$ и $\varphi(7)=6$ и $\gcd(3,7)=1$, то $7\cdot 3=21$ — решение исходного уравнения.
• Так как $13,21$ есть нечётные решения, то $26,42$ — решения

Ответ: $\{13,21,26,42\}$. Правильно?

Пример 5. Решить $\varphi(n)=342$

• Так как число $342+1=343$ составное, то этот пункт пропускаем.
• Так как число $19$ есть наибольший простой делитель $342$ и $342=19^1(19-1),$, то $19^2=361$ -- решение.
• Так как $a$ не делится на $4$, пропускаем представимость в виде произведения двух четных чисел.
• Так как $361$ есть нечётное решение, то $722$ — решение

Ответ: $\{361,722\}$. Правильно?

Вроде бы понял как прогонять по алгоритму, другое дело, что не очень понял -- из каких соображений он следует, об этом где-то написано или вы его вывели самостоятельно?)

[venco]

PWT в сообщении #1139583 писал(а):

$\varphi(3)=2$

А ещё $\varphi(4)=2$.

Проверить онлайн можно здесь:
http://www.wolframalpha.com/input/?i=solve+eulerphi(n)%3D12

[whitefox]

PWT в сообщении #1139583 писал(а):

Или $m$ в виде логарифма подойдет?)

Только положительное целое.

PWT в сообщении #1139583 писал(а):

Так как $12=6\cdot2$ и $\varphi(3)=2$ и $\varphi(7)=6$ и $\gcd(3,7)=1$, то $7\cdot 3=21$ — решение исходного уравнения.

На этом шаге алгоритм нужно применить рекурсивно к решению уравнений $\varphi(n)=2$ и $\varphi(n)=6.$ Для которых получим $\varphi^{-1}(2)=\{3,4,6\}$ и $\varphi^{-1}(6)=\{7,9,14,18\}$ соответственно.

Так как $3\bot7,$ $3\bot14,$ $4\bot7,$ $4\bot9,$ $6\bot7$ (здесь $\bot$ значит "взаимнопросто"), то решениями будут $3\cdot7=21,$ $3\cdot14=42,$ $4\cdot7=28,$ $4\cdot9=36,$ $6\cdot7=42.$

PWT в сообщении #1139583 писал(а):

Ответ: $\{13,21,26,42\}$. Правильно?

Пропущено $\{28,36\}.$

PWT в сообщении #1139583 писал(а):

Вроде бы понял как прогонять по алгоритму, другое дело, что не очень понял -- из каких соображений он следует, об этом где-то написано или вы его вывели самостоятельно?)

Наверняка где-нибудь написано. А следует он из того, что:

• $\varphi(a)\cdot\varphi(b)=\varphi(a\cdot b)$ для $a\bot b;$
• $\varphi(p^m)=p^{m-1}(p-1)$ для $p$ простого.

[PWT]

Спасибо большое, разобрался!

[Sonic86]

Вручную еще можно считать вот так:
$\varphi(x)=\prod\limits_{k=1}^n p^{a_p-1}(p-1)=n$, тогда $p-1|n$. Можно вычислить все делители $d|n$ и проверить на простоту $d+1$ - получим список простых $L$. Тогда решение имеет вид: $x=\prod\limits_{p\in L}p^{a_p}$. Можно перебирать $p$ в порядке убывания. Для поиска показателей удобно использовать такую лемму: если $p-1|n$, то $a_p\leqslant 1+v_p(n)$. Можно также проверять простые соотношения $s\leqslant v_2(n)$ ($s$ - число различных простых делителей $n$). Но в итоге перебор все равно получается рекурсивным: как только рассматриваем случай $a_p>0$, так сразу делаем подстановку $x=xp^{a_p}$ и в итоге надо снова решать уравнение $\varphi(x)=n_1<n$.
Хотелось бы увидеть оценки скоростей разнообразных алгоритмов. С другой стороны, в умной статье, на которую я привел ссылку, написано, что список всех прообразов имеет экспоненциальную мощность в худшем случае (в среднем - полиномиальную), так что скорость работы поиска всех прообразов экспоненциальная в худшем случае по-любому.