Уравнение с функцией Эйлера

Дано уравнение [m]\varphi (m)=a[/m], a-заданное число. Надо найти m. В каком случае решение будет единственным. В задании конкретное уравнение [m]\varphi (m)=462000[/m].

m=125*49*121. Легко получается из мультипликативности фунции Эйлера.

Вопрос про единственность — сложнее. Например, если p — число Ферма, то есть простое вида p=1+2^k, то уравнение фи(m)=p-1 имеет два решения. До сих пор неизвестно, конечно ли множество чисел Ферма.

Да, кстати, 125*49*121 — не единственное решение.
625*49*23 — тоже решение.

Может есть и еще решения...

121*61*71 — тоже решение.

А если верить Вольфраму — решений и вовсе 316 штук.

http://oeis.org/A007366 A007366 phi(x) = n has exactly 2 solutions.
http://mathworld.wolfram.com/TotientValenceFunction.html

Есть ли такие a, что phi(a)=1 — открытая математическая проблема.

Сорри, очевидная опечатка. Крайнее предложение №6 следует читать как:

"Есть ли такие a, что уравнение phi(x)=a имеет единственное решение — открытая математическая проблема."

Я разложил число a на простые множители:
a = 462000 = 2*231*1000 = 2*3*77*(2^3)*(5^3) = (2^4)*3*(5^3)*7*11.
Далее переписал это таким образом (методом созерцания):
a = ((5^2)*4) * (7*6) * (11*10) =
= ((5^2)*(5-1)) * (7*(7-1)) * (11*(11-1)),
из чего сделал вывод, что в качестве m годится, например, число
m = (5^3)*(7^2)*(11^2) = 125*49*121 = 741125.
Больше пока ничего не придумал.

Я не первый раз обращаюсь к Вам за помощью. Весной я обращался потому, что занимался системой RSA. У нас в гимназии это спецкурс, хочу потом поступать на такую специальность. Мне надо подробно научиться решать такие задачи,чтобы засчитали мое решение. А Вы решали мою задачу и дали ответ, не понял полный или нет. Но мне нужно показать , как я решал. Сам я пока не пока не знаю как.

Смотри №5 и №6-№7.

300 решений исключают ручное решение данной задачи за разумное время.
Вопрос о том, когда решение единственно — открытая математическая проблема — тоже не уровень спецкурса в гимназии.

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

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

Шаг 1 алгоритма — в разложении ответа на множители могут присутствовать только простые 2,3,5,7,11 и такие простые p, что p-1 — делитель 462000. Этих простых конечное число и они находятся перебором (не по простым, а по делителям 462000, которых всего то 160).

Шаг 2 — в разложении ответа все простые входят в первой степени, исключение только для 2,3,5,7,11 — они могут входить в более высоких степенях (но не более, чем 5,2,4,2,2).

Шаг 3 — много делителей быть не может — фи быстро станет больше 462000. Делителей, отличных от 2,3,5,7,11 вообще не больше четырех (в разложении числа — кандидата на решение). Если проделать шаг 1 — возможно окажется, что их не больше двух.

Реализуйте разумный перебор на шагах 2 и 3, вычисляя фи для каждого перебираемого числа — и Вы получите все решения.

Начинаем с формулы для расчета функции Эйлера для числа вида
[m]m={{p}^{{{l}_{1}}}}_{1}\cdot {{p}_{2}}^{{{l}_{2}}}...\cdot {{p}_{k}}^{{{l}_{k}}}[/m]. Она имеет вид: [m]\varphi (m)=({{p}_{1}}^{{{l}_{1}}}-{{p}_{1}}^{{{l}_{1}}-1})({{p}_{2}}^{{{l}_{2}}}-{{p}_{2}}^{{{l}_{2}}-1})...({{p}_{k}}^{{{l}_{k}}}-{{p}_{k}}^{{{l}_{k}}-1})[/m].
Число 462000=100*42*110=(5^3-5^2)*(7^2-7)(11^2-11)[m]\varphi ({{5}^{3}}\cdot {{7}^{2}}\cdot {{11}^{2}})=\varphi (741125)[/m]

Ну, этот, наиболее очевидный ответ, уже получили три раза в данной ветке :)

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

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

И чем это принципиально лучше ответа от г-на Боравлева? :)

Не говоря уже о том, что если человек собирается что-то делать с функцией Эйлера — он должен знать ее основные свойства и понимать, откуда они берутся.

И, уж точно, но знает, как посчитать функцию Эйлера по разложению на простые.

Вообще мне в гимназии нужно было найти хотя бы одно решение. Остальное я уже сам придумал-насчет единственности. А вообще думаю как факторизовать модуль в системе RSA/

Не понимаю — то ли Вы всех разводите стеба ради, то ли всерьез.

Если всерьез — то предъявите хоть одно a, для которого уравнение имеет единственное решение — проверить Вашу правоту — дело нескольких минут.

Спасибо всем за помощь. Познакомился сWolfram, очень понравилась. Но вот еще вопрос. А можно ли как-то найти функцию Эйлера для модуля системы RSA без предварительной факторизации модуля. Хотя наверное вопрос не очень.

Если кто-то в мире и знает ответ на этот вопрос — он молчит. А пока он молчит, криптографы верят в то, что найти функцию Эйлера без факторизации нельзя.

Вы сейчас мешаете разным личностям господина Кругликова вести беседу друг с другом. Зачем нарушать гармонию его внутренних "я"? :)
Он же не для вас задал себе этот вопрос, а для себя.

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

Личность у меня одна — раздвоением не страдаю.
А вот подписей — две. И все, кому надо, это знают.

А если какие господа сами с собой из-под разных ников разговаривают — почему бы их не забанить?

Была бы моя воля, банил бы. :-)

Ну, если у Вас нет полномочий — так есть знакомые с полномочиями.

Сделайте доброе дело — передайте им пожелание шир. нар. масс.

Пусть так. Так попытайтесь ответить, да и все. Вспомните задачу , поставленную
Г. Вулем в теме С6. Составное число. Вы со всей мехматовской мощью ее решили, но как. Задача же решалась в одну строчку и даже без одного исходного данного. В этом вся Ваша квалификация.

Не могу понять как решить эту задачу. Понимаю прекрасно что элементов всего будет 4, так как воспользовавшись формулой Эйлера от числа 8 получим 4. А вот дальше затуп и застрял. Для Z48 образующих элементов 16 штук. А дальше что?

Сегодня разбирали на занятии с учеником. Им её в школе на дом задали.

4-угольник ABCD вписан в окружность и описан около окружности. Вписанная окружность касается сторон 4-угольника в точках К,L,M,N. Отношение площадей 4-угольников KLMN и ABCD равно k. Угол между диагоналями AC и BD равен [m]\varphi[/m]. Радиус описанной окружности равен R. Найти площадь 4-угольника ABCD.

http://s09.radikal.ru/i182/1205/f6/5959a551ce02.jpg

3997

Подойдет замена [m]t=xy[/m] или есть удобнее?

4007

Правильно ли я понимаю, что нужно взять [m]\int_0^1dx\int_{0}^{1-x}dy\int_{xy}^{1-x-y}[/m] ?

4012

Правильно ли я понимаю, что нужно взять тот же интеграл [m]\int_0^1dx\int_{0}^{1-x}dy\int_{xy}^{1-x-y}[/m] ?

4013

[m]x=r\cos\varphi[/m]

[m]y=r\sin\varphi[/m]

[m]z=\pm\sqrt{0,5r^2\sin2\varphi}[/m]

Так что нужно вот такой интеграл брать? [m]\int_{0}^{2\pi}d\varphi\int_0^ardr\int_{-0,5r^2\sin2\varphi}^{+0,5r^2\sin2\varphi}dz[/m]

дана задача : на какое максимальное число честей может разбить плоскость 2010 прямых? мне сказали что нужно решать используя характеристику эйлера... я прочитала... и ничего не поняла... объясните пожалуйста!!