Вибрані питання теорії чисел

Аналогічно, запис 35234 у шістковій системі числення повинен позначати число 4 + 3 • 6 + 2 • 62+ 5 • 63+ 3 • 64.

Одиниця кожного наступного розряду у п'ятірковій системі містить п'ять одиниць попереднього розряду, у шістковій — шість, у n-ковій — п одиниць.

Числа, записані у певній позиційній системі числення, називаються системними. Якщо система числення десяткова (звичайна), то числа називаються системними десятковими. Якщо система п'ятіркова — то системними п 'ятірковими і т. д. Зрештою, часто слово системні опускають і говорять просто про числа десяткові, п'ятіркові і т. д.

Спосіб переходу від будь-якої n-кової системи числення до десяткової випливає з прийнятих умовностей (тобто з означення).

Наприклад, оскільки

34125 = 2+1-5+4-52+3-5=482, то, провівши обчислення у правій частині цієї рівності, одержимо:

3412 =2 + 5+4-25+3- 125.

Зворотний перехід — від запису у десятковій системі до запису в іншій системі — дещо складніший.

Нехай, наприклад, десяткове число 586 треба подати у сімковій системі числення. Позначимо шуканий запис через . Тоді, згідно з прийнятим означенням: 586 = (*)

Другий, третій і четвертий доданки у правій частині цієї рівності діляться на 7. Отже, при діленні на 7 усього числа у правій частині отримаємо остачу d. Але ж ліва частина дорівнює правій, тому шукана цифра d дорівнює остачі від ділення даного числа 586 на 7, тобто d = 5. Оскільки 586 = 83-7 + 5, то, підставляючи цей результат в ліву частину рівності (*), отримаємо  
А якщо в лівій і правій частині відкинути одне і те саме число d = 5 і поділити обидві частини на 7, то матимемо нову рівність:

. (**)

Звідси, у такий самий спосіб, як і для d, шукаємо c. Це буде остача від ділення 83 на 7; тобто c = 6. А неповна частка 11 = b + а - 1. Знову ділимо ліву частину на 7 і знаходимо остачу: 4 = b. А для неповної частки отримаємо рівність: 1 =а

Таким чином, шуканий запис набуває вигляду 14657.

3. Приклади:

Задача 1. Від деякого двоцифрового числа відняли потроєну суму його цифр і одержали число, записане останньою цифрою. Знайти це двоцифрове число.

Розв’язання: позначимо шукане число через . Тоді число , а сума його цифр a+b. З умови задачі одержуємо рівняння , або після спрощення 7a=3b. Звідси . Отже, а ділиться на 3, ділиться на 7. Знаючи, що a i b – цифри, одразу отримаємо значення для b = 7. Для а також отримаємо єдине значення а = 3, бо при двох інших можливих значеннях ( 6 і 9) – число уже буде двозначним.

Задача 2. Запис числа починається цифрою 4. Якщо останню його цифру переставити на перше місце, то одержимо число, втричі менше від початкового. Знайти найменше натуральне число з такою властивістю.

Розв'язання. Зрозуміло, що шукане число не одноцифрове. Шукатимемо його спочатку серед двоцифрових чисел. Якщо позначимо це число через , то з умови задачі матимемо: , або

. Звідси , або . Остання рівність, очевидно, не справджується при жодному наборі значень цифр a, b, крім a=b=0 (бо 29 не ділиться на 7). Але двоцифрове число не може мати обох цифр, що дорівнюють 0. Отже, двоцифрових чисел з описаною в умові задачі властивістю немає. Шукатимемо далі трицифрові числа . За умовою задачі . Оскільки 299с ділиться на 7 лише при с=7, але тоді - не двоцифрове число, то трицифрових чисел з такою властивістю також не існує.  Продовжуючи так само пошук серед чотирицифрових та п’ятицифрових чисел, матимемо відповідно рівності:

   та

 з яких число  з шуканими властивостями так  само не визначається. Знаходимо  його тільки серед шестицифрових  чисел. Якщо - шукане число, то

. Звідси при . Отже, відповідне число

.

 

 

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

Означення. Число а ділиться на число b, якщо існує таке число c, що а = b*c. У цьому випадку кажуть також, що а ділиться націло на b, або що число b ділить число а без остачі, або що число b є дільником числа а, або, нарешті, що число а є кратним числу b.

Звернемо увагу, що оскільки а = b*c=c*b, то поряд з b дільником числа а є і число c.

Таким чином усі дільники даного числа розбиваються на пари.

Означення. Числа, які діляться націло на 2, називаються парними, а які не діляться на 2, — непарними.

Отже, парними є ті і тільки ті числа, які можна подати у вигляді 2к, де к — деяке натуральне число. Непарні числа можна подати у вигляді 2к-1.

Звичайно, поділити націло одне число на інше можна не завжди. Наприклад, число 20 націло не ділиться на 6. Справді, якби таке ділення було можливе, то при якомусь натуральному d справджувалася б рівність 20 = 6*d. Однак така рівність не справджується при значеннях d = 1; 2; 3; а при d = 4 добуток 6*d = 24 уже більший 20. Тому при d > 4 тим більше матимемо, що 6*d > 20 і, отже, рівність 20 = 6*d не може справджуватись при жодному натуральному d.

Неважко також довести, що менше число ніколи не ділиться націло на більше.

Але якщо ділення націло можливе, то його результат визначається однозначно. Дійсно, припустимо, що при діленні націло а на b можливі дві частки q1, та q2. Тоді а = b*q1,i а = b*q2. Отже, а-а =b* q1 - b*q2, звідки b(q1 – q2)=0. Відомо, що якщо добуток двох чисел дорівнює нулю, то принаймні одне з них — нуль. Але число b не нуль, тому q1 – q2= 0. А це й означає, що q1=q2.

Зауважимо, що будь-яке натуральне число п ділиться на 1 і на себе.

Означення. Натуральне число, більше одиниці, яке ділиться тільки на одиницю і на себе, називається простим. Натуральне число, яке має ще й інші дільники (крім одиниці і самого себе), називається складеним.

Складене число, отже, можна подати у вигляді добутку двох менших множників. Складеними є, наприклад, числа 6 = 2*3,

12 = 4*3 = 6*2. Зауважимо, що число 1, згідно з означенням, — ні просте, ні складене, а число 2 — єдине парне просте число.

Часто при розв'язуванні задач зручно мати на увазі, що якщо число

п — складене, то воно обов'язково має дільник, менший за .

Нагадаємо, що символом (читається "корінь квадратний з ен") в математиці позначається число, добуток якого самого на себе (інакше кажучи, квадрат якого) дорівнює п. Тобто

1. Властивості подільності суми, різниці і добутку натуральних чисел.

Властивість 1. Якщо числа а і b діляться на c, то їхня сума

а + b також ділиться на c

Доведення. Нехай кожне з чисел а, b ділиться на c. Тоді, згідно з означенням, існують такі натуральні числа q1 i q2, що а = q1*c і b=q2*c.  Тому , де число q=q1+q2 — також натуральне. Рівність а + b = q*c згідно з тим же означенням, означає, що число а + b ділиться на c. Властивість доведено.

Властивість 1 поширюється на довільну кількість доданків.

Властивість 2. Якщо числа а і b діляться на c і а > b, то різниця а - b також ділиться на c.

Доведення:  аналогічне до попереднього і випливає з рівності

.

Наcлідок. Якщо одне з чисел а, b та їхня сума а + b діляться на c, то й друге число також ділиться на с.

Справді, оскільки b = (а + b) - а, то за властивістю 2 число b ділиться на c.

  Властивість 3. Якщо а ділиться на c, а b ділиться на d, то добуток аb ділиться на добуток сd.

Доведення. Якщо а ділиться на c, а b на d, то а = q1*c, b=q2 *d, де q1   i q2 — деякі натуральні числа. Тоді — також деяке натуральне число. А це й означає, що ab ділиться cd.

Припускаючи, зокрема, що d=1 звідси отримуємо такий

Наслідок. Якщо а ділиться на с, то при будь-якому натуральному множнику b число аb ділиться на c.

Властивість 4. Якщо а ділиться на b, то для будь-якого натурального степеня п число аn ділиться на bn.

Доведення. Якщо а ділиться на b, то а = q*b, де q — натуральне число. Звідси— деяке інше натуральне число. А це й означає, що аn ділиться на bn, що й треба було довести

Властивість 5. Якщо а ділиться на добуток , то воно ділиться і на кожен зі співмножників

Доведення. Оскільки де числа - натуральні, то за означенням число a ділиться і на .

Властивість 6. Якщо ціле число a ділиться на цілі взаємно прості числа b1 і b2, то a ділиться і на їх добуток.

Доведення. Нехай . За умовою a ділиться на b2, а b1 взаємно просте з b2. Отже, згідно з твердженням 8, число c  ділиться на b2, тобто Тому що і треба було довести.

 

2. Приклади:

Задача 1. Число a + 2 ділиться на 5. Довести, що число За + 16 також ділиться на 5.

Розв'язання. Перетворимо вираз За + 16 наступним чином:

За + 16 = За + 6 + 10 = 3(а + 2) + 10.

За умовою число a + 2 ділиться на 5. Отже, ділиться на 5 і число 3(а + 2). Крім того, на 5 ділиться число 10. Отже, за властивістю про подільність суми, на 5 ділиться і сума 3(а + 2) + 10, тобто число За + 16, що й треба було довести.

Задача2. Кожнез чисел a + bі ab ділиться на с. Довести, що тоді a3+b3 ділиться на с2.

Розв'язання. Запишемо число a3 + b3 y вигляді:

а3 +b3 = (а + b)(а2 - ab + b2) = (а + b)*((а2 + b2) - аb) =

=(а + b)*((a+b)2-2ab-ab)= (а + b)*((a+b)2-3ab).

Оскільки a + b ділиться на с, то й (а + b)2 також ділиться на с. А врахувавши, що за умовою й ab ділиться на с, прийдемо до висновку, що множник ((a + b)2- Заb) ділиться на с. Тому добуток

(а +b)*((a+b)2-3ab) ділиться на добуток с*с, тобто на с2, що й треба було довести.

Задача 3. Дано п'ятицифрове число 25762. Яку цифру і на якому місці потрібно дописати, щоб одержати шестицифрове число, яке ділиться на 36?

Розв'язання. Для того, щоб число ділилося на 36, потрібно, аби

воно ділилося на 9 і на 4 (9 і 4 — взаємно прості числа). Перша умова вимагає, щоб сума цифр цього числа ділилася на 9. Сума цифр даного п'ятицифрового числа 22. 3 усіх можливих 10 цифр тільки одна цифра 5 доповнює цю суму до числа, кратного 9. Отже, потрібно дописати цифру5.

Для того, щоб число ділилося на 4, число, записане двома його останніми цифрами, повинно ділитися на 4. 3 останніх двох цифр даного числа утворюється число 62, яке на 4 не ділиться. Отже, дописувати цифру 5 треба біля останньої цифри, причому зліва від неї. Одержимо число 257652.

Відповідь. Потрібно дописати 5 перед останньою цифрою.

 

 

 

9. Ділення чисел з остачею

Оскільки в загальному випадку менше з двох заданих чисел а і b, (нехай b < а) не є дільником більшого (тобто а не ділиться націло на b), то природною є постановка проблеми про ділення націло числа а на якусь цілу частину числа b, тобто про ділення на дільник b1 числа b. Тоді число b1, буде спільним дільником чисел а і b.

Означення. Поділити з остачею число а на число b (а і b — натуральні числа) — означає знайти таке натуральне число c і таке ціле 0 < r < b, що

а = bq+r (*)

При цьому число c називається неповною часткою, а число r — остачею від ділення а на b. При r = 0 ділення з остачею є діленням націло.Доведемо, що для довільного числа а числа b i q визначаються однозначно. Припустимо, що разом з рівністю (*) можлива рівність такого ж вигляду при інших значеннях q і r:

Віднімаючи тоді цю рівність від рівності (*), матимемо:

  або .

А це означає, що різниця остач ділиться націло на b. Але кожне з чисел менше b. Тим більше, менша від b їхня різниця, отже, вона не може ділитися націло на b. Одержали протиріччя, тому зроблене припущення не правильне. Отже, результат ділення з остачею визначається однозначно, що й треба було довести.

Можливість і однозначність ділення з остачею має своїм наслідком наступний факт:

Будь-яке натуральне число а при довільно вибраному натуральному к>1 можна однозначно подати якоюсь однією з наступних к формул при належному виборі цілого невід 'ємного п:

а = кп; а = кп + 1; а = кп + 2; а = кп + (к- 1).

Це просто випливає з того, що остачею від ділення а на к може бути лише одне, яке-небудь з чисел 0, 1, 2, 3,..., k-1.

Вважаючи, наприклад, к = 2, матимемо такі дві форми натуральних чисел:

а = 1п (парні числа, діляться на 2 без остачі);

а = 2п+ 1 (непарні числа, при діленні на 2 дають остачу 1).

 

1. Приклади:

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

Розв'язання. Розглянемо спочатку конкретний приклад. Нехай a = 2, a b = 100, тобто розглядаються остачі від ділення на 100 чисел вигляду 2n.

Послідовність чисел 2n у межах до 100 має вигляд:

21 = 1; 22 = 4; 23 = 8; 24 = 16; 25 = 32; 26 = 64.

При діленні їх на 100 матимемо такі ж остачі r1. = 2, r2 = 4, r3 = 8, r4 = 16, r5 = 32,r6= 64.

Наступні остачі обчислюватимемо за встановленим правилом. Наприклад, оскільки

27 =26 *2, а відповідний добуток остач від ділення на 100 чисел 26 і 2 дорівнює 64 * 2 = 128, то остача r7 = 28. Таким чином одержимо: r7 = 28, r8= 56, r9 = 12, r10 =24, r11 = 48, r12 = 96, r13= 92, r14 = 84, r15 =68, r16 = 36, r17 = 72, r18 = 44, r19 = 88, r20 =76, r21 =52, r22=4…

Після остачі r22 = 4, яка дорівнює r2, усі наступні остачі повторюватимуться у тій же послідовності. Наприклад, r23= r22*2=8,

r24= r23*2=16. Повторення відбувається із періодом 20.

Тепер доведемо твердження задачі в загальному випадку. Усіх можливих остач при діленні на число b існує b штук: 0, 1, 2, 3,..., b - 1, отже, скінченне число. Тому при діленні достатньо великої кількості чисел серед остач обов'язково знайдуться співпадаючі. Нехай у послідовності остач r1, r2, r3…, що одержується при діленні чисел аn на b, rк і rn — перші, які співпали між собою. Покажемо, що тоді rк+1= Це й означатиме, що обумовлена періодичність існує, причому починається з rк. Справді, остача rn+1 визначається з добутку остач rп *r = rк* r1, тобто дорівнює rk+1. Доведення завершено.