Читайте также:
|
Як відомо, в кільці Z Цілих чисел визначені операції додавання, віднімання і множення, а дія ділення не завжди можлива. Тому виникає потреба визначити, при яких умовах цілі числа діляться одно на одне.
Подільність чисел – це певне відношення між числами, яке в Z+ має такі властивості: рефлексивність (а a), транзитивність ([ a b /\ b с ] => [ a с ])і антисиметричність ([ а b /\ b a => a =b ]). Будь - яке відношення, яке має властивості рефлексивності, транзитивності і антисиметричності, називається відношенням не строгого порядку. Отже, подільність чисел в Z + є відношенням не строгого порядку. Аналогічним відношенням частинної упорядкованості є, наприклад, відношення «≥» в кільці Z. Воно рефлексивне (а ≥ a), транзитивне [ а ≥ b /\ b ≥ с ] => [ а ≥ b ], антисиметричне (якщо а ≥ b і b ≥ a, то b ≥ a).
Між відношеннями подільності і ≥ в кільці 2 можна встановити і таку аналогію. Відношення а і b означає, що існує таке число с, при якому виконується рівність a = bс. Відношення а ≥ b, або a – b ≥ 0, означає, що існує таке число с ≥ 0, при якому a = b + с. Рівності а = bс і a = b + c, як бачимо, аналогічні.
Факт подільності двох чисел можна, звичайно, встановити за допомогою алгоритму ділення чисел з остачею. Проте для великих чисел це завдання досить складне. Тому бажано знайти зручні ознаки, за якими можна було б судити про подільність чисел, не виконуючи самого ділення. В цілому суть ознак подільності зводиться до того, що розгляд подільності деякого натурального числа а на натуральне число т замінюється розглядом подільності на число т іншого, меншого за а натурального числа b, яке можна знайти за деяким правилом, що визначається числовою функцією f (a), тобто b = f (a). При цьому числа а і b = f (а)є, як кажуть, рівноподільними на число m, тобто такі, які, одночасно діляться або одночасно не діляться на число m. І Часто вимагають, щоб вони були конгруентними за модулем m.
Одним із способів знаходження ознак подільності, основаних на конгруентності чисел, є так званий спосіб Паскаля. Нехай деяке натуральне число а при основі числення q має вигляд
а = рngn+ р n –1 gn –1 + ∙∙∙+ p 1 g + р 0 (1)
де коефіцієнти рk є натуральні числа, які задовольняють нерівності 0 ≤ рk< g. Позначимо через rk остачу від ділення числа g k на m, тобто g k≡ rk (mod m), і побудуємо число b = f (a) за таким правилом:
b = f (а) = рnrn+ р n –1 rn –1 + ∙∙∙ + p 1 r 1+ р 0 (2)
На основі властивості 9 a ≡ b (mod m). Оскільки b < a, то дістаємо таку ознаку Паскаля подільності чисел:
Якщо число b = рnrn+ рn –1 rn –1 +... + р 1 r 1+ р 0 ділиться на число т, то ділиться на нього і число a = рngn + рn –1 gn –1 +... + р 1 g + р 0
Якщо ж b на число т не ділиться, то не ділиться на т і число а.
За допомогою цієї загальної ознаки можна встановити зручні конкретні ознаки подільності чисел, записаних у звичайній для нас десятковій системі числення. У цій системі g = 10 і число а має вигляд:
a = pn ∙10 n + рn –1∙10 n –1+... + р 1∙10 + р 0 (3)
Коротко це можна записати так: a = рnрn –1∙∙∙ р 1 р 0
а) Ознака подільності на 2 і на 5.
Оскільки 10 k: 2 і 10 k: 5, то всі остачі rk від ділення 10 k на числа 2 і 5 дорівнюють нулю. Тому за формулою (2) число b = f (a) = р0. Отже, маємо таку ознаку:
Число а ділиться на 2 і на 5 тоді і тільки тоді, коли на них ділиться цифра одиниць числа а.
Приклад 1. Число а = 8574 ділиться на 2, бо 4 ділиться на 2. Число 8127 не ділиться на 5, бо 7 не ділиться на 5.
б) Ознака подільності на 3 і на 9.
Оскільки всі остачі rk від ділення 10 k на число 3 або 9 дорівнюють 1, то за
b = f (a) = pn + рn –1+... + р 1+ р 0.
Отже, маємо таку ознаку:
Число а ділиться на 3 (або на 9) тоді і тільки тоді, коли сума цифр, які його зображують, ділиться на 3 (або відповідно на 9).
Приклад 2. Число a = 5742 ділиться на 3, бо сума цифр b = 5 + 7 + 4 + 2 = 18 ділиться на 3.
в) Ознака подільності на 11. За модулем 11 маємо
102 k≡ 1 (mod 11), 102 k –1≡ –1 (mod 11).
Тому r 2 k = 1, r 2 k –1= –1, і, отже, за рівністю (2)
b = р 0– р 1+ р 2– р 3+ р 4– р 5+... = (р 0+ р 2+ р 4+...) – (р 1+ р 3+ р 5+...).
Враховуючи, що цифри р 2 k з парними індексами в числі а стоять на непарних місцях, можна сформулювати таку ознаку:
Число а ділиться на 11 тоді і тільки тоді, коли різниця між сумою цифр, які стоять на непарних місцях, і сумою цифр, які стоять на парних місцях, ділиться на 11.
Приклад 3. Число a = 53746 ділиться на 11, бо число b = (6 + 7 + 5) –(4 + 3)=18–7=11 ділиться на 11.
У системі числення з основою g = 102можна знайти зручні ознаки подільності на числа 4, 25, 50. Число а в цій системі можна записати так:
a = cs ∙100 s + с s –1∙100 s –1+ ∙∙∙+ c 1∙100 + с 0.
Порівнюючи це з (3), бачимо, що c 0= р 1∙10 + р 0= р 1 р 0, тобто є двоцифровим числом, яке зображується двома останніми цифрами числа а в десятковій системі числення.
Враховуючи, що a ≡ c 0(mod 100) і числа 100 k діляться на числа 4, 25, 50, дістаємо такі ознаки подільності:
Число a = рnрn –1... р 1 р 0 ділиться на 4 (або на 25 чи 50), якщо на 4 (або відповідно на 25 чи 50) ділиться двоцифрове число c 0= р 1 р 0, утворене двома останніми цифрами числа а, записаного в десятковій системі числення.
Ознаки подільності є цінними, якщо вони прості, зручні для користування. Проте більшість ознак, які можна вивести з ознаки Паскаля, є складними. Існує ряд зручних ознак подільності, які не випливають з загальної ознаку Паскаля, а зйайдені іншими способами. Наприклад, одну з ознак подільності на 7 можна сформулювати так:
Число a = 10а 1 + а 0 ділиться на 7 тоді і тільки тоді, коли ділиться на 7 число b = a 1– 2а 0.
Зазначимо, що на відміну від усіх попередніх ознак числа а і b тут рівноподільні на 7, а не, конгруентні між собою за модулем т = 7.
Існує ще одне цікава властивість в теорії конгруенцій:
Дата добавления: 2014-12-20; просмотров: 173 | Поможем написать вашу работу | Нарушение авторских прав |