57 школа, 9 класс
22 декабря 2001 г.

Алгоритм Евклида

В этом листочке множество K - это или Z, или Q[x], или Z[i].

Пусть a и b принадлежат K. Определим множество I(а, b) следующим образом: I(а, b) = {n из K | существуют x из K и y из K такие, что ax+by=n}.

1. Пусть K = Z. Верно ли, что:
а) число 18 принадлежит I(15, 57)
б) число 11 принадлежит I(46, 68)?

2. Можно ли утверждать, что при любых a из K и b из K множество I(а, b) является идеалом в K?

В задачах 6, 7а, 8а из листочка Главные идеалы было доказано, что каждый непустой идеал в Z, Q[x] и Z[i] является главным, то есть имеет вид I(а). Это, в частности, означает, что для любых а и b найдется с, такое что I(а, b) = I(с).

3. Пусть K = Q[x]. Найдите многочлен с, такой что I(x³-1, x²-1) = I(с).

Сейчас мы еще раз докажем подчеркнутое выше утверждение для Z, Q[x] и Z[i] (и вообще, для любого множества, в котором есть деление с остатком). Заодно мы научимся по данным а и b находить с, такое что I(а, b) = I(с).

4. Пусть K = Z[i]. Найдите с, такое что I(101, 3+30i) = I(с).

(Алгоритм Евклида.) Пусть даны а₁ и а₂ принадлежащие K. Определим числа а₃, а₄, ..., а_n. Если а_i-1 не делится на а_i, то положим а_i+1 равным остатку от деления а_i-1 на а_i. Если а_i-1 делится на а_i, то последовательность на этом заканчивается.

5. Выпишите последовательность Евклида
а) для целых чисел
б) для гауссовых чисел
в) для многочленов
(здесь давались индивидуальные задания).

6. Докажите, что при любых а₁ и а₂ последовательность Евклида конечна.

7. Пусть алгоритм Евклида для чисел а₁ и а₂ дал последовательность а₃, ..., а_n.
а) Можно ли утверждать, что а_i принадлежит I(а₁, а₂) при любом i?
б) Можно ли утверждать, что I(а₁, а₂) = I(а_n)?

8. Через 10 дней начнется год, номер которого одинаково читается слева направо и справа налево. Когда был предыдущий год с таким свойством? Когда будет следующий год с таким свойством?