Делимость на себя и на 1

Date: 2015-10-07; view: 493.

О2.Натуральное число кроме 1, которое делится только на 1 и на самого себя , называется простым. Иначе составное.

2) транзитивность: ((a:b)ᴧ(b:c))(a:c)

Доказательство:

a:b Ǝq1 ϵZ|a=b*q1 a=c(q2*q1) a:c

b:c(≠0) Ǝq2 ϵZ|b=c*q2 q

3)Числа а и b делятся на с, то a+b,a-c,k*a(kϵZ) тоже делятся на с.

Доказательство:

a:c Ǝq1 ϵZ|a=c*q1 a+b=c*q1+c*q2=c*(q1+q2) (a+b):c

b:c Ǝq2 ϵZ|b=c*q2

4)Все слогаемые, за исключением одного , делится на с, это слогаемое тоже делится на с.

Доказательство: Пусть все слогаемые кроме с1:с.Равенство a1=b1+…+bm –a2-…-am. справо все слогаемые :с их сумма:с.

5)(a:b) (|a|≥|b|)

Доказательство:

a:b Ǝq ϵZ|a=b*q a≠0 q≠0,qϵZ |q|≥+1

|b|*|q|≥|b| |b*q|≥|b| |a|≥|b|

§ 2. Деление с остатком. Определение существования единственности.

Определение. Пусть a,b ∈ Z, b≠0, a⋮ b с остатком, если существует представление:

Частные случаи деления с остатком:
1) Если a=b и q=1, r=0: a=b∙1+0 ó a=b
2) Если a<b и q=0, r=a: a=b∙0+a ó a=0
3) Если a>b, то a=b∙q+r, r ∈ Z
0≤ r<|b|

Пример: ±257 разделить на ±23:

· 257=23∙11+4
23∙11=253
23∙12=276
23∙11<257<23∙12

· -257=23∙(-12)+19

· 257=-23∙(-11)+4

· -257=-23∙12+19

Теорема.Пусть a,b ∈ Z, b≠0, тогда существует единственная пара чисел q,p ∈ Z такая что то a=b∙q+r, 0≤ r<|b|

Доказательство: ►доказательство существования пары q, r (2 случая):

1) b>0 и рассмотрим последовательность чисел кратных b: …,-2b,-b,0,b,2b,3b,…

Находим такое q, что:
b∙q≤ a< b(q+1)
0≤a- b∙q<b

a = b∙q+( a- b∙q) => a= b∙q+r, 0≤r<b

r

2) b<0 (-b>0):
a=(-b)∙q + r
a=b∙(-q)+r, 0≤ r<|b| ◄
►доказательство единственности пары q, r:
Пусть существует два представления, одно представление уже построено (1): a= b∙q+r, 0≤r<|b|
и второе (2): a= b∙q₁+r₁, 0≤r₁<|b|. Докажем что q= q₁ и r= r₁:
Предположим r≠ r₁: вычтем из (1)-(2):
0=b∙(q- q₁)+(r- r₁) (3)
r- r₁=b∙(q- q₁)
(r-r₁)⋮b => (по свойству 5) |r-r₁|≥|b|, но с другой стороны из (1) и (2) =>|r-r₁|<|b|=> получили противоречие(!?), значит r=r₁ => из(3) 0=b∙( q- q₁), b≠0 => делим на b и получаем q- q₁=0 => q=q₁►

§3. НОД. Определение. Св-ва. Методы нахождения

О1. a,bϵZ, одно из них ≠0.ОД это число , которое является делителем a и b.Наибольшее из ОД –НОД.

О2. Если НОД(а,b)=1 то a и b взаимно простые.

Способы нахождения НОД:

1)Способ веделения мн-ва ОД и наибольшего числа НОД.

2) Способ разложения исходных чисел на простые множители.

3)Метод последовательного деления (Алгоритм Евклида).основан на Леммах:

-a:b ,b>o 1.Da,b=Db 2.НОД(a,b)=b

Доказательство:

dϵDa,b dϵDb : Da,b С Db dϵDb b:d,a:b a:bᴧb:d a:d dϵDa

значит dϵDa,b и DbϵDa,b НОД(a,b) наибольшее d в мн-ве Da,b из(1)

Da,b = Db следовательно d наиб.число Db делителей числа a само число b d=b.

-вып. Рав-во a=bq+r, тогда 1. Da,b=Db,r 2. НОД(a,b)=НОД(b,r)

Доказательство: 1) dϵDa,b; a=bq+r r:d dϵDb,r Da,b С Db,r ,dϵDb,r

A=bq+r; bq:d и r:d a:d,значит Db,r С Da,b Da,b=Db,r

2) Da,b=Db,r равны их наибольшие числа и НОД(a,b)=НОД(b,r)

ПРАВИЛО Чтобы найди НОД(a,b) делят большее из них на меньшее , потом меньшее на первый остаток. Затем первый на второй и т.д. пока остаток будет равен 0. Тогда последний не нулевой остаток это НОД

§4. Алгоритм Евклида

Для нахождения НОД(a,b) применяется Алгоритм Евклида:

· a⋮ b ( b>0) , то НОД(a,b)=b

· a не кратно b, то a= b∙q₁+r₁, 0<r₁<b=>НОД(a,b)=НОД(b,r₁)

ü b⋮r₁=> НОД(b,r₁)=r₁

ü b не кратно r₁ => НОД(a,b)=НОД(r₁,r₂)

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

Замечание: ( (a⋮c)⋀(b⋮c))ó (НОД(a,b) ⋮c)

Пример: Вычислить НОД(96,165):

165=96∙1+69

96=69∙1+27

69=27∙2+15

27=15∙1+12

15=12∙1+3

12=3∙4

НОД(96,165)=3

§5.Линейное представление НОД

Определение. Пусть d=НОД(a,b), u,v∈ Z выполняется равенство a∙u+b∙v=d – линейное представление d= lin(a,b)

Теорема. ( О линейном представлении НОД).

Если d=НОД(a,b), u,v∈ Z такие что выполняется равенство d=a∙u+b∙v

Доказательство:

►1) если a⋮b, то НОД(a,b)=b

d = a ∙ 0 + b ∙ 1

b u v

2) если a не кратно b, то нахождение линейного представления состоит из 2-ух этапов

1. Cпускаемся вниз с помощью алгоритма Евклида и находим НОД(a,b)=d

rn=d

2. Подъем вверх, выражение rₓ=d

rn=r n-2∙ 1 +rn-1∙(-qn)

u0 v0

rn=lin(r n-2, rn-1)

rn-1=lin(r n-3, rn-2)

rn=lin(r n-3, rn-2)

…

rn= a∙u+b∙v◄

Пример: Найти линейное представление НОД(96,165):

НОД(96,165)=3

3=15-12=15-(27-15)=2∙15-27=2∙(69-27∙2)-27=2∙69-5∙27=2∙69-5∙(96-69)=7∙69-5∙96=

=7∙(165-96)-5∙96=7∙165-12∙96=3

Теорема. ( Критерий взаимной простоты). Числа a и b взаимно просты тогда и только тогда, когда существует такие v,u ∈ Z что a∙u+b∙v=1

§6. Свойства НОД

1)a и bϵz.одно≠0 kϵN, тогда НОД(ka,kb)=k. НОД(a,b). K можно выносить за НОД

Доказательство:

Умножим рав-во из §4 на число к и получим:

Ka=(kb)q1+kr1, 0<kr1<kb

Kb=(kr2)q2+kr2, 0<k2<kr1

(1) ….

Krn-3=(krn-2)qn-1+krn-1 , 0< krn-1 <krn-2

Krn-2=(krn-1)qn-1+krn , 0< krn-1 <krn-2

Krn-1=(krn)qn+1 , 0< krn-1 <krn-2

Нер-во(1)-это признаки остатка в частном .первая строка показывает , что q1-частное, kr1-ост.от деления ka на kb.Значит (1) пос-ть Евклида для чисел ka, kb, НОД(ka,kb)=krn =k*НОД(a,b)

2)К- общий делитель a и b, тогда НОД(a/k,b/k)=НОД(a,b)/k

Доказательство: a1=ak,b1=b/k;a=a1k,b=b1k. НОД(a1,b1)=НОД(ka1,kb1)/k;НОД(ka1,kb1)=kНОД(a1,b1)-верно.

3)Если a и b разделить на их НОД, то получаться взаимно простые числа.

Доказательство: d=НОД(a,b) по свойству (2):

НОД(a/d,b/d)=НОД(a,b)/d=НОД(a,b)/НОД(a,b)

4)Пусть a*b делится на c НОД(a,c)=1, тогда b:c.

Доказательство: НОД(a,c)=1 Ǝu,vϵZ au+c*v=1(*b) bau+bcv=b

bau:c , bcv:c b:c

§7. НОК

О1.Нок a и b ≠0, наименьшее число ϵN, которое делится на a и b .

Теорема. a>0,b>0. a*b/НОД(a,b)=НОК[a,b]

Доказательство: получим сначало формулу для ОК и по ней выберем НОК

d:=НОД(a,b) a1:=a/d, b1:=bd a=a1d, b=b1d НОД(a1,b1)=1

m-OK a и b , тогда m=a1s=bt для st1ϵZ1 m=a1ds=b1dt;a1s=b1t

a1s:b1 s:b1 s=b1u , uϵZ , тогда m=as=a1ds=a1b1u=

НОД(a1,b1)=1 = a1db1d*u/d=ab*u/d

Т.е.любое ОК m чисел a и b имеет вид ab*u/d, uϵZ. Теперь нужно выбрать наименьшее ОК. С другой стороны любое число m=ab*u/d является ОК чисел a и b . ab*u/d=a*bu/d:a, поэтому формула для общих кратных a и b m=ab/НОД(a,b)*u , uϵZ. Наименьшее общее кратное получили при u=1, следовательно НОК[a,b]=ab/НОД(a,b).

Способы нахождения НОК:

-по средствам нахождения НОД

- по средствам разложения на простые множители.

§8. НОД и НОК нескольких чисел

Определение. НОД чисел a₁, a₂, …., aₓ не равных 0 называется наибольший из общих делителей этих чисел.

НОД(a₁, a₂, …., aₓ), (a₁, a₂, …., aₓ).