Русская Википедия:Делимость

Дели́мость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.

Определение

Если для некоторого целого числа <math>a</math> и целого числа <math>b</math> существует такое целое число <math>q</math>, что <math>bq=a,</math> то говорят, что число <math>a</math> делится нацело на <math>b</math> или что <math>b</math> делит <math>a.</math>

При этом число <math>b</math> называется делителем числа <math>a</math>, делимое <math>a</math> будет кратным числа <math>b</math>, а число <math>q</math> называется частным от деления <math>a</math> на <math>b</math>.

Хотя свойство делимости определено на всём множестве целых чисел, обычно рассматривается лишь делимость натуральных чисел. В частности, функция количества делителей натурального числа подсчитывает лишь его положительные делители.

Обозначения

<math>a\,\vdots\, b</math> означаетШаблон:Sfn, что <math>a</math> делится на <math>b</math>, или что число <math>a</math> кратно числу <math>b</math>.

<math>b\mid a</math> означает, что <math>b</math> делит <math>a</math>, или, что то же самое: <math>b</math> — делитель <math>a</math>.

Связанные определения

У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.
У каждого натурального числа, большего <math>1</math>, есть хотя бы один простой делитель.
Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.
Используется также понятие тривиальных делителей: это само число и единица. Таким образом, простое число может быть определено как число, не имеющее никаких делителей, помимо тривиальных.
Вне зависимости от делимости целого числа <math>a</math> на целое число <math>b\ne 0</math>, число <math>a</math> всегда можно разделить на <math>b</math> с остатком, то есть представить в виде:
<math>a=b\,q + r,</math> где <math>0 \leqslant r < |b|</math>.

В этом соотношении число <math>q</math> называется неполным частным, а число <math>r</math> — остатком от деления <math>a</math> на <math>b</math>. Как частное, так и остаток определяются однозначно.

Число <math>a</math> делится нацело на <math>b</math> тогда и только тогда, когда остаток от деления <math>a</math> на <math>b</math> равен нулю.

Всякое число, делящее как <math>a</math>, так и <math>b</math>, называется их общим делителем; максимальное из таких чисел называется наибольшим общим делителем. У всякой пары целых чисел есть по крайней мере два общих делителя: <math>+1</math> и <math>-1</math>. Если других общих делителей нет, то эти числа называются взаимно простыми.
Два целых числа <math>a</math> и <math>b</math> называются равноделимыми на целое число <math>m</math>, если либо и <math>a</math>, и <math>b</math> делится на <math>m</math>, либо ни <math>a</math>, ни <math>b</math> не делится на него.
Говорят, что число <math>a</math> кратно числу <math>b</math>, если <math>a</math> делится на <math>b</math> без остатка. Если число <math>c</math> делится без остатка на числа <math>a</math> и <math>b</math>, то оно называется их общим кратным. Наименьшее такое натуральное <math>c</math> называется наименьшим общим кратным чисел <math>a</math> и <math>b</math>.

Свойства

Замечание: во всех формулах этого раздела предполагается, что <math>a,\,b,\,c</math> — целые числа.

Любое целое число является делителем нуля, и частное равно нулю:

<math>\quad0\,\vdots\,a.</math>

Любое целое число делится на единицу:

<math>\quad a\,\vdots\,1.</math>

На ноль делится только ноль:

<math>a\,\vdots\,0\quad\Rightarrow\quad a = 0</math>,

причём частное в этом случае не определено.

Единица делится только на единицу:

<math>1\,\vdots\,a\quad\Rightarrow\quad a = \pm 1.</math>

Для любого целого числа <math>a \ne 0</math> найдётся такое целое число <math>b \ne a,</math> для которого <math>b\,\vdots\,a.</math>

Если <math>a\,\vdots\,b</math> и <math>\left|b\right| > \left|a\right|,</math> то <math>a\,=\,0.</math> Отсюда же следует, что если <math>a\,\vdots\,b</math> и <math>a \ne 0</math> то <math>\left|a\right| \geqslant \left|b\right|.</math>

Для того чтобы <math>a\,\vdots\,b</math> необходимо и достаточно, чтобы <math>\left|a\right| \vdots \left|b\right|.</math>

Если <math>a_1\,\vdots\,b,\,a_2\,\vdots\,b,\,\dots,\,a_n\,\vdots\,b,</math> то <math>\left( a_1 + a_2 + \dots + a_n \right)\,\vdots\,b.</math>

Отношение делимости натуральных чисел является отношением нестрогого порядка и, в частности, оно:
- рефлексивно, то есть любое целое число делится на себя же: <math>\quad a\,\vdots\,a.</math>
- транзитивно, то есть если <math>a\,\vdots\,b</math> и <math>b\,\vdots\,c,</math> то <math>a\,\vdots\,c.</math>
- антисимметрично, то есть если <math>a\,\vdots\,b</math> и <math>b\,\vdots\,a,</math> то <math>a\,=\,b.</math>

В системе целых чисел выполняются только первые два из этих трёх свойств; например, <math>2\,\vdots-2</math> и <math>-2\,\vdots\,2,</math> но <math>2 \ne -2</math>. То есть отношение делимости целых чисел является только лишь предпорядком.

Число делителей

Шаблон:Main

Число положительных делителей натурального числа <math>n,</math> обычно обозначаемое <math>\tau(n),</math> является мультипликативной функцией, для неё верна асимптотическая формула Дирихле:

<math>\sum_{n=1}^N\tau(n)=N\ln N+(2\,\gamma-1)N+O\left(N^\theta\right).</math>

Здесь <math>\gamma</math> — постоянная Эйлера — Маскерони, а для <math>\theta</math> Дирихле получил значение <math>\frac{1}{2}.</math> Этот результат многократно улучшался, и в настоящее время наилучший известный результат <math>\theta=\frac{131}{416}</math> (получен в 2003 году Хаксли). Однако наименьшее значение <math>\theta</math>, при котором эта формула останется верной, неизвестно (доказано, что оно не меньше, чем <math>\frac{1}{4}</math>).^[1]^[2]^[3]

При этом средний делитель большого числа n в среднем растёт как <math>\frac{c_1 n}{\sqrt{\ln n}}</math>, что было обнаружено А. Карацубой^[4]. По компьютерным оценкам М. Королёва <math>c_1=\frac{1}{\pi}\prod_p \left(\frac{p^{3/2}}{\sqrt{p-1}} \ln\left(1+\frac{1}{p}\right)\right)\approx 0{,}7138067</math>.

Обобщения

Понятие делимости обобщается на произвольные кольца, например, целые гауссовы числа или кольцо многочленов.

См. также

Ссылки

Видео о делимости

Примечания

Шаблон:Примечания

Литература

Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
Шаблон:Книга
Шаблон:Книга

Внешние ссылки

Шаблон:Выбор языка Шаблон:Числа по характеристикам делимости

[1] Шаблон:Книга

[2] Шаблон:Книга

[3] Шаблон:MathWorld

[Arnold-4] Шаблон:Книга

[1]

[2]

[3]

[4]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:Делимость

Содержание