С6. Составное число.

Натуральное число представимо в виде произведения различных простых множителей. Сумма всех его делителей равна 384. Количество чисел, меньших данного числа и взаимно простых с ним равно 120. Найти это число.

Сумма делителей произведения двух взаимно простых чисел есть произведение сумм делителей каждого, поскольку
[m]\sum\limits_{d_1|m} \sum\limits_{d_2|n} d_1\cdot d_2 = \sum\limits_{d_1|m} d_1 \cdot \sum\limits_{d_2|n} d_2[/m].
Для простого p она, очевидно, равна p+1. Значит для нашего числа она есть [m](p_1+1)...(p_k+1)=384[/m].
Функция Эйлера (то самое количество чисел, меньших данного и взаимно простых с ним) от произведения двух взаимно простых чисел также является произведением функций эйлера для каждой. Действительно, число не взаимно простых с mn чисел есть
[m](m-\phi(m))n+(n-\phi(n))m — (n-\phi(n))(m-\phi(m)) = mn — \phi(m)\phi(n),[/m] откуда и следуется наша формула
Значит она для нашего числа равна
[m](p_1-1)...(p_k-1)=120[/m]
[m]384 = 2^7\cdot 3,\ 120=2^3\cdot 3\cdot 5[/m].
Предположим, что среди [m]p_i[/m] есть число 2 (для определенности это первое из наших p). Тогда [m](p_1+1)/(p_1-1)=3[/m], откуда произведение остальных [m](1+p_i)/(p_i-1) = 1+ 2/(p_i-1)[/m] есть 16/15, откуда минимальное из них не меньше 31. Но два делителя свыше 30 быть не могут, так как их произведение будет больше 900. Значит если наше число четно, то оно может быть равно только 62. При этом 62, очевидно, не подходит.
Значит число нечетно. Значит все [m]p_i-1[/m] четны, откуда их число k не может быть больше 3. Предположим, что k=3. Тогда множителям никуда не остается, как быть равным 2, 6 и 10. Значит наше число есть [m]3\cdot 7 \cdot 11= 231,[/m] что нам, очевидно подходит. Пусть k=2. Тогда складывая наши два соотношения имеем [m]p_1\cdot p_2 = (120+384)/2-1 = 251[/m]. Это число простое, что противоречит предположению. Остается вариант k=1, который разбивается о то, что [m]384-120 \neq 2[/m]
Значит единственный вариант — 231.

По-моему, тут недолго решить, что вы, как один не безызвестный форумный персонаж, выкладываете задачи из под одного аккаунта и решаете их из под другого :)
А я, соответственно, ваш бот :)

Нет, это точно не он. (Где нападки на Мехмат и педвузы?!) :-]

:-D
Чтобы убедиться в ложности подобных мыслей достаточна отправить заявки на занятия со мной и Вами и воочию удостовериться. :-)

Решение, конечно, замечательное, но для школьников, незнакомых с функцией Эйлера, сложно. Тут без нее можно прийти к необходимым уравнениям, используя лишь логические соображения (ну для Вас это и так понятно). Только не торопитесь их демонстрировать, может быть, кому-то будет интересно поразмышлять.
И, конечно, спасибо за Ваше неизменное участие и молниеносность. :-)

Вывести функцию Эйлера либо ее частный, интересующий нас, случай, разумеется, можно — есть куча способов, не требующих никаких спец. знаний и навыков.

Вот только если кто-то из школьников знает про функцию Эйлера — он имеет большую фору против того, кто ее не знает. В этом смысле задача не очень хорошая — создает преференции не по уму/сообразительности, а по "натасканности".

Эта задача- некая разновидность олимпиадных задач ИКСИ. Эта задача может быть сведена к следующей алгебраической задаче. При каком значении параметра n уравнение имеет три натуральных корня.
[m]{{x}^{3}}-(252-n){{x}^{2}}+131x-n=0[/m]

Если мы будем исходить из того, что простых делителя именно 3, то такое уравнение получить действительно несложно, если [m]p_1+p_2+p_3 = a[/m], [m]p_1p_2+p_1 p_3 + p_2 p_3 = b[/m], [m]p_1 p_2 p_3 = n[/m], то данные нам соотношения превратятся в
[m]n+a+b+1= 384,\ n-a+b-1=120,[/m]
откуда и из теоремы Виета будет следовать ваше утверждение.
Только надо еще показать, что простых делителя именно 3. И решить уравнение. Я как-то с ходу не скажу, как его просто решить.

Без перебора не обойтись. Предполагаем, что меньший корень сначала 2, решения нет(функция Эйлера n=246 не равна 120). Полагаем корень 3, получаем n=231 проверяем, все.

А ведь задачу можно решить без знания суммы делителей.
Очевидно, что n может быть произведением не менее трех делителей. Пусть [m]n={{p}_{1}}\cdot {{p}_{2}}\cdot {{p}_{3}}[/m].
Тогда [m]\varphi (n)=({{p}_{1}}-1)\cdot ({{p}_{2}}-1)\cdot ({{p}_{3}}-1)=120[/m], при этом все скобки чётные. Делим обе части на 8, получаем [m]{{q}_{1}}\cdot {{q}_{2}}\cdot {{q}_{3}}=15=1\cdot 3\cdot 5[/m], где [m]{{q}_{i}}=\frac{{{p}_{i}}-1}{2}[/m]. Отсюда получаем [m]{{p}_{1}}=3,{{p}_{2}}=7,{{p}_{3}}=11,n=231.[/m]

Так сумму делителей проще получить, чем функцию Эйлера.

Быть может, покажете , как решить?

Интересно было бы посмотреть результат.

А вообще, чего мелочиться-решать школьные задачки nакому мощному математическому сообществу.
Предлагаю взяться за вскрытие криптосистемы RSA.

1. Зачем? Если RSA хочет вскрыть серьезная спецслужба — она сделает это через бэк-доры в ПО, которые туда заложены, так как все официальные крипто-программы выпускаются на рынок только с согласования органов. Переписка тех, кто считает себя самым умным и добыл (или самостоятельно написал) левый кодировщик также вскрывается без проблем — достаточно посетить квартиру умника, пока его нет дома, и немного поработать.

Вариант с самыми умными также работает и в исполнении менее серьезных людей.

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

2. Нравятся Вам эти три буквы RSA — так попробуйте создать эффективный алгоритм разложения на множители, дискретного логарифмирования, тестов на простоту и.т.д. — в случае успеха клиенты на пользование результатами работы ваших алгоритмов встанут в очередь и будут неплохо платить. Можете простое число в 100 миллионов знаков найти — за него тоже заплатят (просто как за рекорд, вряд ли его можно использовать для каких-то практических или общенаучных целей).

С практической точки зрения, Вы конечно правы. Но есть еще математико -криптоаналитический интерес.
Кроме того, я использую RSA, в частности, для обучения сильных учеников( кто хочет на информационную безопасность поступать) теории чисел. Их так легче заинтересовать.
У меня есть определенная идея по RSA. Могу представить для критического обсуждения, если есть желание.

Если хотите — попытайтесь вычислить мое инкогнито и прислать мне в личку свои идеи или сообщение о том, что Вы меня вычислили — тогда и поговорим.

Энное количество софорумников уверено, что знает, кто такой Anonimus Vulgaris.

Я могу получать открытый текст без алгоритмов разложения на множители, дискретного логарифмирования, тестов на простоту и.т.д. А к кому за деньгами обращаться?

Во-первых, я не понял, что Вы можете.
Во-вторых, не ко мне.
В-третьих, Вы пока даже не смогли мне письма написать :)

Здравствуйте,Я являюсь магистрантом, моей задачей является спрогнозировать цены (цены на товары и услуги) , которые являются нестационарными величинами с помощью метода разложения Карунена-Лоэва. Очень много литературы, но что касается прямого прогнозирования ничего нет(( Может кто нибудь сможет мне объяснить алгоритм данного метода , может быть кто-то встречался с ним ранее? заранее благодарю)

Что можно сказать о двух множителях,если их произведение:
1)положительно;2)отрицательно;3)ровно нулю;4)равно одному из множителей?

Доказать, что последовательность
[m]{2}^{n} — 3[/m] , [m]n = 2, 3, 4, ...[/m]
содержит бесконечное множество чисел. каждые два из которых взаимно просты.

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

Число 201071131 является произведением двух простых чисел p и q , а количество натуральных чисел, меньших заданного числа и взаимно простых с ним, равно 201041064. Найти p,q/