Пункт 1. Ділення з остачею.

Цілі числа — {..., –3, –2, –1, 0, 1, 2 , 3,...}. У цій книжці буде вживатися досить стандартне позначення цієї множини — літера Z. Відомо, що щодо звичайних операцій додавання і множення, множина цілих чисел є кільцем, або Z є моногенним асоціативно-комутативним кільцем з одиницею. Підмножина {1, 2, 3, 4,...} множини цілих чисел називається множиною натуральних чисел і стандартно позначається буквою N.

Визначення. Нехай a , b Î Z. Число а ділиться на число b якщо знайдеться таке число q Î Z , що а = qb . Синоніми: а кратне b ; b — дільник а . Запис: а(3 вертикальні крапки AL) b чи b | a .

Легко помітити, що відношення подільності b | a є бінарним відношенням на множині Z, а якщо обмежитися розглядом тільки натуральних чисел, те нескладно установити, що на множині N це бінарне відношення є рефлексивним, антисиметричним і транзитивним, тобто відношенням часткового порядку. Легко перевіряється також наступна властивість:

Нехай а ₁+ а ₂+...+ а _n= c ₁+ c ₂+...+ c _k– рівність сум цілих чисел. Якщо всі доданки в цій рівності, крім одного, кратні b , то і доданок, що залишився, має бути кратним b .

Перераховані властивості відношення подільності дозволять нам довести основну теорему першого пункту:

Теорема . Для даного цілого відмінного від нуля числа b, усяке ціле число а єдиним чином представляється у виді а = bq + r , де 0 £ r < | b |.

Доказ. Зрозуміло, що одне представлення числа а рівністю а = bq + r ми одержимо, якщо візьмемо bq рівним найбільшому кратному числа b , що не перевищує а (див. рис. 1)

( a = 3b+r )

Рис. 1

Тоді, очевидно, 0 £ r < | b |. Доведемо одиничність такого представлення. Нехай а = bq + r і а = bq ₁+ r ₁— два таких представлення. Значить 0 = а – а = b ( q – q ₁) + ( r – r ₁). Тут 0 ділиться на b; b ( q – q₁) ділиться на b, отже ( r – r₁) мусить ділитися на b . Оскільки 0£ r<b і 0£ r₁<b , то r – r₁< b і r – r₁ділиться на b, значить r – r₁дорівнює нулю, а, значить і q — q₁дорівнює нулю, тобто два таких представлення збігаються.

Відразу після доказу теореми, поки не забулися позначення, що використовувалися в ньому, дамо

Визначення. Число q називається неповною часткою, а число r — залишком від ділення а на b.

Ідея малюнка 1, що пояснює доказ теореми, належить древнім грекам. Саме древні греки, чомусь, дуже любили багаторазово укладати один відрізок в інший, а частину більшого відрізка, що залишилася, природно, називали “залишком”.

Помітимо, що залишок — завжди є число невід’ємне, а от неповна частка може бути яким завгодно цілим числом. Тому на питання: “Скільки буде мінус п'ять поділити на три з залишком?”, кожний повинен відповідати: “Мінус два, у залишку — один!”.

Пункт 2. Найбільший спільний дільник.

Почнемо з визначення.

Визначення. Число d Î Z, що ділиться одночасно на числа а, b, c, ... , k Î Z, називається спільним дільником цих чисел. Найбільше d з такою властивістю називається найбільшим спільним дільником. Позначення: d = (a, b, c, ..., k).

Перелічимо, подекуди доводячи, основні властивості найбільшого спільного дільника.

Теорема (Властивість 1) . Якщо (a, b) = d, то знайдуться такі цілі числа u і v, що d=au+bv.

Доказ . Розглянемо множину P = { au + bv ç u,v Î Z }. Очевидно, що P Í Z , причому P – ідеал у Z. Очевидно, що a, b, 0 Î P. Нехай x, y Î P і y ¹ 0. Тоді залишок ділення x на y належить P. Дійсно:

x = yq + r, 0 £ r < y,

r = x – yq = (au₁+ bv₁) – (au₂+bv₂) q=a ( u₁– u₂q)+ b (v₁–v₂q) Î P.

Нехай d Î P - найменше додатне число з P (задумайтеся, чому таке існує!). Тоді а ділиться на d. Справді, a=dq+r₁, 0 £ r₁< d, a Î P, d Î P, значить r₁Î P, отже r₁=0. Аналогічно одержуємо, що b ділиться на d, отже d - спільний дільник a і b.

Оскільки d Î P, то d = au₀+ bv₀. Якщо тепер d₁- спільний дільник a і b, то d₁| (au₀+bv₀), тобто d₁| d. Значить d ³ d₁і d - найбільший спільний дільник.

Властивість 2 . Для будь-яких цілих чисел а і k справедливо: ( а , kа ) = а ; (1, а ) = 1.

Властивість 3 . Якщо a = bq + c , то сукупність спільних дільників a і b збігається із сукупністю спільних дільників b і c , зокрема,

( a , b ) = ( b , c ).

Доказ. Нехай d | a , d | b , тоді d | c . Нехай d | c , d | b , тоді d | a .

Проілюструємо цей доказ на давньогрецький лад. Подивіться на рис. 2:

Рис. 2

Якщо d ціле число разів укладається в а і в b , то, очевидно, що d мусить ціле число разів укластися й у с.

Властивість 4 . Нехай a , b і m - довільні цілі числа. Тоді

( am , bm ) = m ( a , b ).

Доказ. Якщо d - найбільший спільний дільник чисел а і b , то dm | am і dm | bm , тобто dm - дільник am і bm . Покажемо, що dm - найбільший спільний дільник цих чисел. Оскільки d - найбільший спільний дільник чисел а і b , то, відповідно до властивості 1, для деяких цілих чисел u і v виконується рівність d = au + bv. Помноживши цю рівність на m, одержимо:

dm = amu + bmv .

Видно, що якщо деяке число s ділиться одночасно на am і bm , то s має ділитися і на dm , тобто s £ dm , отже, dm - найбільший спільний дільник.

Властивість 5 . Нехай s - дільник а і b . Тоді:

(a/s,b/s)=(a,b)/s

Доказ .

(a,b)=(a/s*s,b/s*s)=s(a/s,b/s)

Властивість 6 . Очевидно тепер, що

(a/(a,b),b/(a,b))=1

Властивість 7 . Якщо ( a , b ) = 1, то ( ac , b ) = ( c , b ).