Iteraciones de funcionamiento del módulo

Question

Mientras trabajaba en algo completamente diferente de la tarea, pensé hasta el siguiente problema:

Considere el siguiente proceso. Deje $a_0$$n$, y determinar el $a_1,\ldots, a_k$ como sigue: $$a_{j+1} = n \text{ mod } a_j$$ ...donde el proceso termina cuando se $a_j \mid n$. Es decir, $a_k = 0$.

Definir $f(a_0, n) = k$.

Aparte de dirigir la iteración, ¿cómo podría uno compute o expresar $f(a_0, n)$?

Ejemplo: $f(124323, 938342) = 12$

68081 = 938342 mod 124323
53289 = 938342 mod 68081
32429 = 938342 mod 53289
30330 = 938342 mod 32429
28442 = 938342 mod 30330
28198 = 938342 mod 28442
 7808 = 938342 mod 28198
 1382 = 938342 mod 7808
 1346 = 938342 mod 1382
  180 = 938342 mod 1346
    2 = 938342 mod 180
    0 = 938342 mod 2

Este proceso termina siempre (como puede ser trivialmente demostrado).

Aparte de las obvias $f(n\pm1, n)$ de los casos, realmente no sé por dónde empezar a acercarse a este, problemas que acabo de pensar tienden a ser más difícil que la de matemáticas que yo conozco. ;)

Así que, mis preguntas son:
1) Obviamente, si alguien ve una evidente ruta para hacer este cálculo, que sería genial.
2) Si esto es algo que se sabe que es imposible, que también sería bueno saber.
3) Si alguien tiene una sugerencia, te agradecería que ... me gusta tratando de entender las cosas, pero sé que los buenos consejos pueden ser difíciles de escribir.

Answer 1

Esto es lo que yo llamo el algoritmo de Gauss para calcular inversas, al $n = p$ prime. Mediante la sustitución de $a$ $a' := n\ {\rm mod}\ a = n - qa\,$ rendimientos $a'\equiv -qa\,$ que es un menor múltiplo de $a$. Reiteró, se produce un descenso en los elementos del ideal de la $(a)$ de todos los múltiplos de $a$ mod $n$. Se termina con un factor de $n$. Este factor puede ser $1$ al $n = p$ es primo, lo que demuestra que el $1$ es un múltiplo de a $a$, por el producto de la secuencia de cocientes $q_i,\,$ dando así $\,a^{-1}$ mod $n$.