Подільність цілих чисел

Міністерство освіти і науки України

Національний університет водного користування та природокористування

Навчально-науковий інститут автоматики, кібернетики та обчислювальної техніки

Кафедра вищої математики

Реферат на тему:

«Подільність цілих чисел»

Виконав:                                                        Прийняв:

Стрілець Павло Миколайович,                         Професор, к. ф.-м. н., д. п. н.

студент групи ПМ-11                                        Тадеєв Петро Олександрович

Рівне-2019

Зміст

1.Подільність з остачею………………………………………………….…….2

2. Подільність чисел та її властивості………………………………………...2

3. НСД і НСК двох чисел. Методи їх знаходження. Алгоритм Евкліда……6

4. Прості і складені числа……………………………………………………...8

5.Основна теорема арифметики……………………………………………….9

6. Решето Ератосфера…………………………………………………………10

7. Список використаних джерел……………………………………………..12

1.Подільність з остачею

Ділення одного натурального числа на інше ціле не завжди виконується. Тому розглядають більш загальну дію — ділення з остачею.

Поділити натуральне число a на натуральне число b з остачею — означає подати число a у вигляді , a=bq+r де q і r — невід’ємні цілі числа, причому 0≤r Число q при цьому називається неповною часткою, а число r — остачею від ділення a на b Наприклад, при діленні числа 27 на 6 неповна частка дорівнює 4, а остача 3: 27=6·4+3. Щоб знайти ділене при діленні з остачею, потрібно неповну частку помножити на дільник і до здобутого добутку додати остачу. Очевидно, що r=0 тоді і тільки тоді, коли b є дільником a. Ділення з остачею завжди виконується, про що свідчить наведена далі теорема.

Теорема 1 (про ділення з остачею)

Довільне ціле число a можна однозначно поділити з остачею на натуральне число b.

Доведення

Розглянемо арифметичну прогресію з різницею b:

…-3b, -2b, -b, 0, b, 2b, 3b, …

Тоді, існує таке натуральне число q, що qb≤a≤(q+1)b. Поклавши a-qb=r, отримаємо a=qb+r, 0≤ r. Для доведення однозначності припустимо, що існує інша пара чисел q1, r1 для якої виконуються ті самі умови: a=q1b+r1, 0≤r1. Спочатку покажемо, що r=r1. Припустимо, що це не так, і, наприклад, r1. Тоді 01. З іншого боку b(q-q1)=r-r1, тобто b є дільником r-r1, що неможливо, оскільки b>r-r1. Отже r=r1, і тому q=q1.

Приклад. Нехай a=16, b=3. Тоді 16=5·3+1.

Зрозуміло, що a⁝b тоді і тільки тоді, коли остача рівна нулю.

2. Подільність чисел та її властивості

2.1 Подільність на множині цілих  чисел.

Про довільні цілі числа а і b кажуть, що а знаходиться у подільності з b або що а ділиться на b (позначається а ⁝ b), якщо існує ціле число х, таке, що:

а = b · х: ∀ a, b ∈ N0, а ⁝ b ⇔ ∃ х ∈ N0 , a = b · x.

З означення відношення подільності випливають наступні властивості. 

1. Нуль ділиться на будь-яке ціле  число: ∀ a ∈ N0, 0 ⁝ a.