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

[PWT]

Как решаются уравнения вида $\varphi(n)=a$, где $a$ -- известное (например, трехзначное число)?
Где можно почитать об этом?

[vorvalm]

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

Где можно почитать об этом?

Учебник по теории чисел. Рекомендую А.Бухштаб.

[Sonic86]

Решать можно перебором - перебирая канонические разложения - долго и муторно (в PARI/GP есть функция invphi, видимо не зря)
Можно вычислить $2^a-1$ и разложить на множители

Нагуглил:
http://arxiv.org/abs/math/0404116
https://hal.inria.fr/file/index/docid/7 ... me/TOT.pdf
http://mathoverflow.net/questions/10950 ... t-function
http://math.stackexchange.com/questions ... t-function
http://www.numbertheory.org/php/carmichael.html

http://arxiv.org/pdf/1401.6054v3.pdf
Вот еще статья maxal-а, а invphi - это его в PARI/GP

[PWT]

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

Решать можно перебором - перебирая канонические разложения - долго и муторно (в PARI/GP есть функция invphi, видимо не зря)
Можно вычислить $2^a-1$ и разложить на множители

Нагуглил:
https://hal.inria.fr/file/index/docid/7 ... me/TOT.pdf
http://mathoverflow.net/questions/10950 ... t-function
http://math.stackexchange.com/questions ... t-function

Спасибо! Пока что не ясно -- зачем раскладывать $2^a-1$ на множители, но я попробую.

Пусть $\varphi(n)=122$.

$2^{122}-1=3\cdot 768614336404564651\cdot 2305843009213693951$ (допустим, что мы угадали разложение на простые множители). Но как это поможет?

[Sonic86]

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

Пока что не ясно -- зачем раскладывать $2^a-1$ на множители, но я попробую.

Это шутка была Просто $n$ делит $b^{\varphi(n)}-1$ для любого $b$.
Впрочем, можно было бы вычислить $d=\gcd(2^a-1,3^a-1)$ и тогда $n|d$, а $d$-то мало, так что м.б. это даже и не шутка...
(хотя нет - даже здесь где-то косяк в рассуждении, потому что $\gcd(2^4-1,3^4-1)=5$, в то время как $\varphi(5)=\varphi(8)=\varphi(6)=4$. Наверное потому, что $b$ в общем случае не первообразное даже. Просто это все было бы легче кодить)

[PWT]

Хах) То есть это все сводится к жесткому перебору вариантов или же громоздкому разложению на множители некоторых сложных функций от функции Эйлера?

[Sonic86]

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

[PWT]

Хорошо, спасибо. Оказывается, что для каждого $a$ может быть достаточно много $n$. Там даже приближенная оценка есть.

[venco]

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

Просто $n$ делит $b^{\varphi(n)}-1$ для любого $b$.

Для взаимнопростых $n$ и $b$. Т.е. случай с общими множителями надо обрабатывать дополнительно.

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

Впрочем, можно было бы вычислить $d=\gcd(2^a-1,3^a-1)$ и тогда $n|d$, а $d$-то мало, так что м.б. это даже и не шутка...
(хотя нет - даже здесь где-то косяк в рассуждении, потому что $\gcd(2^4-1,3^4-1)=5$, в то время как $\varphi(5)=\varphi(8)=\varphi(6)=4$.

$\varphi(6)=2$, а $8$ имеет общие множители с $a=4$.
Так что этот метод, наверное, можно доработать.

-- Ср июл 20, 2016 17:48:03 --

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

Пусть $\varphi(n)=122$.

$gcd(3,122)=gcd(5,122)=1$
$gcd(3^{122}-1,5^{122}-1)=2936=2^3\cdot 367$
решений нет.

-- Ср июл 20, 2016 17:58:13 --

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

$gcd(3^{122}-1,5^{122}-1)=2936=2^3\cdot 367$

Вот только как это вычислить для достаточно больших $a$ - не представляю. А для маленьких проще разложение $a$ использовать.

-- Ср июл 20, 2016 17:59:57 --

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

-- Ср июл 20, 2016 17:58:13 --

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

$gcd(3^{122}-1,5^{122}-1)=2936=2^3\cdot 367$

Получилась рекурсивная цитата.

[PWT]

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

$gcd(3,122)=gcd(5,122)=1$
$gcd(3^{122}-1,5^{122}-1)=2936=2^3\cdot 367$
решений нет.

Спасибо, но как из этого следует, что решений нет, вот что не пойму...

[venco]

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

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

$gcd(3,122)=gcd(5,122)=1$
$gcd(3^{122}-1,5^{122}-1)=2936=2^3\cdot 367$
решений нет.

Спасибо, но как из этого следует, что решений нет, вот что не пойму...

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

[Батороев]

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

Как решаются уравнения вида $\varphi(n)=a$, где $a$ -- известное (например, трехзначное число)?

По-видимому, можно попытаться использовать формулу для вычисления функции Эйлера:

Цитата:

Функция Эйлера от натурального числа[править | править вики-текст]
Для произвольного натурального числа значение ${\displaystyle \varphi (n)}$представляется в виде[7]:
${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),\;\;n>1,}$

Например, решая для $a=122=2\cdot 61$, видно, что $\varphi(p_i)\ne 61$ (нечетное число), следовательно, $61$ может быть только делителем числа $n$. Но для простого $61$ в сомножителях числа $a$ нет его функции Эйлера $\varphi (61)=61-1=60$. Из чего следует, что при указанном значении $a$ чисел $n$ не существует.

[whitefox]

Функция Эйлера — мультипликативная. Поэтому для решения уравнения $\varphi(n)=a,$ при неизвестном $n,$ можно использовать следующую рекурсивную процедуру:

1. для каждого $ d\mid a$ найти решения уравнений $\varphi(n_1)=d$ и $\varphi(n_2)=a/d;$
2. для каждой пары взаимнопростых $n_1$ и $n_2$ число $n_1\cdot n_2$ будет решением исходного уравнения.

Имхо, без факторизации $a$ не обойтись.

[Батороев]

Рассматривавшийся здесь случай $a=4=2\cdot 2$ можно проанализировать следующим образом:
Рассмотриваем все множители числа $a$ в качестве функции Эйлера простых делителей числа $n$:
1. $\varphi (2)=1$. Тогда $2^2$ является степенью двойки, сокращенной на единицу, т.е $n=2^3$.
2. $\varphi (3)=2$. В этом случае число $n$ должно содержать простой множитель $3$ в первой степени (т.к. любая более высокая степень всегда бы оставила "след" в числителе числа $a$). Оставшийся у числа $a$ делитель $2$ рассматриваем, как сокращенную степень числа $2^2$ и получаем число $n=3\cdot 2^2=12$.
3. $\varphi (5)=4$. В этом случае можно рассматривать $n=5$, а также $n=10$, т.к. первые степени двойки в указанной выше формуле сократятся.

[Sonic86]

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

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

Просто $n$ делит $b^{\varphi(n)}-1$ для любого $b$.

Для взаимнопростых $n$ и $b$. Т.е. случай с общими множителями надо обрабатывать дополнительно.

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

Впрочем, можно было бы вычислить $d=\gcd(2^a-1,3^a-1)$ и тогда $n|d$, а $d$-то мало, так что м.б. это даже и не шутка...
(хотя нет - даже здесь где-то косяк в рассуждении, потому что $\gcd(2^4-1,3^4-1)=5$, в то время как $\varphi(5)=\varphi(8)=\varphi(6)=4$.

$\varphi(6)=2$, а $8$ имеет общие множители с $a=4$.
Так что этот метод, наверное, можно доработать.

Можно исключить случай не взаимно простых $b$, если использовать это:

Батороев в сообщении #1139120 писал(а):

Например, решая для $a=122=2\cdot 61$, видно, что $\varphi(p_i)\ne 61$ (нечетное число), следовательно, $61$ может быть только делителем числа $n$. Но для простого $61$ в сомножителях числа $a$ нет его функции Эйлера $\varphi (61)=61-1=60$. Из чего следует, что при указанном значении $a$ чисел $n$ не существует.

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

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

Имхо, без факторизации $a$ не обойтись.

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

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