Египетские дроби. Часть вторая

Египетские дроби. Часть вторая

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

Мы вычислили что любую дробь вида

\(\cfrac{n}{p}\)

можно представить в виде

\(\cfrac{n}{p}=(b+\cfrac{c}{p})\cfrac{1}{a}\)

где параметры связаны следующими формулами

\((b*p\:)mod \:n = -c\)

\((a*n\:)mod \:p = c\)

 пусть \(b\) - равно 1.  Мы же хотим дробь представить в виде двух сумм, не так ли?

тогда дробь, где в знаменателе стоит число в степени \(k\) и которую можно представить в виде двух дробей

будет иметь следующее решение

 \(\cfrac{n}{p^k}=(1+\cfrac{1}{p^k})\cfrac{1}{a}\)

где

\((p^k\:)mod \:n = -1\)

\((a*n\:)mod \:p^k = 1\)

Если мы возведем каждую часть уравнения \((p^k\:)mod \:n = -1\) в квадрат

мы получим \((p^{2k}\:)mod \:n = 1\) что фактически приводит нас к малой теореме Ферма, которая гласит

\((p^{\phi(n)}\:)mod \:n = 1\)

Таким образом мы можем сделать вывод, что если 

\(k=\cfrac{\phi(n)}{2}\)

и \((p^k\:)mod \:n = -1\)

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

Более того, тогда и любую дробь, вида 

 \(\cfrac{n}{p^m}\)  где \(m>k\) можно будет представить в виде двух аликвотных дробей.

Проверим, дробь  \(\cfrac{4}{17^{11}}\) можно ли представить суммой двух дробей.

Определим значение функции Эйлера для числа 4. Ответ 2

Тогда \(k=1\)

\((17\:)mod \:4 = -1\) это тождество неверно, а следовательно, с учётом того что \(k=1\) ( меньше быть не может) мы можем утверждать что дробь \(\cfrac{4}{17^m}\)  - при любой степени \(m\) не представима в виде двух аликвотных дробей.

теперь давайте рассмотрим   \(\cfrac{25}{17^{11}}\) 

Функция Эйлера для числа 25  равна 20.

Тогда \(k=10\)

\((17^{10}\:)mod \:25 = -1\)

Тождество верное - а следовательно, любая дробь вида \(\cfrac{25}{17^m}\), где \(m\) равно или больше 10  можно представить как сумму двух египетских дробей.

В принципе мы можем немного улучшить критерий ( уменьшить степень знаменателя), вспомним что мы когда то 

\((p^k\:)mod \:n = -1\) возводили в квадрат ( что бы добиться в правой части  положительного числа)

Положительное число может быть не только при возведении в квадрат, но и в 4-ую степень и в 6-ую и в 8-ую и т.д....

таким образом критерий может быть таким

Если найдется такое целое число \(z\), что тождество \((p^\cfrac{\phi(n)}{2*z}\:)mod \:n = -1\)  будет верным

тогда дробь  \(\cfrac{n}{p^t}\) можно будет представить в ввиде двух египетских дробей,  при \(t>=\cfrac{\phi(n)}{2*z}\)

Поиск по сайту