Вывести формулу зависимости количества правильных дробей от $%n$%, которые невозможно сократить, где числитель находится в промежутке $%1..n$%, а знаменатель равен $%n$%. Как подойти к решению такой задачки?

задан 28 Апр '15 12:20

изменен 28 Апр '15 12:38

Сначала немного не правильно сформулировал.

(28 Апр '15 12:33) Isaev
1

Да, тут функция Эйлера в чистом виде: несократимость означает взаимную простоту числителя и знаменателя.

(28 Апр '15 14:25) falcao
10|600 символов нужно символов осталось
2

Думаю, можно использовать Функцию Эйлера

Например, $%n=24$% $$\varphi (24)=8$$ $$\frac{1}{24}; \frac{5}{24}; \frac{7}{24};\frac{11}{24};\frac{13}{24};\frac{17}{24};\frac{19}{24};\frac{23}{24}$$ В общем виде: $$\varphi (n)=n \prod_{p|n}\left ( 1-\frac{1}{p} \right )$$

ссылка

отвечен 28 Апр '15 12:29

изменен 28 Апр '15 12:43

Но если знаменатель кратен какому-либо простому числу, то должно отсеиться больше дробей?

(28 Апр '15 12:42) Isaev

Наоборот, в случае простого $%p$% $$\varphi (p)=p-1$$ Пример, $%p=3, \varphi (3)=3-1=2$% $$\frac{1}{3}; \frac{2}{3}$$

(28 Апр '15 12:45) Роман83

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

(28 Апр '15 13:11) Isaev
1

Общий случай: $$n=p_{1}^{\alpha_1}\cdot p_{2}^{\alpha_2} \cdot p_{k}^{\alpha_k}$$ $$\varphi(n)=n(1-1/p_1)(1-1/p_2)...(1-1/p_k)$$

(28 Апр '15 13:35) Роман83

"где $%p$% — простое число и пробегает все значения, участвующие в разложении $%n$% на простые сомножители." Вот это я упустил, потому и туплю) Спасибо, работает!

(28 Апр '15 13:49) Isaev
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×669
×80

задан
28 Апр '15 12:20

показан
299 раз

обновлен
28 Апр '15 14:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru