57 школа, 9 класс
19 января 2002

Неразложимые числа

В этом листочке множество K - это Z, Q, Z[x], Q[x], Z[(-5)^1/2] или Z[i].

Напомним, что запись a|b означает, что а делит b, или, другими словами, b делится на а. Мы говорим, что u обратимо, если u|1.

1. Опишите множество всех обратимых элементов:
   a) в Z,
   б) в Z[i],
   в) в Z[(-5)^1/2],
   г) в Q[x],
   д) в Z[x].

   Числа а и b называются эквивалентными (обозначение: a~b), если a|b и b|a.

2. Верно ли, что 2~6 в множестве:
   а) Z?
   б) Q[x]?

3. Пусть A и B принадлежат Z[i] и N(A)=N(B). Можно ли утверждать, что A~B?

4. Можно ли утверждать, что если a~b и b~c, то a~c?

5. Можно ли утверждать, что если a~b, с~d и a делится на c, то b делится на d?

6. Верно ли, что:
   а) если а=bu, где u - обратимо, то a~b?
   б) если a~b, то существует обратимое u, такое что а=bu?

7. Можно ли утверждать, что если a~b, то I(a)=I(b)?

8. Пусть a~b и c~d. Можно ли утверждать, что
   а) aс ~ bd?
   б) a+с ~ b+d?

   Необратимое а из K называется неразложимым, если его нельзя представить в виде произведения двух необратимых элементов K.

9. Можно ли утверждать, что если p - неразложимо и c|p, то с~р или c~1?

10. Докажите, что если p - неразложимо и идеал I(a, p) является главным, то либо I(a, p)= I(p) и а делится на р, либо I(a, p)= I(1).

11. Пусть p - неразложимо и а не делится на p. Можно ли утверждать, что существуют X и Y такие, что aX+pY=1? Каков ответ на этот вопрос:
    а) в Z?
    б) в Z[i]?
    в) в Z[(-5)^1/2]?
    г) в Q[x]?
    д) в Z[x]?

12. Пусть p - неразложимо, а не делится на p, и b не делится на p. Можно ли утверждать, что аb не делится на p? Каков ответ на этот вопрос:
    а) в Z?
    б) в Z[i]?
    в) в Z[(-5)^1/2]?
    г) в Q[x]?
    д) в Z[x]?

13. Докажите, что каждый ненулевой необратимый элемент равен произведению конечного набора неразложимых элементов. (Произведение одного сомножителя считается равным этому сомножителю.)

    Простые числа (неразложимые числа в Z)

    В задачах 14-27 число р - натуральное простое, n и k - натуральные числа, а и b - произвольные целые числа.

14. Докажите, что следующие числа попарно взаимно просты (то есть никакие два из этих чисел не имеют общего делителя, большего 1):

    2+1, 2²+1, 2⁴+1, ..., 2²ⁿ+1.

15. Докажите, что существует бесконечно много простых чисел.

16. (Простые числа Ферма) Докажите, что если р = 2ⁿ+1, то n = 2^k при некотором целом k.

17. Пусть а не делится на p. Докажите, что существует b, такое что ab сравнимо с 1 по модулю p.

18. Пусть а не делится на p. Докажите, что числа 0, а, 2а, 3а, ..., (р-1)а попарно несравнимы по модулю р.

19. (Теорема Вильсона) Докажите, что р является простым числом в том и только том случае, если р|(р-1)!+1.

20. (Малая теорема Ферма) Докажите, что р|а^р-а.

21. Докажите, что существует бесконечно много простых чисел вида
    а) р = 3k + 2
    б) р = 4k + 3
    в) р = 6k + 5.

22. Докажите, что a² сравнимо с b² по модулю p в том и только том случае, если a сравнимо с b по модулю p или a сравнимо с -b по модулю p.

    Число а называется квадратичным вычетом по модулю р, если a сравнимо с b² по модулю p при некотором b.

23. Сколько квадратичных вычетов по модулю р найдется среди чисел 0, 1, ..., р-1?

24. Докажите, что если а - квадратичный вычет по модулю р, а не делится на р и р не равно 2, то a^(p-1)/2 сравнимо с 1 (mod p).

25. Может ли число -1 являться квадратичным вычетом по модулю р = 4k + 3?

26. Докажите, что число n не может иметь простой делитель вида р = 4k + 3, если
    а) n = а² + 1
    б) n = а² + b², где b не делится на p.

27. Докажите, что существует бесконечно много простых чисел вида р = 4k + 1.

    Построение правильных р-угольников

    Во всех последующих задачах р - нечетное простое число; a, b, k, t - целые числа, угол w равен 360/р градусов.

    Определим символ Лежандра (а/р) следующим образом:
    если р|а, то (a/p)=0
    если а является ненулевым квадратичным вычетом по модулю р, то (а/р) = 1
    если а не является квадратичнчым вычетом по модулю р, то (а/р) = -1.

28. Докажите, что (аb/р) = (a/p)(b/p).

29. Пусть f(x) - многочлен степени n с целыми коэффициентами со старшим коэффициентом 1. Докажите, что среди чисел 0, 1, ..., (р-1) найдется не более n таких a, что f(a) сравнимо с 0 (mod p).

30. Докажите, что (a/p) сравнимо с a^(p-1)/2 (mod p).

31. Докажите, что (-1/р) = 1 если и только если р сравнимо с 1 (mod 4).

32. Вычислите:
    а) sin w + sin 2w + sin 3w + ... + sin (p-1)w.
    б) cos w + cos 2w + cos 3w + ... + cos (p-1)w.

33. Обозначим
    через A_р сумму косинусов всех углов вида kw, где 0 < k < p и (k/p) = 1,
    через B_р - сумму косинусов всех углов вида ka, где 0 < k < p и (k/p) = -1.
    Вычислите:
    а) А_рB_р
    б) |Ар - Bр|

34. В предыдущей задаче замените слово "косинус" на слово "синус" и решите ее.

    Пусть а не делится на р. Порядок числа по модулю р - это наименьшее натуральное n, такое что aⁿ сравнимо с 1 по модулю р.

35. Докажите, что порядок любого числа по модулю р делит (р-1).

    В двух следующих задачах p - простое число вида 2^k+1.

36. a) Докажите, что если (а/р) = -1, то а^2k-1 сравнимо с -1 по модулю р и а имеет порядок 2^k
    б) Докажите, что если (а/р) = -1, то числа 1, а, а², a³, ..., a^(p-2) попарно не сравнимы по модулю р.

37. Пусть U_i = {u | 0 < u < p и существует а, такое что а²ⁱ сравнимо с u (mod p)}. По аналогии с квадратичными вычетами, естественно говорить, что U_i - это множество всех вычетов степени 2ⁱ.
    а) Сколько элементов в множестве U_i?
    Пусть tU_i = {k | 0 < k < p и существует u из U_i, такое что tu сравнимо с k (mod p)}.
    б) Докажите, что для любого целого t сумма косинусов всех углов вида kw, где k принадлежит tU₂, является квадратичной иррациональностью (то есть выражается через целые числа с помощью арифметических операций и квадратных корней).
    в) Верно ли то же самое для синусов?
    г) Докажите, что с помощью циркуля и линейки можно построить правильный р-угольник.