Попробовал найти формулу алгоритма Евклида в явном виде. Получилось нечто вида:



![$q_{n-3}[q_{n-2}(q_{n-1}q_n+1)+1]+q_{n-1}q_n+1$ $q_{n-3}[q_{n-2}(q_{n-1}q_n+1)+1]+q_{n-1}q_n+1$](https://dxdy-01.korotkov.co.uk/f/c/2/8/c2802c53219b9257efd1fa9c345202e582.png)
![$q_{n-4}\left(q_{n-3}[q_{n-2}(q_{n-1}q_n+1)+1]+q_{n-1}q_n+1\right)+q_{n-2}(q_{n-1}q_n+1)+1$ $q_{n-4}\left(q_{n-3}[q_{n-2}(q_{n-1}q_n+1)+1]+q_{n-1}q_n+1\right)+q_{n-2}(q_{n-1}q_n+1)+1$](https://dxdy-01.korotkov.co.uk/f/8/f/4/8f408d882ad22dae9df415ee5456d56682.png)
............
я даже не знаю как это грамотно скомпоновать
В общем, в следующем шаге последний член будет умножаться на

и к нему будет прибавляться предпоследний. В итоге в самом конце должна получиться некоторая "бериберда", которая возможно как-то "собирается". В любом случае, применять такую формулу для анализа очень нецелесообразно.
где
![$q_1=\left[\dfrac ab\right]$ $q_1=\left[\dfrac ab\right]$](https://dxdy-04.korotkov.co.uk/f/7/7/4/774eb5e679920fb2a7d99bd3fe7b3e7982.png)
,
![$q_2=\left[\dfrac{b}{a\mod b}\right]$ $q_2=\left[\dfrac{b}{a\mod b}\right]$](https://dxdy-04.korotkov.co.uk/f/f/f/b/ffbc1ad58fce9b7987d74bf8131fd7ed82.png)
,
![$q_3=\dfrac{a\mod b}{b-\left[\dfrac{b}{a\mod b}\right]\cdot (a\mod b)}$ $q_3=\dfrac{a\mod b}{b-\left[\dfrac{b}{a\mod b}\right]\cdot (a\mod b)}$](https://dxdy-02.korotkov.co.uk/f/d/4/b/d4ba2b1af4d2f0d567a3c815cea348b982.png)
,............,

в квадратных скобках указана целая часть числа.
Для

знаменатель из

уйдёт в числитель, а знаменатель ещё более усложнится.
Должна быть более простая формула, уж слишком что-то замудрено для такого простого алгоритма, который пишется буквально в три строчки.
-- Вс мар 13, 2011 23:17:07 --
Пфф, а вобще не так)
Надо выразить

через

.

Значит

Откуда выражается

:


- Тоже должно быть целым, значит

.
И возвращаем всё это в начальные переменные.


Ну это вы переписали тот же алгоритм Евклида: остаток, потом остаток на остаток и т.д. Если числа будут большие то рассуждение пропорционально вырастет.
-- Вс мар 13, 2011 23:24:45 --Можно. Например, так:

. Только обычно проку от таких формул мало.
Спасибо. Насколько я понимаю

- это функция Эйлера? Формула необходима для анализа некоего выражения, поэтому желательно всё же чтобы ей можно было как-то манипулировать.
Если ваша формула верна, необходимо доказать, что всякое целое число

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

.
здесь

- любые целые числа.
Либо показать те целые числа, которые такой формой не представимы.