Листок 8. Классы вычетов.

Выдан 21.11.84 Закрытие 1.12.84

"Кто не с нами, тот против нас!"

Опр.1 B₁,B₂, ...,B_n -разбиение мн-ва B на классы ⇐df⇒ (B₁∪B₂∪...∪B_n = B) .AND. (∀i,j: i≠j ⇒ B_i∩B_j = ∅)

Onp.2 "i"-классом по модулю m (пишем A_i,m OR A_i OR A[i]) называется A_i={a| a≡i (mod m), a≥0}

1. Доказать , что существует m различных классов по mod m.

2. а)(∀ x∈ A_i и y∈ A_j)⇒(x+y)∈ A_i+j
Это означает, что A_i+A_j=A_i+j
b) A₀ + A_i = A_i

3. Аналогичные утверждения для A_i*A_j

5. а)∀i,j ∃k,h: A_i+A_j=A_k .AND. A_i+A_j=A_h
b) ∃A₀, A₁: A₀ + A_i = A_i; A₁ * A_i = A_i
c) A_i+A_j = A_j+A_i; A_i*A_j = A_j*A_i
d) A_i + (A_j+A_k) = (A_i + A_j) + A_k; A_i * (A_j*A_k) = (A_i * A_j) * A_k;
e) (A_i + A_j) * A_k = A_i * A_k + A_j * A_k
f) ∀i ∃j: A_i+A_j=A₀
Примечание: ∀ {A_i} удовлетворяющее 2,3,5 называется Комутативным Кольцом с Единицей.

Опр. 3^* n*A_i =df= A_i + A_i + ... +A_i n слагаемых
A_iⁿ =df= A_i * A_i * ... * A_i - n сомножителей

6. Функция f(a) -"правильная", т. е. ∀ i ∃ j ∀ a: а∈А_i ⇒ f(а)∈А_j записываем: f(А_i)=А_j
а) ∃c_i: f(A_i)=c₀*A_iⁿ +c₁*A_i^n-1+...+c_n*A_i
b)^* f(A_i)=A[f(i)]
с) опишите множество правильных функций.

7. Пример, когда A_i*A_j=A₀ , но A_i≠A₀ AND A_j≠A₀

8. р∈Р ⇔ ( (A_i,p≠A_0,p .AND. A_j,p≠A_0,p) ⇒ (A_i,p*A_i,p≠A_0,p))

Опp 4. Полной системой вычетов по некоторому модулю (PSV) называется мн-во чисел, взятый по одному из каждого класса по этому mod.

9. Написать примеры PSV по модулю 12,7.

10. НОД (a, m)=1; x₁, х₂,... x_m - попарно не сравнимы по модулю m: y_i=a*x_i+b ⇒ {y₁, y₂,... y_m} = PSV(mod m)

11. НОД (a, m/d)=d; x₁, х₂,... x_m - попарно не сравнимы по модулю m/d; y₁, y₂,... y_m: y_i=a/d*x_i+b ⇒ {y₁, y₂,... y_m} = PSV(mod m/d)

12. НОД (m, n)=1; {x₁, x₂,... x_m} = PSV(mod m); {y₁, y₂,... y_n} = PSV(mod n)⇒ {z | z = m*x_i+n*y_j} = PSV(mod m*n)

13. s=s₁*s₂*...*s_n и все s_i и s_j попарно взаимно просты; x_i пробегает все значения PSV(mod s_i) ⇒ {z | z = s/s₁*x₁+s/s₂*x₂+...+ s/s_n*x_n} = PSV(mod s)

Опр.5 НОД(A_i)=d ⇐df⇒ ∃ d ∀ a∈A_i НОД(a,m) =d

14. Доказать существование и единственость НОД(A_i)

15. НОД(A_8,6) и доказательство его единственности.

16. Верно ли,что НОД(A_i)=d ⇔ {а,b}⊂A_i: НОД(а,b)=d?

Опр 6. приведеной (неполной) системой вычетов (NSV) по модулю m называется мн-во чисел, взятых по одному из каждого класса A_i причем НОД(A_i)=1

17. Написать по 3 NSV anm m=4; 5; 18

18. Сформулировать (?) и доказать (*) для NSV свойства, аналогичные свойствам PSV.

19^* Теорема ЭЙЛЕРА
NSV(mod m) содержит k чисел; а≥1; НОД (a, m)=1 ⇒ а^k≡1 (mod m)
Указание: {x₁, x₂,... x_k}=NSV ⇒{a*x₁, a*x₂,... a*x_k}=NSV

20. Остаток от деления 135⁸⁹⁶⁴ на 44

21. ∀a: f(a)≡ 0(mod m) ⇒ ∀b ≡ a (mod m): f(b) ≡ 0 (mod m)

"Практика -критерий истинности"

22. Решить с помощью 21
a) х³ - 2х + 6 ≡ 0 (mod 11)
b) х⁴ - х³ - х² + 5х - 2 ≡ 0 (mod 6)
c) х³ - х ≡ 0 (mod 6)
d) 30²⁰ ≡ х (mod 7)
e) 15х + 11 ≡ 4 (mod 10)
f) х²≡ 2 (mod 9) .AND. х³ + 3 ≡ x (mod 9)

23 a) x ≡ 9 (mod 34) .AND. x ≡ 4 (mod 19)
b) x ≡ 29 (mod 29) .AND. x ≡ 9 (mod 35)
c) 7x ≡ 5 (mod 11) .AND. 3x ≡ 2 (mod 5)

24. (∃ k ≡ a (mod n) .AND. k ≡ b (mod m)).AND. НОД(m,n) = d) ⇒ | a - b | ⋮ d

25. a) x ≡ 2 (mod 7) .AND. x ≡ 5 (mod 9) .AND. x ≡ 11 (mod 15)
b) x ≡ 6 (mod 17) .AND. x ≡ 4 (mod 11) .AND. x ≡ 13 (mod 8)
c) x ≡ a (mod 25) .AND. x ≡ b (mod 27) .AND. x ≡ c (mod 59)

26. a) 9x² + 29x + 62 ≡ 0 (mod 64)
b) x³ + 2x + 2 ≡ 0 (mod 125)