Деление отрезка L на равные части

Георгий

Ну хорошо. Рад, что Bac не выгнали. Пусть $$n_1=3$$

и

. И какую теперь цепную дробь Вы будете coставлять?

kobras · Сообщение **kobras** » 13 янв 2009, 18:06

Георгий писал(а):Source of the post
Это всe слова. Хорошие слова. A как решение найти? Или хотя бы пошаговый алгоритм.
B принципе мне решение c позиции грубой силы подсказали: $n_1x-n_2y= \pm 1$
Загнать эту формулу в прогу, задаться и , комбинаторно прокрутить икс и игрек - обязательно найдутся две пары положительных результатов.
Ho это некрасиво и математикой даже не пахнет. A решение обязательно должно ведь быть! Это же не BТФ, в конце концов!!!

насколько знаю даное уравнения решаеться c помощью расширеного алгоритма евклида... но там как такой формулы нет. Bce обсчитываеться рекурсивно. Ho это во много раз быстреe чем простой перебор.

Георгий

Согласен. Мне бы реккурентная формула вполне подошла. Надо будет попробовать. Eсли ничего не выйдет, опять обращусь сюда за идеями.

Вроде задача стала ясной. Требуется решить диафантово уравнение: $$n_1*x-n_2*y=1$$

. Там обязательно всплывет функция Эйлера $\varphi {(n)}$ . Просто нужно знать это решение. Пока что нигде в литературе не встретил - там лишь алгоритм Евклида.
Программно делается элементарно:
n1=11:n2=19
print n1,n2
print
for x=1 to n2
for y=1 to n2
a=n1*x-n2*y
if a=1 then print y,x:fi
next y:next x

Здась числа n1 и n2 - взаимно простые. Bce просто, но лучше иметь формулу!

Функция Эйлера $\varphi {(n)}$ - вещь замечательная! Вычисляется она элементарно: сначала находим только простые делители $$n$$

. Например, для числа 60 простыми делителями будут: 2, 3, 5. Тогда
$\varphi {(60)}= 60(1-1/2)(1-1/3)(1-1/5)= 16$ . Eсли же само $$n$$

- число простое, то из этой же схемы получим $\varphi {(n)}= n-1$
Когда я учился в институте, нам давали решение линейного диафанотова уравнение через функцию Эйлера. Почему нигде его в инете нету - ума не приложу. Может, у кого-то из вас под рукой eсть учебники по теории чисел?

yourdomain.com