22:56 

Теория чисел. Функция Эйлера.

IWannaBeTheVeryBest
`\phi(x) = 2`
В учебнике дано решение, но я его не могу понять никак. Просто на первой фразе встал.
"`x` обладает каноническим разложением. `x = p_1^{a_1} * \dots * p_k^{a_k}`. При этом `\phi(x) = p_1^{a_1 - 1} * \dots * p_k^{a_k - 1} * (p_1 - 1) * \dots * (p_k - 1)`
Пусть `\phi(x) = 2^m*l`, где `l` - нечетное. Поскольку для нечетного простого числа `p` величина `p - 1` четна, то в каноническом разложении `x` имеется не более `m` нечетных простых множителей." (дальше попробую сам понять)
Не понимаю причинно следственную связь. Как из одного вытекает другое. Все, что удалось мне выжать
`2^m * l` четное число.
`2^m * l = p_1^{a_1 - 1} * \dots * p_k^{a_k - 1} * (p_1 - 1) * \dots * (p_k - 1)`
Ну и понятно, что в последнем равенстве, справа не все множители нечетные.

@темы: Теория чисел

Комментарии
2017-05-10 в 23:23 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
IWannaBeTheVeryBest, что в последнем равенстве, справа не все множители нечетные.
чего ради?... если `p` - простое, то `(p - 1)` - чётное...

2017-05-10 в 23:24 

Trotil
Не понял, phi(x) = 2 - это уравнение и его надо решить?

2017-05-10 в 23:44 

IWannaBeTheVeryBest
Trotil, Да.
All_ex, Про простое и четное я понял. А как из этого следует то, что каноническое разложение икса должно содержать не более `m` нечетных множителей.
К тому же если в равенстве `2^m * l = \dots` справа будут все нечетные множители, то ведь и число должно нечетное получиться, ведь так? Ну как там. Произведение двух нечетных чисел - нечетное число.
`(2k + 1) * (2n + 1) = 4kn + 2k + 2n + 1 = 2(2kn + k + n) + 1 sim 2k + 1`
Далее по индукции - произведение нечетных чисел - нечетное число

2017-05-10 в 23:51 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
А как из этого следует то, что каноническое разложение икса должно содержать не более `m` нечетных множителей
Ну, Вы писали, что При этом `\phi(x) = p_1^{a_1 - 1} * \dots * p_k^{a_k - 1} * (p_1 - 1) * \dots * (p_k - 1)`... двойки можно вынести из каждого множителя произведения `(p_1 - 1)*...*(p_k - 1)`... то есть `k \le m`...

2017-05-10 в 23:58 

IWannaBeTheVeryBest
All_ex, Ага. А если `k < m`, то `p_1` неизбежно = 2, я верно понимаю? Просто количество скобок будет меньше `m` а нам нужны еще двойки.

2017-05-11 в 00:34 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
то `p_1` неизбежно = 2 - чего вдруг?... Если `p = 17`, то `p - 1 = 16`, то есть `2^4`...

2017-05-11 в 10:40 

IWannaBeTheVeryBest
All_ex, Так хорошо. Можно такой вопрос, возможно глупый, но хотелось бы все же понять. Количество множителей в каноническом разложении равно `k`?
Или `sum_{i = 1}^{k} a_i`? То есть если какое-то простое число в каноническом разложении имеет степень, скажем, 3, то это 1 множитель, или 3 множителя? Вот мне кажется, что 3 и количество множителей определяется суммой всех степеней.

2017-05-11 в 11:10 

IWannaBeTheVeryBest
Не знаю, меня как-то напрягает, что из каждой скобки мы можем вытащить неопределенное количество двоек...
Хотя это же вроде и доказывает, что количество нечетных множителей не превосходит m. Если из каждой скобки мы можем достать только по одной двойке, то это как раз случай, когда `k = m`. Если двоек можно вытащить больше, то тогда как раз `k < m`. А если `k` вдруг превзойдет `m`, то значит среди множителей в каноническом разложении есть двойка. Например, если `k = m + 1`, то `p_1 = 2`. Там как раз скобок будет `m`.

2017-05-11 в 11:46 

Trotil
Альтернативное доказательство.
Мне кажется, что можно как-то доказать, что если phi(x)=2, то x <=6. А далее простым перебором.

2017-05-11 в 11:52 

IWannaBeTheVeryBest
Trotil, Может быть. Но меня интересует общее решение. А если будет `\phi(x) = 40`. Откуда мне брать какую-то гипотезу о том, что `x <= 6` а может и не `6`.

2017-05-11 в 12:05 

Trotil
А если будет `\phi(x) = 40`, то x тоже будет ограничен каким-то числом сверху, но диапазон перебора будет существенно шире, что для ручного перебора уже неприменимо.

Что касается общего решения, я бы воспользовался тем, что
1) phi(x*y)=phi(x)*phi(y), если (x,y)=1
2) phi(p^m) = p^(m-1)(p-1)

и далее, раскладывая 40 на множители, тоже получал бы варианты, но здесь перебор существенно меньше.

2017-05-11 в 12:09 

IWannaBeTheVeryBest
Вообще есть мысль рассмотреть функцию Эйлера в виде
`\phi(x) = x * \prod_{i = 1}^{k} (1 - 1/(p^i)) = 2`
Вообще получается так, что
`x * (1/2) * (2/3) * (4/5) * (6/7) * \dots = 2`
Отсюда двойка получается только если `x \in {3, 4, 6}`. Ну по очевидным причинам. `4 = 2^2` значит икс умножится только на `1/2`. `3 = 3^1`, значит икс умножится только на `2/3`. Ну и `6 = 2 * 3`, значит икс умножится на `(1/2) * (2/3)`. Во всех случаях как раз выходит 2. Но просто если будет реально 40, то составлять всевозможные варианты, где получится 40 наверное будет проблематично.

2017-05-11 в 12:12 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Количество множителей в каноническом разложении равно `k`?
это количество простых делителей...

То есть если какое-то простое число в каноническом разложении имеет степень, скажем, 3, то это 1 множитель, или 3 множителя?
степень простого числа показывает, что есть ещё делители кратные степени этого простого числа...

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

Если из каждой скобки мы можем достать только по одной двойке, то это как раз случай, когда `k = m`.
не считая случая, что `p_1 = 2` ...

А если `k` вдруг превзойдет `m`
такого не бывает... ведь там речь про нечётные простые множители ...
например,
`x = 3^5 * 11^7` тогда `phi(x) = 3^4 * 11^6 * (3 - 1) * (11 - 1) = 2^2 * 3^4 * 5 * 11^6` ... число простых нечётных множителей равно степени двойки...
или
`x = 3^5 * 13^7` тогда `phi(x) = 3^4 * 13^6 * (3 - 1) * (13 - 1) = 2^3 * 3^5 * 13^6` ... число простых нечётных множителей меньше степени двойки...
и, наконец,
`x = 2^s * 3^5 * 11^7` тогда `phi(x) = 2^{s - 1} * 3^4* 11^6 * (2 - 1) * (3 - 1) * (11 - 1) = 2^{s - 1 + 2} * 3^4* 5 * 13^6`... Если степень `s = 1`, то полученная степень двойки равна числу простых нечётных множителей... если `s > 1`, то число простых нечётных множителей меньше степени двойки...

2017-05-11 в 12:15 

Trotil
> Откуда мне брать какую-то гипотезу о том, что `x <= 6` а может и не `6`.
А, нашел интересное: ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%...

Число A(x) и есть возможное максимальное число.

2017-05-11 в 12:15 

Trotil
> Откуда мне брать какую-то гипотезу о том, что `x <= 6` а может и не `6`.
А, нашел интересное: ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%...

Число A(x) и есть возможное максимальное число.

2017-05-11 в 12:16 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
мдя... долго писал... :shuffle2:

2017-05-11 в 12:48 

IWannaBeTheVeryBest
Так, ну со степенями понял. Но в данном случае опять же двойка была и, ну как по мне, можно было решить быстрее, чем в учебнике написано. Хотя возможно там был какой-то общий подход.
Вот интересно, если все же `\phi(x) = 40`
Количество натуральных делителей 40 `\tau(40) = \tau(2^3 * 5) = (3 + 1) * (1 + 1) = 8`
Это множество `{1,2,4,5,8,10,20,40}`
Это как считать `A(40)`? Ну получается, что надо подбирать такие делители 40... `p - 1` короче, где `p` - простое. То есть это множество `{1,2,4,10,40}`.
Получается
`A(40) = 40 * 2/1 * 3/2 * 5/4 * 11/10 * 41/40 = (3 * 11 * 41)/8`
Какое-то не целое число получается. Или я что-то не так считаю?

2017-05-11 в 13:00 

IWannaBeTheVeryBest
У меня с 40 получилось `{41; 55}`. Вообще говоря подбирать не так то и сложно.

2017-05-11 в 13:36 

Trotil
Может быть оно и не обязано быть целым?

P.S. Вольфрам видит и другие решения: www.wolframalpha.com/input/?i=phi(x)%3D40

2017-05-11 в 14:34 

IWannaBeTheVeryBest
Да, подбирать труднее, чем мне казалось.

2017-05-11 в 14:36 

IWannaBeTheVeryBest
Кстати. Видимо определение функции Эйлера везде разное. Просто в учебнике решением уравнения `phi(x) = 2` является `{3; 4; 6}`
А по вольфраму `{+-3; +-4; +-6}`

2017-05-11 в 14:56 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
А по вольфраму `{+-3; +-4; +-6}`
Возможно он определяет как число положительных чисел простых с `x`... поэтому отрицательные тоже указывает...

2017-05-11 в 15:10 

IWannaBeTheVeryBest
Возможно он определяет как число положительных чисел простых с
Возможно.
А вы не знаете, существует ли вообще общий подход к решению таких уравнений? или всегда нужно по разному решать?
Я в принципе разобрался как решить можно, но подбором через `\phi(x) = x * \prod (1 - 1/p)`. И что-то это нисколько не весело при больших числах.

2017-05-11 в 19:43 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
А вы не знаете, существует ли вообще общий подход к решению таких уравнений? или всегда нужно по разному решать?
тут я не подскажу, поскольку достаточно чахлый специалист в этой области... :nope:

2017-05-11 в 20:38 

IWannaBeTheVeryBest
Ладно. Всем спасибо))

   

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная