takya.ru страница 1страница 2 ... страница 4страница 5
скачать файл
1. Отношение делимости и его св-ва

Опр:целое число а делится на целое отличное от нуля число в, если сущ. такое целое число с,что а=b*с.При этом а наз. делимым,b-делителем,с-частным.

Отношение делимости явл. бинарным на мн-ве Z.Обратным к этому отношение "делит".Обозначение: а|b (b делит а).



Св-ва отношения делимости:

1.Отношение делимости рефлексивно и транзитивно на мн-ве Z.

Док-во:Действительно а:а, т.к. сущ 1 пренадлежащая Z.а=а*1.Докажем транзитивность, т.е.покажем что если а:b и b:с, то а:с?

из того что а:b и b:с =>(по опр. отнош.делимости) сущ. n,m пренадлежащие Z,что а=b*n(1) и b=с*m(2).Подставим (2) в (1): а=b*n=(c*m)*n=c*(m*n)=>a:c. т.к.m,n пренадлежат Z



2.Отношение делимости сохраняется при изменении знаков делимого или делителя.Т.е. а:b=> (-a):b, a:(-b), (-a):(-b)

3.Если a:b и c:b =>(a+/- c):b. Если a:c и b принадлежит Z =>(a*b):c

Следствие(из св-ва 3): 1)а1 :с, а2:с, ...аn и Z1,Z2,...Zn пренадлежит Z => (a1z1+a2z2+...+anzn):с

2) Если a1,a2,...an : c и b1,b2,...bm:c и r1,r2,...rn,s1s2,...,sm для любых Z чисел => r1a1+r2a2+...+rnan = b1s1+b2s2+...+bmsm+ dm+1 : с

Замечание: Утверждения обратноме св-ву (3) не верны т е из делимости суммы на некоторое число не вытекает делимость слогаемых из делимости произведения - делимость сомножителей.

4. 1) a: c и b не : c => a+b не : c

2) ( для любых а принадлежащих Z) ( (o:a) и (a:1))

3) ( для любых а не= 0) не существует ( g принадлежит z) (0*q=a)

5. Если a:b => |a| >=|b|

Следствие : 5,1 Если a:b и b:a => |a|=|b|

Кроме того делимость нацело рассм деление с остатком


2 . Теорема о делении с остатком

ОПР Разделить целое число а на целое число b не =0, с остатком осзаначет найти 2 таких целых числа q и r , что выполняется 2 усл 1) a=bg+r 2) 0=r- остаток от деления q - полным (a:b) или неполным часным

Возникает задача 0 возможность деления с остатком и его однозначности на Z Такую задучу решает теорема о делении с остатком

Теорема: каковы бы небыли два целых числка а и b не равные 0, всегда возможно и при этом единственным способом разделить a на b с остатком

Док-во:1)докажем вначале возможность деления с остатком,т.е. сущ-ние для люблых а,b не равных нулю и пренадлежащих Z, такой пары целых чисел q и r,что вып усл:a=b*q+r(1), 0<=r<=|b|(2).рассм 2 логич возможных случая.

1.а-любое,b>0.Рассм мн-во всех чисел кратных b:b*(-1),b*0,b*1...Среди таких чисел всегда найдется наим кратное b,но непревосход а.Обозначим егоb*q<=a.aнер-ву 0<=a-b*q<=b (4).Введем обознач:a-b*q=r, таким образом => a=b*q+r, 0<=r<=b.итак в случае 1 теорема верна.

2.a-любое,b<0.=> (-b)>0.и тогда по случаю 1 деление с остатком а на(-b) возможно.т.е. a=(-b)*q1+r, 0<=r<=(-b) (5).рав-во (5) запишем ввиде . a=b*(-q1)+r. т.е. a=b*q+r.в случае 2 теорема верна.теорема о существовании доказана.

2)докажем единственность деления с остатком.

примеры


12 на 5: 12=5*2+2

q=2 r=2
3. Понятие идеала кольца целых чисел.Примеры



Опр: непустое мн- во K наз-ся кольцом если на этом мн-ве определены 2 бинар. алг. опер.( умножение) ( сложение), причём вып след аксиомы

1) относительно орп "+" мн-во К яв-ся абелевой группой

2)(умножение) ассоциативно те (для любых а и b принадлежащий К) (a*(b*c) = (a*b)*c)

3) Обе операции связаны левым и правым дистриб законами



Опр:непустое мн-во I целых чисел наз-ся идеалом кольца Z если вып след усл

1) I замкнуто относительно + ( для любого a и b принадлежащего I => что a + b тоже принадлежит I)

2) I замкнуто относительно операции * на любое целое число(для любого а пренадлежащего I )любого к принадлежащего Z => k*a принадлежит Z

простейшие св-ва идеалов

1) идеал I кольца Z замкнуто относительно операции вычитания

Док-во действительно, если а,b пренадлежит I => (-1)*b= -bпринадлежащее I =>a+(-b)=a-b принадлежащая I

2)Каждый идеал содержит 0

док-во а принадлежит I =>( св 1 a-a=0 принадлежит I)



3)Идеал кольца целых чисел замкнуто относительно(умножения)( a,bпринадлежит I => a*bпринадлежит I для любого а и b принадлежавшего I)

док-во вытекает непостедственно из усл 2 из опр идеала



Примеры идеала

1)2Z -мн-во всех чётных чисел такое мн-во замкнуто относиетельно опер-и сложения и умножения на любое целое число. сумма чётных чисел есть число чётное, и произведение любого целого на чётное есть число чётное. Итак идиал кольца Z - 2Z

2) I = {0} - любой идеал кольца целых чисел
4. Главные идеалы кольца Z

Опр:непустое мн-во I целых чисел наз-ся идеалом кольца Z если вып след усл

1) I замкнуто относительно + ( для любого a и b принадлежащего I => что a + b тоже принадлежит I)

2) I замкнуто относительно операции * на любое целое число(для любого а пренадлежащего I )любого к принадлежащего Z => k*a принадлежит Z

Теорема 1 :каждый идеал кольца целых чисел явл-ся главным. Если I не нулевой идеал и d наим целое положительное число,содержащиеся в I, то I = d*Z , т е

идеал состоит из всех целых чисел кратных d



Док-во :Очевидно что нулевой идеал явл-ся главным,предположим что I не нулевой, тогда I содержит число а и а не равно 0 => по второму требованию опр идеала (-1)*а=-а преданлежащая I , таким образом мы получили что а или (-а) положительное и по-этому мы можем заключить что в подмн-ве I содержиться положит целые числа, но среди всех полож-х чисел в I мы можем выбрать наименьшее. Пусть для определённости таким числом будет d. теперь если мы докажим что I=d*z(1) то мы покажем что каждый идеал кольца явл-ся главным . Согласно выбору d принадлежит I, тогда по условию 2 опр идеала все числа кратные d попадают в I , => dZ включается в I (2) Докажем обратное включение те что I включаеться в dZ (3) для этого возьмём произвольный элемент из I , пусть этот элемент с принадлежащее Z. Мы можем считать без ограницения общности что с положительное число. Докажем что с кратное d. для этого раздделим с на d с остатком, получим:

с=d*q+r, d>r>=0(4) ( по теор-ме деления с остатком) q, r принадлежат Z, dпринадлежит I => d*q принадлежит I и с принадлежит I, тогда по св=ву 1 идеалов разность с-d*q=r принадлежит I

r принадлежит I r>= 0. предположим r строго больше 0 => r принадлежит I r>0 r0 невозможен => r=0.
5. Протые и составные числа и их св-ва

Опр1 Целое число а отличное от 0 и +\-1 наз-ся простым,если кроме делителей +\-1 и +\-а других делителей оно не имеет

Опр2 Целое число а отличное от 0 и +\-1 наз-ся составным, если кроме делителей +\-1 и +\-а оно имее другие делители

опр3 Целые числа а и b наз-ся взаимно простыми если их любой общий делитель любо +1 либо -1

Лемма 1 : Если числа а и b взаимно просты то сущ-т такие целые числа u и v принадлежащие Z что а*u+b*v=1

Лемма 2: Если произведение двух целых чисел делиться на простое число, то по крайней мере один из сомножителей делиться на это число

Лемма 3: Если произведение неск-х целых чисел делиться на простое число p, то по крайней мере делиться на p

Док-во Док-во проведём с помощую ММИ по числу сомножителей

1 база индукции: для n =2 лемма верна по лемме 2

2 предположим что утверждение верно для к сомножитей т е если a1a2...ak :p( нацело), то сущ-т i ai :p(нацело) i принадлежит {1,2....k}, исходя из предположения покажем что утверждение равное для к+1 рассмотрим a1*a2*...*akk+1 =( a1a2...ak) аk+1

а) ак+1 :p( нацело)- лемма верна

б) ак+1 не :p( нацело), но тогда из того что a1*a2*...*akk+1 делиться нацело на р => а1...ак делиться нацело, но по индексеонному предположению среди к сомножителей найдётся который делиться на р. т е сущ i такое что аі:p, i принадлежит {1,2....k}

таким образом в кождом из случаем лемма для к+1 верна. => по принципу МИ лемма верна для любого n принадлежащего N числа сомножителя


6. Основная теорема арифметики

Т. Каждое нат. число >1 представимо в виде произведения простых чисел, причем такое представление единственно с точностью до порядка следования сомножителей.

Д-во. 1.Сущ-ние. Если число а является простым, то в этом случае представление в виде произведения очевидно. Предположим теперь, что т-ма сущ-ния верна для всех чисел <а. Если а простое, то т. сущ-ния верна. Предположим, что а составное число. Тогда а можно представить как а=а12 , причем а1< а2 и а21=р12*…*рк, а2k+1*pk+2*…*pn , причём рi – простые числа.

Сл-но ввиду р-ва а= а12 = р12*…*рn т.о. исходя из индукционного предположения мы доказали сущ-ние разложения для самого числа а. Согласно ПМИ т. верна для любого нат числа.

2. Единственность разложения. Применим ПМИ. Если число а – простое, то то единст. Разл-ния очевидна.

Предположим теперь, что представление в виде простых чисел ед-но для всех целых чисел < а. Исходя из этого мы докажем, что такое представление единственно для самого числа а. По первой части число а можно представить в виде произведения простых чисел. Пусть мы имеем два различных представления а= р12*…*рn (1) и а= а1* а2*…* аn (2), сравнивая (1) и (2) получаем р12*…*рn = а1* а2*…* аn (3). Причем рi – простые числа для любых i из {1,2,…,n} aj – простые числа для любых j из {1,2,…,n}, сл-но в видур-ва (3) произведение а1* а2*…* аn делится на р1, поскольку по л3. мы заключили, что по крайней мере один из сомножителей а1* а2*…* аn дел-ся на а1. В кач-ве такого сомн-ля мы м-м взять q1 , оба числа р1 и q1 простые, поэтому это возможно тогда, когда р1 = q1 (4). Учитывая (4) мы м-м разделить обе части на р1.

Р23*…*рn = а2* а3*…* аn (левая и правая часть <а). Т.о. единственность верна по индукции. Предположим для всех чисел <а, то мы заключаем, что р2=q2, р3=q3, m=n,…, рm=qn, (6). Из р-в (4) и (6) мы получаем единственность разл-ния на простые мн-ли числа а. Согласно ПМИ т. верна для любого нат числа.
7. Бесконечность мн-ва простых чисел

Т.2 (Евклида) Мн-во положительных простых чисел бесконечно.

Д-во. Предположим от противного, что мн-во всех простых чисел конечно. Пусть это будет р12*…*рn , рi – прост. число. Составим число а=р12*…*рn+1 (1), тогда по осн. Т. арифметики число а разлагается в произведение простых чисел, т.е. найдется такое простое число, что а будет делиться на р, но такое число будет находиться среди мн-ва простых чисел р принадлежит { р12,…,рn }, так как согласно предположению мы взяли все простые числа, сл-но р12*…*рn дел-ся на р, т.о. число а дел-ся на р.

р12*…*рn дел-ся на р, сл-но по св-ву отн-ния дел-ти мы получили а-р12*…*рn =1дел-ся на р. 1 дел-ся на р, сл-но р=1, это противоречит опр-нию простого числа. Получаем противоречие, сл-но из неверного предположения о том, что мн-во полож. простых чисел конечно остаётся признать, что такое мн-во бесконечно.


8. Решето Эратосфена

Т.3. Положительное составное число а имеет по крайней мере один положительный простой делитель, не превосходящий корня кв-го из а.

Д-во. Пусть р не равно 1 – наим. полож-ный делитель целого числа а. Предположим, что р – сост-ное число, тогда р будет иметь простой делитель а, что 12<=>a=p2=>p не превосходит корня кв-го из а. ч.т.д.

Следствие. Если положительное число а, отличное от 1, не делится ни на одно простое число, не превосходящее корня из а, то оно простое.

Сущность метода

Пусть требуется найти все положительные простые числа, не превосходящие данного натурального числа а.

Для этого мы выписываем последовательность натуральных чисел от 2 до а: 2,3,4,5,…,а в этой посл-ти вычтем каждое второе число после 2, каждое третье после 3(причем считают и те числа, которые вычеркнуты ранее), первое не вычеркнутое за тремя простое число 5, поэтому мы вычеркиваем каждое 5-е число после пяти и т.д. Такое вычеркивание мы продолжаем до тех пор, пока не дойдем до первого простого числа, меньшего корня кв-го уз а. В силу следствия все числа, оставшиеся не вычеркнутыми, будут простыми не превосходящими а.
9. Число и сумма натуральных делителей

Лемма. Пусть n=* (1) – каноническое разложение нат-го числа n на простые мн-ли. Тогда каждый натуральный делитель d числа n имеет вид (2) d=*, где   

Д-во. Пусть d – некоторый делитель числа n , т.е. d|n, т.к. каждый простой делитель числа d явл-ся делителем числа n, то ввиду р-ва (1) в разложении d на простые мн-ли входят числа из мн-ва { р12,…,рs } поэтому число d представимо в виде (2) и показатели принадлежат {0,1,…,аi} для i=1,..,s.

Обратно, если d представимо в виде (2) , то число n=d(*) причем  для i=1,..,s это означает, что d – нат делитель числа n. Ч.т.д.



Т.3 Пусть n=* –каноническое разложение на простые мн-ли нат-го числа n. Тогда справедливы следующие утверждения:

1)число натуральных делителей числа n опр-ся формулой *; 2) Сумма всех натуральных делителей числа n опр-ся формулой 

Д-во. 1) По предыдущей лемме любой натуральный делитель d числа n имеет вид d=*, причём   для  найти число всех натуральных делителей числа n можно посчитать число всевозможных упорядоченных наборов  которые удовлетворяют условию (*) могут принимать  значений, причем выбор значений  не зависит один от другого, так как по основной теореме арифметики разложение на простые мн-ли единственно, то различным наборам соответствуют различные делители числа n. Поэтому их общее число опр-ся умножением ()*…*(

2) Составим произведение (1) (1+)*( 1+)*…*( 1+ если раскрыть скобки в произведении (1) то мы получим сумму вида (2)  Каждое из слагаемых в сумме(1) встречается в точности один раз. Причем по предыдущей лемме мы имеем, что каждый натуральный делитель числа n имеет вид * поэтому сумма (2) представляет сумму всех натуральных делителей числа n, т.е. лучено из (1) =(2)=(1)= (1+)*( 1+) (3) в каждой из скобок предст. собой сумму членов геометрической прогрессии. Поэтому из (3) мы получаем, что  ч.т.д.


10.НОД

Опр:Целое число с наз ОД целых чисел а1, а2…аn, если с является делителем каждого из этих чисел.

Опр:НОД целых чисел а1, а2…аn наз.такой их ОД который делится на любой ОД этих чисел.

Непосредственно из опр.Нод вытекают сле. Его св-ва:



1.d=НОД(а1, а2…аn), то мн-во всех ОД этих чисел совпадают с мн-вом всех делителей числа d.

2.Любых 2 НОД целых чисел а1, а2…аn , могут отличаться только знаком, т.е. если d=НОД(а1, а2…аn), то -d=НОД(а1, а2…аn).

Лемма: Мн-во I явл.идеалом кольца Z.

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

  1. Покажем что оно замкнуто относительно опер «+» элементов.

Возьмем x,y € I =>x+y € I

x € I =>x= k1 a1+…+kn an

y € I=>y= k11 a1+…+kn1 an

x+y=( k1+ k11)a1 +…+( kn+ kn1)an , т.к. k1+ k11 ,…, kn+ kn1 € Z


11.Критерий НОД.

Т4: Для любого множества целых чисел а1, а2…аn сущ. НОД.Число d явл.НОД чисел а1, а2…аn титтк идеал порожденный числами (а1, а2…аn) совпадает с идалом порожденными числами d

Док-во:1) Если все числа =0, то равенство идеалов тривиально.Предположим что среди чисел а1, а2…аn есть числа не = 0.Построим мн-во целочисленных линейных комбинаций этих чисел I={ k1 a1+…+kn an| ki € Z }.В таком мн-ве есть числа не = 0, т.к. в это множество попадают все числа аi, I€{1,2…n}.Действительно аi € I,т.к. аi=0* а1+…1*аi+…+0*аn.По предыщей лемме мн-во I- идеал кольца Z, кроме того как мы установили I-ненулевой идеал, но по т1 каждый идеал кольца Z явл. главным.Следов. идеал I=(d), по опр.главного идеала, т.обр идеал I=dZ, т.е. он состоит из всех целых чисел, которые делятся на d, докажем что в этом случае d будет совпадать с НОД, т.к. I=dZ , то для любых i которое €{1,2…n}, числа аi:d(напомним, что аi:€ Z),с другой по опр.мн-ва I мы заключаем, что из того что d€ Z=> d= k1 a1+…+kn an.Из этого р-ва следует, что любой ОД чисел а1, а2…аn явл.также делителем числа d.Итак,нами установлено что d ОД чисел (а1, а2…аn) и кроме того любой другой ОД этих чисел делит d.Это означает что d= НОД(а1, а2…аn).

2)допісать



СЛ1: НОД d чисел а1, а2…аn в виде целочисленной лин.комбинации этих чисел, т.е. d= k1 a1+…+kn an |ki € Z, др. словами сущ. лин.представление НОД.Кроме того если сущ.среди чисел аi не=0, то |d|-наим полож.число, представимое в этом виде явл.кратным числа d.

СЛ2:Если число d представимо в виде целочисленной лин.комбинации чисел а1, а2…аn явл. ОД этих чисел, то d= НОД(а1, а2…аn).

Док-во:Пусть d= k1 a1+…+kn an |ki € Z.Возьмем Любой другой ОД целых чисел аi.Пусть им является число с , тогда по св-ву отн. делимости с|=d, т.о. по опр НОД, мы заключаем что d= НОД(а1, а2…аn)
скачать файл


следующая страница >>
Смотрите также:
1. Отношение делимости и его св-ва Опр
567.13kb.
Математика, 8 класс
51.08kb.
Практическая диагностика детской одаренности представляет собой чрезвычайно ответственный вид деятельности
621.27kb.
Памятка для родителей будущих первоклассников
60.7kb.
Памятка родителям первоклассника
15.76kb.
Рекомендации родителям первоклассников в период адаптации к школе
13.58kb.
Числовые ряды Числовая последовательность
140.11kb.
Определить отношение каждого
109.58kb.
Календарно-тематическое планирование 10а,б класс, алгебра
185.02kb.
Экологическая игра
86.79kb.
Тема «Поволжский экономический район»
55.17kb.
К политехническому институту у меня глубоко личное и нежное отношение. И дело не только в том, что я шесть лет своей юности провел в его стенах и получил диплом инженера физика
88.88kb.