ALG#03 (Лекции Кузьмина)

либо совпадают. , где , т.е. выкидываем все совпадения, т.е. разложим множество на объединения непересекающихся подмножеств. И т.к. р – взаимное отображение. где

Следствие1: Все блоки импримитивности, полученные из заданного блока действием на него подстановок из группы G, имеют одинаковую мощность.

Следствие2: Множество может быть представлено в виде объединения попарно не пересекающихся блоков импримитивности.

Условие примитивности сильнее условия транзитивности, но как?

Теорема: Пусть G – 2-транзитивная группа подстановок, значит она примитивна.

Док-во: Пусть в 2-транзитиной группе G есть блок импримитивности . Пусть G – не примитивна. ; С другой стороны т.к. группа 2-транзитивна - это противоречит, т.е. блок импримитивности не существует, значит группа примитивна.

Замечание: Примитивная группа не имеет гомоморфизмов на группу меньшей мощности.

Утв: Пусть G – транзитивная импримитивная группа. - блок импримитивности; , где Н – подстановка на множестве .

Док-во: т.е. . Пусть , для .

Задача: Введем БО на . Докажем, что это отношение эквивалентности:

1. Рефлективное: .

2. Симметричное: .

3. Транзитивность: отбиты совпадают

Если орбиты то они совпадают? Пусть a - это уравнение в группе разрешимо однозначно, значит перебирая все g, получаем все .

Задача: , группа G, - блок импримитивности.

. Доказать: , т.к. любое разбиение на не пересекающиеся множество эквивалентно введению БО эквивалентности.

Задача:

, т.е. либо переходит сам в себя, либо на пересекается.

- это переход самих элементов.

тоже блок.

Кольцо целых чисел.

Опр: Число a делится на число b: b|a если .

Следствие: Если а=0, b|a => b=0, т.к. bc=0.

Опр: Деление с остатком а на b – это представление а в виде: a=bq+r, .

Замечание: Пусть b=3, то 2,-2 при делении на 3 имеют разные остатки: 2=0*3+2; -2=(-1)*3+1.

Утв: Для любых положительных чисел a,b число а всегда можно разложить на b, и разложение определяется однозначно.

1. Пусть ;

2. Пусть (Лемма Архимеда)

3. Однозначность: Пусть есть два таких числа q1,q2: a=q1b+r1; a=q2b+r2: - отличаются хотя бы в одной координате и пусть .

Пусть противоречит однозначность результата деления (в кольце Z).

Опр: Числа a,b – сравнимы по modn, если остатки от деления a,b на n совпадают. .

Обозначение: .

Утв: Числа a,b сравнимы тогда и тогда, когда их разность делится на n, т.е. .

Док-во:

1. Прямое: - по определению делимости.

2. (по условию) , а единственное совпадение в 0 - по определению.

Теорема: Отношение сравнимости по mod n (n>1) – конгруэнция кольца целых чисел.

Док-во:

1. - отношение эквивалентности-?

2. Согласованность операций в кольце с отношением :

   1. Сложение: докажем это: т.к. .

   2. Умножение a1b1 a2b2:

a1b1 a2b2 Это конгруэнция кольца.

NOD, NOK целых чисел.

Опр: NOD целых чисел a,b(a,b)=d – натуральное число

1. d|a, d|b;

2. (т.е. d – max).

Опр:

1. a|D,b|D;

2. (т.е. D – min).

Теорема “Алгоритм Евклида построения NOD 2-х чисел”: Пусть даны

1. Делим а с остатком на b:

2. Тогда NOD(a,b)=Rn – последний ненулевой остаток в этой цепочке.

Док-во:

1. Лемма: . Пусть . Покажем, что т.к. - некоторый делитель 2-х чисел т.к.

2. 1. Сходимость алгоритма: не более чем за |b| шагов последовательность rn начнет состоять из одних нулей, а последовательность конечная значит можно найти последний ненулевой остаток. Пусть .

   2. Почему (a,b)=(a-q1b,b) – по Лемме т.е.

Теорема: Пусть .

Док-во: (по индукции) Покажем, что в условиях предыдущей теоремы: . Введем 2 последовательности чисел:

1. Пусть к=1

2. Пусть k<n – выполнено это свойство. k=n-? , а в предыдущей теореме:

Опр: a,b – взаимнопросты .

Следствие: .

Док-во: Прямое следует из теоремы. Обратное пусть пусть .

Свойства взаимно простых чисел.

Опр: – простое – если оно делится только на 1 и само на себя.

Опр: b – собственный делитель а, если b|a, 1<b<|a|. Другими словами р – простое, если оно не имеет собственных делителей.

Утв: Если р – простое и p|ab то p|a или p|b (или оба).

Док-во:

1. Пусть p|b

2. Пусть Пусть - противоречит - по свойству 3.

Теорема: Любое целое число однозначно с точностью до перестановки сомножителей представляется в виде: -попарно различные простые числа.

Док-во:

1. Пусть n – простое т.е. для всех простых чисел теорема верна.

2. По индукции по n:

   1. n=2 – очевидно

   2. Пусть n<k – верно

n=k-? Если простое то см 1) иначе k – составное , но т.к. 1<k1,k2<k, то то для них выполняется предположение индукции: перемножая эти представления и складывая показатели при одинаковых , получаем нужное представление для k.

Покажем, что данное разложение однозначно: Пусть есть два представления для n: - т.к. знак числа, а рассматриваем только произведения: ; (т.к. оба простые) и т.к. эти множества равны т.е. наборы совпадают ; m1=min{r1,l1}; поделим равенство на Пусть пусть l1>m1 - входит в правую часть - делит левую часть но все - попарно различны – противоречит. Пусть l1=m1 => по аналогии все степени совпадают.

Опр: Представление целого числа n в виде произведения степеней попарно различных простых чисел – каноническое разложение числа n.