Продолжаем, нашу тему про аликвотные дроби. В предыдущей статье Египетские (аликвотные) дроби мы упомянули, что некоторые дроби в знаменателе которого стоит какое либо число в степени при определенных условиях может быть выражена суммой двух египетских дробей.
Мы вычислили что любую дробь вида
\(\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}\)