Определение Множество натуральных чисел

Определение 1. Множество натуральных чисел N определяется с использованием аксиом Пеана

1. 
   
   
2. 
   - последующее для
   
3. 
   
   
4. 
   
   
5. 
   Если некоторое подмножество является таким, что
   

Сложение:



должны выполняться законы:

1. 
   a+1=
   
2. 
   (a+b)+c=a+(b+c) – ассоциативность
   
3. 
   a+b=b+a – коммутативность
   
4. 
   Если a+b=a+c, то b=c
   

Умножение:
можно единственным образом сопоставить им произведение
a*b=(….(a+a)+…+a) - b раз

1. 
   a*1=a
   
2. 
   a* =ab+a
   
3. 
   (ab)c=a(bc)
   
4. 
   ab=ba
   
5. 
   (a+b)c=ac+bc
   
6. 
   Если ab=ac, то b=с
   

выполняется 1 из 3 транзитивных отношений: a>b, a<b, a=b
Определение 2. Множество Z целых чисел определяется как объединение множеств N, отрицательных N и нуля
Определение 3. Пусть над некоторым множеством R произвольной природы определены операции сложения и умножения. Множество R называется кольцом, если выполняются следующие условия:

1. 
   a+b=b+a
   
2. 
   
   
3. 
   
   
4. 
   
   
5. 
   
   

Определение 4. Если в кольце R умножение коммутативно (ab=ba), то кольцо R называется коммутативным

Определение 5. Если в кольце R умножение ассоциативно( (ab)c=a(bc)), то кольцо R называется ассоциативным

Определение 6. Если в кольце R существует единичный элемент e, такой что ae=ea=a, то R называется кольцом с единицей

Определение 7. Если в ассоциативном, коммутативном кольце R с единицей
то кольцо называется полем
Говорят, что целое число a делится нацело на целое число b>0, если существует целое число c, такое что a=bc. Число а называют кратным числа b, число b — делителем числа а, число с — частным от деления а на b.

Свойства деления:

1. 
   Нуль делится на любое целое число
   
2. 
   Если a₁ делится на b, a₂ делится на b, то а₁ ± а₁ делится на b
   
3. 
   Если a₁ ± a₂ делится на b и а₁ делится на и, то a₂ делится на b
   
4. 
   Любое целое число делится на 1
   
5. 
   Если a делится на b и b делится на c, то a делится на c
   
6. 
   Если 1 делится на a, то a=±1
   

Определение 1.5. Пусть числа а и b целые и b≠ 0. Разделить а на b с остатком — значит представить а в виде a=qb + r, где q,r Z и 0<r<|b|. Число q называется неполным частным, число r — остатком от деления а на b.

Теорема 1.1 (о делении с остатком). Для любых a,b Z, b≠0, существует единственная пара таких чисел q,r Z, что a = qb + r; 0<r<|b|.
Доказательство. Сначала докажем теорему для случая а ≥0, b > О,
N = {n N }.
Множество N «непусто» поскольку 0 Кроме того, для любого п N выполняется неравенство п≤ nb, а значит, п ≤ а. Таким образом, вес элементы множества N ограничены сверху числом а, и в множестве N существует наибольший элемент q. Но тогда qb ≤ а < (q + 1)b. Обозна­чим r = a-qb,тогда получаем требуемое неравенство для r:
0≤r = a-qb<(q + 1)b-qb = b.
Теперь найдем требуемую пару чисел q и r для а < 0, b >0. Со­гласно предыдущему случаю, для -а > 0 и b существуют целые числа такие, что -а = b + . При = 0 полагаем q = - , r = 0. При > 0 полагаем
q= -(q' + l), r=b-
При b < 0 нужно разделить с остатком а на |b| согласно одному из рассмотренных случаев: а = q'|b| + r, а затем положить q = -
Единственность докажем от противного. Пусть существуют две такие пары целых чисел q₁,r₁,q₂,r₂ что
a=q₁b + r₁ =q₂b + r₂,

где 0≤r₁ ,r₂ < |b|. Тогда

(q₁-q₂)b=-(r₁-r₂)

откуда следует

|q₁-q₂||b|=|r₁-r₂|<|b| , 0≤|q₁-q₂|<1
а так как числа q₁ и q₂ целые, то |q₁-q₂|=0 , q₁=q₂, r₂=r₁.


1.2. Наибольший общий делитель н наименьшее общее кратное
Определение 1.6. Целое число d≠0 называется наибольший общим делителем целых чисел а₁, а₂, ...,а_к (обозначается d = НОД(а₁, а₂, .... a_k)), если выполняются следующие условия:

1. 
   каждое из чисел а₁, a₂,.... a_k делится на d;
   
2. 
   если d₁≠ 0 — другой общий делитель чисел а₁, а₂,...a_k, то d делится на d₁
   

Ненулевые целые числа а и b называются ассоциированными (обо­значается а ~ b), если а делится на b и b делится на а.
Теорема 1.2 (об ассоциированных числах). Числа а и b ассоциированы тогда и только тогда, когда а = ±b.
Доказательство. Пусть а делится на b, тогда существует такое це­лое число с, что а=bс. Поскольку |c| ≥ 1, получаем |a|= |b|*|c|≥|b|*1=|b|, то есть |a|≥|b|
В то же время b делится на а. Проводя аналогичные выкладки, по­лучаем |b|≥ |а|. Таким образом, |a| = |b|, то есть а = ±b.
Теорема 1.3 (о единственности наибольшего обще­го делителя). Пусть числа a₁, а₂, .... a_k целые и d₁—их наибольший общий делитель. Целое число d₂ является наибольшим общим делителем чисел а₁, а₂,.... а_k тогда и только тогда, когда d₂ ~d₁.
Доказательство. Число d₁ — наибольший общий делитель чисел a₁, a₂… a_k, а d₂ — общий делитель этих чисел. Значит, по определению наибольшего общего делителя, d₁ делится на d₂. Точно так же, если рас­сматривать d₂ как наибольший общий делитель чисел a₁, a₂,…a_k, a d₁— как общий делитель этих чисел, то d₂ делится на d₁. Таким образом, d₁ ~ d₂. Необходимость доказана.
Теперь докажем достаточность. Пусть d₂ ~ d₁. Тогда, по определению наибольшего общего делителя, каждое из чисел а₁, а₂,... a_k делится на d_1. Кроме того, числа d₁ и d₂ ассоциированы, поэтому d₁ делится на d₂. Значит, каждое из чисел а_1, a₂, .... a_k делится на d₂. Таким образом, d₂ — общий делитель чисел а₁, а₂, ...,a_k. Покажем теперь, что он наибольший.
Пусть δ — некоторый общий делитель чисел а₁, а₂,...a_k. По условию d₁ = НОД(a₁, а₂ …a_k) , тогда d₁ делится на δ. А раз d₂ ~ d₁, то d₂ делится на d₁, значит d₂ делится на δ и d₂ = НОД(a₁, а₂, …a_k).
Учитывая теоремы 1.2, 1.3, далее для определенности наиболь­ший общий делитель целых чисел будем считать положительным чис­лом.

Теорема 1.4 (о существовании и линейном пред­ставлении наибольшего общего делителя). Для любых це­лых чисел а₁, а₂, .... a_k существует наибольший общий делитель d, и его можно представить в виде линейной комбинации этих чисел: d= c₁a₁ + c₂a₂ + ... + c_ka_k, где с_i Z.