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

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

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

Опр.1 B1,B2, ...,Bn -разбиение мн-ва B на классы ⇐df⇒ (B1∪B2∪...∪Bn = B) .AND. (∀i,j: i≠j ⇒ Bi∩Bj = ∅)

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

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

2. а)(∀ x∈ Ai и y∈ Aj)⇒(x+y)∈ Ai+j
Это означает, что Ai+Aj=Ai+j
b) A0 + Ai = Ai

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

5. а)∀i,j ∃k,h: Ai+Aj=Ak .AND. Ai+Aj=Ah
b) ∃A0, A1: A0 + Ai = Ai; A1 * Ai = Ai
c) Ai+Aj = Aj+Ai; Ai*Aj = Aj*Ai
d) Ai + (Aj+Ak) = (Ai + Aj) + Ak; Ai * (Aj*Ak) = (Ai * Aj) * Ak;
e) (Ai + Aj) * Ak = Ai * Ak + Aj * Ak
f) ∀i ∃j: Ai+Aj=A0
Примечание: ∀ {Ai} удовлетворяющее 2,3,5 называется Комутативным Кольцом с Единицей.

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

6. Функция f(a) -"правильная", т. е. ∀ i ∃ j ∀ a: а∈Аi ⇒ f(а)∈Аj записываем: f(Аi)=Аj
а) ∃ci: f(Ai)=c0*Ain +c1*Ain-1+...+cn*Ai
b)* f(Ai)=A[f(i)]
с) опишите множество правильных функций.

7. Пример, когда Ai*Aj=A0 , но Ai≠A0 AND Aj≠A0

8. р∈Р ⇔ ( (Ai,p≠A0,p .AND. Aj,p≠A0,p) ⇒ (Ai,p*Ai,p≠A0,p))

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

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

10. НОД (a, m)=1; x1, х2,... xm - попарно не сравнимы по модулю m: yi=a*xi+b ⇒ {y1, y2,... ym} = PSV(mod m)

11. НОД (a, m/d)=d; x1, х2,... xm - попарно не сравнимы по модулю m/d; y1, y2,... ym: yi=a/d*xi+b ⇒ {y1, y2,... ym} = PSV(mod m/d)

12. НОД (m, n)=1; {x1, x2,... xm} = PSV(mod m); {y1, y2,... yn} = PSV(mod n)⇒ {z | z = m*xi+n*yj} = PSV(mod m*n)

13. s=s1*s2*...*sn и все si и sj попарно взаимно просты; xi пробегает все значения PSV(mod si) ⇒ {z | z = s/s1*x1+s/s2*x2+...+ s/sn*xn} = PSV(mod s)

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

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

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

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

Опр 6. приведеной (неполной) системой вычетов (NSV) по модулю m называется мн-во чисел, взятых по одному из каждого класса Ai причем НОД(Ai)=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)
Указание: {x1, x2,... xk}=NSV ⇒{a*x1, a*x2,... a*xk}=NSV

20. Остаток от деления 1358964 на 44

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

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

22. Решить с помощью 21
a) х3 - 2х + 6 ≡ 0 (mod 11)
b) х4 - х3 - х2 + 5х - 2 ≡ 0 (mod 6)
c) х3 - х ≡ 0 (mod 6)
d) 3020 ≡ х (mod 7)
e) 15х + 11 ≡ 4 (mod 10)
f) х2≡ 2 (mod 9) .AND. х3 + 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) 9x2 + 29x + 62 ≡ 0 (mod 64)
b) x3 + 2x + 2 ≡ 0 (mod 125)

Contact me!

Contact Information
Search

Home
Standard
Science
Teacher
Listok08

Skin:

Last modified
May 7, 2008

Slide show for teacher - double click on image to start
Slide show for teacher