Теория алгоритмов, А тут мне помогут?:( Опции

[TOPEHTO]

Народ нужна ваша помощь! подскажите хотя бы с чего начать:Нужно доказать что НОД и НОК примитивно рекурсивные функции...кто поможет?

[TOPEHTO]

Насчета НОКа Я правильно написал-то?
и еще НОК(х,0)=х
НОК(х,у+1)=f(x,y,f(x,y))
???
потом, честно как с I3 действовать так и не понял...
примерно получил:
f(x,y,z)=(i1(x,y,z),s(i3(x,y,z))
помойму так...где-то...
и еще такой вопрос, если рассмотреть на конкретном примере:
НОД(27,9)=(27-9,9)
что еще надо дописать чтобы смело написать что этот НОД равен 9, с точки зрения грамотности
СпасиБо за помощь

Добавлено через 2 мин.
Кста, как просто деление например доказать:x / y = 1 + (x - y) / y.
???
чето Я совсем запутался((