1632
правки
Изменения
м
'''Формула деления с остатком''': <tex>n = m\,k + r,</tex> где <tex>n\,</tex> — делимое, <tex>m\,</tex> — делитель, <tex>k\,</tex> — частное, <tex>r\,</tex> — остаток, причем <tex>0\leqslant r < b </tex>==Основная теорема арифметики===
:Любое {{Теорема|id=th666|statement=Каждое натуральное число можно представить <tex>n>1</tex> представляется в виде: <tex>n = 2p_1\,k + r,cdots p_k</tex> , где остаток <tex>rp_1,\ldots ,p_k</tex> — [[простые числа]], причём такое представление единственно с точностью до порядка следования сомножителей.|proof= '''Существование'''. Пусть <tex>0\,n</tex> или — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если <tex>r\,n</tex> = составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, <tex>1\,n</tex>тоже является произведением простых чисел. Противоречие.
:Любое число можно представить в виде: '''Единственность'''. Пусть <tex>n = 4\,k + r,</tex> — наименьшее натуральное число, где остаток разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть <tex>r\,p</tex> = — любой из сомножителей в любом из двух разложений. Если <tex>0\,p</tex> или входит и в другое разложение, мы можем сократить оба разложения на <tex>r\,p</tex> = и получить два разных разложения числа <tex>1\,dfrac{n}{p}</tex> или , что невозможно. А если <tex>r\,p</tex> = не входит в другое разложение, то одно из произведений делится на <tex>2\,p</tex> или <tex>r\,</tex> = <tex>3\а другое — не делится (как следствие из леммы Евклида, см. выше),</tex>что противоречит их равенству.}}
|proof=
Если <tex>1 \in A</tex>, то <tex>1</tex> и есть '''min'''. Иначе <tex>1 \notin A</tex>
Если <tex>2 \in A</tex>, то <tex>2</tex> и есть '''min'''. Иначе <tex>2 \notin A</tex>
<tex>P(n)</tex> — все элементы <tex>\leqslant n</tex> не лежат в <tex>A</tex> <tex>\Rightarrow</tex> <tex>P(1) ... P(n)</tex> — верно и <tex>P(n+1)</tex> — верно (т.к. он был бы '''min''') <tex>\Rightarrow</tex> в <tex>A</tex> ничего не лежит. Противоречие.
rollbackEdits.php mass rollback
==Определение натуральных чисел==
===Неформальное определение===
{{Определение
|definition=
'''Натура́льные чи́сла''' (англ. ''natural numbers'', естественные числа) — числа, возникающие естественным образом при счёте (как в смысле перечисления, так и в смысле исчисления).
}}
Существуют два подхода к определению натуральных чисел — числа, используемые при:
* '''перечислении (нумеровании) предметов''' (''первый'', ''второй'', ''третий''…) — подход, общепринятый в большинстве стран мира (в том числе и в России);
* '''обозначении количества предметов''' (''нет предметов'', ''один предмет'', ''два предмета''…). Принят в трудах Николя Бурбаки, где натуральные числа определяются как мощность конечных множеств.
Отрицательные и нецелые числа натуральными числами не являются.
Множество всех натуральных чисел принято обозначать знаком <tex>\mathbb{N}</tex>. Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся большее его натуральное число.
===Формальное определение===
Определить множество натуральных чисел позволяют '''аксиомы Пеано''' (англ. ''Peano axioms''):
{{Определение
|definition=
Множество <tex>\mathbb N</tex> будем называть '''множеством натуральных чисел''', если зафиксирован некоторый элемент <tex> 1\in\mathbb N</tex> (единица) и функция <tex>S\colon\mathbb N\to\mathbb N</tex> (функция следования) так, что выполнены следующие условия
# <tex>1\in\mathbb{N}</tex> (<tex>1</tex> является натуральным числом);
# Если <tex>x\in\mathbb{N}</tex>, то <tex>S(x)\in\mathbb{N}</tex> (Число, следующее за натуральным, также является натуральным);
# <tex>\nexists x\in\mathbb{N}\ (S(x) = 1)</tex> (<tex>1</tex> не следует ни за каким натуральным числом);
# Если <tex>S(b)=a</tex> и <tex>S(c)=a</tex>, тогда <tex>b=c</tex> (если натуральное число <tex>a</tex> непосредственно следует как за числом <tex>b</tex>, так и за числом <tex>c</tex>, то <tex>b=c</tex>);
# '''Аксиома индукции'''. Пусть <tex>P(n)</tex> — некоторый одноместный предикат, зависящий от параметра — натурального числа <tex>n</tex>. Тогда:
:: если <tex>P(1)</tex> и <tex>\forall n\;(P(n)\Rightarrow P(S(n)))</tex>, то <tex>\forall n\;P(n)</tex>
:: ('''Если''' некоторое высказывание <tex>P</tex> верно для <tex>n=1</tex> (''база индукции'') и для любого <tex>n</tex> при допущении, что верно <tex>P(n)</tex>, верно и <tex>P(n+1)</tex> ''(индукционное предположение)'', '''то''' <tex>P(n)</tex> верно для любых натуральных <tex>n</tex>).
}}
===Теоретико-множественное определение===
Согласно теории множеств, единственным объектом конструирования любых математических систем является множество.
Таким образом, и натуральные числа вводятся, исходя из понятия множества, по двум правилам:
* <tex>0=\varnothing</tex>
* <tex>S(n)=n\cup\left\{n\right\}</tex>
Числа, заданные таким образом, называются ординальными.
Первые несколько ординальных чисел и соответствующие им натуральные числа:
* <tex>0=\varnothing</tex>
* <tex>1=\left\{\varnothing\right\}</tex>
* <tex>2=\big\{\varnothing,\;\left\{\varnothing\right\}\big\}</tex>
* <tex>3=\Big\{\varnothing,\;\left\{\varnothing\right\},\;\big\{\varnothing,\;\left\{\varnothing\right\}\big\}\Big\}</tex>
Классы эквивалентности этих множеств относительно биекций также обозначают <tex>0, 1, 2, \dots.</tex>
Перечисленные аксиомы отражают наше интуитивные представления о «натуральном ряде».
==Операции над натуральными числами==
===Сложение===
Есть два способа определения суммы двух натуральных чисел <tex>a\ и\ b</tex>. Если натуральные числа определяют через мощность множества с конечным числом элементов (мощность множества — это количество элементов в нём), тогда целесообразно дать следующее определение суммы:
Пусть <tex>N(S)\ — </tex> мощность множества <tex>S</tex>. Возьмём два не пересекающихся множества <tex>A\</tex> и <tex>B,\</tex> причём <tex>N(A) = a</tex> и <tex>N(B) = b</tex>.
Тогда <tex>a + b</tex> можно определить как: <tex>N ( A ∪ B )</tex>.
Здесь, <tex>A ∪ B\ — </tex> это объединение множеств <tex>A\ и B\</tex>. В альтернативной версии этого определения множества <tex>A\ и\ B</tex> перекрываются и тогда в качестве суммы берётся их дизъюнктное объединение, механизм, который позволяет отделять общие элементы, вследствие чего эти элементы учитываются дважды.
Другое известное определение рекурсивно:
Пусть <tex>n+\ — </tex> следующее за <tex>n</tex> натуральное число, например <tex>0+ = 1, 1+ = 2.</tex> Пусть <tex>a + 0 = a</tex>. Тогда общая сумма определяется рекурсивно: <tex>a + (b+) = (a + b)+</tex>. Отсюда <tex>1 + 1 = 1 + 0+ = (1 + 0)+ = 1+ = 2</tex>.
===Умножение===
Воспользуемся определением натуральных чисел <tex>\mathbb{N}</tex> как классов эквивалентности конечных множеств. Обозначим классы эквивалентности конечных множеств <tex>C,\A,\B\</tex> порождённых биекциями, с помощью скобок: <tex>[C], [A], [B].</tex> Тогда арифметическая операция '''умножение''' определяется следующим образом:
<tex>[C] = [A] \cdot [B] = [A \times B];\</tex>
где: <tex>A \times B={(a,\ b) \mid a \in A,\ b \in B}\</tex> прямое произведение множеств — множество <tex>C,</tex> элементами которого являются упорядоченные пары <tex>(a,\ b)</tex> для всевозможных <tex>a \in A,\ b \in B</tex>. Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением.
===Вычитание===
Воспользуемся определением натуральных чисел <tex>\mathbb{N}</tex> как классов эквивалентности конечных множеств. Обозначим классы эквивалентности конечных множеств <tex>C , A , B</tex> порождённых биекциями, с помощью скобок: <tex>[C],\ [A],\ [B].</tex> Тогда арифметическая операция '''вычитание''' определяется следующим образом:
<tex>[C] = [A] − [B] = [A \backslash B];\</tex>
где <tex>A \backslash B = \{ C \in A \mid C \notin B \mid B \subset A \} —\ </tex>разность множеств. Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением.
==Деление чисел с остатком==
{{Определение
|definition=
Если [[Классы чисел#Определение натуральных чисел | натуральное число ]] <tex>n\,</tex> не делится на натуральное число <tex>m\,</tex>, т.е. не существует такого натурального числа <tex>k\,</tex> , что <tex>n = m\,cdot k,</tex> , то деление называется '''делением с остатком'''(англ. ''modulo operation'').}} '''Формула деления с остатком''': <tex>n = m \cdot k + r,</tex> где <tex>n\,</tex> — делимое, <tex>m\,</tex> — делитель, <tex>k\,</tex> — частное, <tex>r\,</tex> — остаток, причем <tex>0\leqslant r < b </tex> :Любое число можно представить в виде: <tex>n = 2 \cdot k + r</tex>, где остаток <tex>r\, = 0\,</tex> или <tex>r\, = 1\,</tex> :Любое число можно представить в виде: <tex>n = 4 \cdot k + r</tex>, где остаток <tex>r\ = 0\,</tex> или <tex>r\, = 1\,</tex> или <tex>r\, = 2\,</tex> или <tex>r\, = 3\,</tex> :Любое число можно представить в виде: <tex>n = m \cdot k + r</tex>, где остаток <tex>r\,</tex> принимает значения от <tex>0\,</tex> до <tex>(m-1)\,</tex> ==Основная теорема арифметики=====Лемма Евклида=== {{Лемма|id=th1|statement=Если простое число <tex>p</tex> делит без остатка произведение двух [[Классы чисел#Определение целых, рациональных, вещественных и комплексных чисел | целых чисел]] <tex>x\cdot y</tex>, то <tex>p</tex> делит <tex>x</tex> или <tex>y</tex>.|proof=Пусть <tex>x\cdot y</tex> делится на <tex>p</tex>, но <tex>x</tex> не делится на <tex>p</tex>. Тогда <tex>x</tex> и <tex>p</tex> — взаимно простые, следовательно, найдутся такие целые числа <tex>u</tex> и <tex>v</tex>, что: <tex>x\cdot u+p\cdot v=1</tex> ([[Наибольший общий делитель|соотношение Безу]]).Умножая обе части на <tex>y</tex>, получаем: <tex>(x\cdot y)\cdot u+p\cdot v\cdot y=y.</tex>Оба слагаемых левой части делятся на <tex>p</tex>, значит, и правая часть делится на <tex>p</tex>.
}}
[[Категория:Любое число можно представить в виде: <tex>n = m\,k + r,</tex> , где остаток <tex>r\,</tex> принимает значения от <tex>0\,</tex> до <tex>(m-1)\,</tex>Теория чисел]]
==Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел==
Для любого подмножества натурального ряда всегда существует минимум.
Т. е. <tex>\forall A \subset \mathbb N, A \ne \varnothing, \exists x \in A: \forall y \in A, x \leqslant y</tex>
}}
Из этой теоремы вытекает следующее утверждение, эквивалентное аксиоме математической индукции, но иногда более удобное при проведении доказательств.{{Утверждение|id=utv1|author=|about=|statement= Источники информации Если <tex>T(n)</tex> истинно при <tex>n =1,</tex> а из того, что оно истинно при всех <tex>n < k,</tex> следует, что оно истинно и при <tex>n =k,</tex> то <tex>T(n)</tex> истинно для всех натуральных значений <tex>n</tex>.* ”Математика: Справ|proof=Обозначим через <tex>A</tex> подмножество натуральных чисел, материалы: Кн. для учащихсякоторых <tex>T(n)</tex> ложно.— МЕсли это подмножество непусто, то оно содержит наименьшее число k.: ПросвещениеЭтим числом не может быть <tex>1</tex>, 1988так как по условию <tex>T(1)</tex> истинно.” Авторы: Гусев ВЗначит, <tex>k > 1</tex>. АНо поскольку <tex>k</tex> — наименьшее число, для которого <tex>T(n)</tex> ложно, то для всех <tex>n < k</tex> <tex>T(n)</tex> истинно, а тогда по условию теорем оно должно быть истинно и при <tex>n = k</tex>.Мы пришли к противоречию — одновременно оказалось, Мордкович Ачто <tex>T(k)</tex> истинно и ложно. ГСледовательно, предположение о том, что <tex>A</tex> не пустое множество, ложно. сЗначит, <tex>A</tex> — пустое множество, т. 12—13е.* [https:/нет натуральных чисел, для которых <tex>T(n)</rutex> ложно.wikipedia.orgЧто означает, что <tex>T(n)</wikitex> истинно для всех натуральных значений <tex>n</%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%BD%D0%B4%D1%83%D0%BA%D1%86%D0%B8%D1%8F/ Математическая индукция]tex>.}}
== См. также ==
*[[Математическая индукция | Математическая индукция]]
*[[Основная теорема арифметики | Основная теорема арифметики]]
== Источники информации ==
* ”Математика: Справ, материалы: Кн. для учащихся.— М.: Просвещение, 1988.” Авторы: Гусев В. А., Мордкович А. Г. с. 12—13.
* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%BD%D0%B4%D1%83%D0%BA%D1%86%D0%B8%D1%8F Математическая индукция]
[[Категория: Классы чисел]]
