Как доказать, что в кольце чисел вида $%a+\sqrt{b}$%, где $%a,b∈Z$% работает алгоритм Евклида?

задан 8 Дек '18 12:42

изменен 8 Дек '18 12:43

1

найти инвариант: ограниченный снизу функционал, который строго убывает на последовательности чисел, получаемых алгоритмом.

(8 Дек '18 12:50) spades

Как искать этот инвариант? Пока могу только доказать нестрогими рассуждениями, что после первого шага новых радикалов не возникает, а меняются лишь коэффициенты перед ними, причём целые. Для целых a алгоритм работает и через некоторое количество шагов a сгорят и останутся два радикала, которые сгорают максимум за два действия.

(8 Дек '18 13:52) Autocellar

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

(8 Дек '18 14:13) spades
1

@Autocellar: это неверно. Легко привести примеры неевклидовых колец такого вида. В них не всегда есть факториальность. Простейший пример -- разложение $%2\cdot2=(1+\sqrt{-3})(1-\sqrt{-3})$% для $%b=-3$%.

(8 Дек '18 17:15) falcao

Я по невнимательности думал, что b>0, там норма понятна. @falcao, условие факториальности ведь не единственное. Есть факториальные кольца такого вида без евклидовости?

(8 Дек '18 17:41) spades

@spades: это да, но евклидовость влечёт факториальность, а здесь её нет, поэтому нет и евклидовости.

Условие b > 0 тоже ничего не гарантирует.

(8 Дек '18 18:10) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×16

задан
8 Дек '18 12:42

показан
100 раз

обновлен
8 Дек '18 18:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru