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

[TOPEHTO]

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

[TOPEHTO]

С каждым разом все яснее и яснее

НОД(x, 0) = x
НОД(x, y + 1) = f(... тут юзаешь формулу; вот здесь - куча подстановок как раз ...)

Вот это писать вместо блаблабла?
Тады вот тут НОД(x, y + 1) =
Что такого отписать, просто в душе не понимаю примеры глянул кое-что попонятней
И насчет деления, говорят что х\у не прим-рекурсия...3\5 не принадлежит натуральным числам, вот [3\5] , т.е. взятие целой части-прим\рекурсия...но это в принципе доказано, просто удостовериваюсь
И еще масенький вопрос:
НОК:НОК(x, y) = x * y / НОД(x, y)
т.е. доказав НОД, НОК впринципе доказывается уже автоматическм, да?

Добавлено через 1 мин.
СпасиБеще ОГРОМНОЕ за ПОМОЩЬ!!!!!!!!!!!!!!!!!!!!!