Класи еквівалентності та властивості конгруенцій

КЛАСИ  ЛИШКІВ  І   КОНГРУЕНЦІЇ

На множині натуральних чисел виконуються операції додавання і множення, але не завжди виконується операція віднімання. Розширюючи множину N так, щоб арифметична операція віднімання завжди виконувалася, ми отримаємо множину цілих чисел Z. Тому Z=N È {0, -1, -2,...} або множина цілих містить цілі від'ємні числа(перед від'ємними числами завжди ставлять знак «мінус», нуль(це число, яке немає знаку) та цілі додатні числа(перед додатніми числами ставлять знак плюс або іноді нічого не ставлять): Z={...-3, -2, -1, 0, 1, 2, 3,...}, тобто, множина цілих чисел Z містить множину натуральних чисел, число нуль та числа, які протилежні натуральним(цілі від'ємні числа).

Зауваження. Впровадження нуля та від'ємних цілих чисел здійснено з метою запровадження дії віднімання, оберненої до додавання, так, щоб ре­зультат був завжди визначений. Це не потребує нових аксіом і здій­снено таким чином: множину натуральних чисел можна розширити до декартового добутку самої на себе з подальшою факторизацією - роз­биттям на класи еквівалентності.

Властивості додавання, множення та відношення порядку для множини цілих чисел ті самі, що й для множини натуральних чисел.

Головну роль у всій теорії цілих чисел відіграють наступні властивості чисел(далі ці властивості чисел сформульовані як теореми).  Ми наводимо їх без доведення.

Т е о р е м а  про  ділення  з  остачею. Для будь-якого цілого а і b > 0 існує і  притому  єдині цілі q та  r, такі, що

а = bq + r,                  де  0 £  r < | b |.

Зауваження: Ціле  число а називають ділене, ціле число b називають дільником, ціле число q - неповною часткою(результат дії ділення), число r називають остачею від ділення а: b.

Зауваження: Якщо ціле число  а ділиться на ціле число  b націло тоді внаслідок ділення отримуємо ціле число, тбто, повну частку, або   остача від ділення а:b  рівна нулю). Тому із умови подільності а:b  націло слідує, що існує деяке ціле число  z  таке,  що  а= z∙b.  

Приклад: Дію ділення 7:2=3(ост. 1) можна записати у такому вигляді:

7 = 2∙3 + 1,

де число 7 називають ділене, число 2 називають дільником числа 7, число 3 - неповною часткою(результат дії ділення), число 1 називають остачею від ділення 7: 2.

При діленні цілого числа на 7 можна отримати  7 різних  остач, тобто, 0, 1, 2, 3, 4, 5, 6.

Взагалі, якщо довільне  ціле число поділити на  натуральне m, то можна отримати m-1 остачу, тобто  0,  1, 2, 3, 4, 5, 6, ..., m-1.  На основі цього можна множину  Z цілих чисел  можна розбити на m підмножин, які будемо позначати  Z_m (де m - ціле число, що змінюється від 0 до m-1). Розглянемо склад кожної такої підмножини:

Підмножина Z₀  складається з безлічі цілих чисел вигляду:

..., -3m, -2m, -m, 0, m, 2m, 3m, ...,

 - це числа, які діляться націло на m. Цю підмножину називають  класом нульових лишків за модулем m. Усі числа класу Z₀ задовольняють рівняння в цілих числах:

x º 0(mod m),

цей вираз читають так: «ікс дорівнює нулю за модулем m», а такий

вираз  прийнято називати конгруенцією за модулем m. Тобто,

-3m º 0(mod m),

-2m  º 0(mod m),

-m º0(mod m),

m  º 0(mod m),

2m  º 0(mod m),

і так далі.

Підмножина Z₁  складається з безлічі цілих чисел вигляду:

..., -3m+1, -2m+1, -m+1, 1, m+1, 2m+1, 3m+1, ...,

 - це числа, які при діленні  на m мають остачу(лишок) 1. Цю підмножину називають  класом одиничних лишків за модулем m. Усі числа класу Z₁ задовольняють рівняння в цілих числах:

x º 1(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m+1 º 1(mod m),

-2m+1  º 1(mod m),

-m+1 º1(mod m),

m+1  º 1(mod m),

2m+1  º 1(mod m),

і так далі.

Підмножина Z₂  складається з безлічі цілих чисел вигляду:

..., -3m+2, -2m+2, -m+2, 2, m+2, 2m+2, 3m+2, ...,

 - це числа, які при діленні  на m мають остачу(лишок) 2. Цю підмножину називають  класом двійкових лишків за модулем m.

Усі числа класу Z₂ задовольняють рівняння в цілих числах:

x º 2(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m+2 º 2(mod m),

-2m+2  º 2(mod m),

-m+2 º2(mod m),

m+2  º 2(mod m),

2m+2  º 2(mod m),

і так далі.

Підмножина Z₃  складається з безлічі цілих чисел вигляду:

..., -3m+3, -2m+3, -m+3, 3, m+3, 2m+3, 3m+3, ...,

 - це числа, які при діленні  на m мають остачу(лишок) 3. Цю підмножину називають  класом трійкових лишків за модулем m.

Усі числа класу Z₃ задовольняють рівняння в цілих числах:

x º 3(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m+3 º 3(mod m),

-2m+3  º 3(mod m),

-m+3 º3(mod m),

m+3  º 3(mod m),

2m+3  º 3(mod m),

і так далі.

Підмножина Z₄  складається з безлічі цілих чисел вигляду:

..., -3m+4, -2m+4, -m+4, 4, m+4, 2m+4, 3m+4, ...,

 - це числа, які при діленні  на m мають остачу(лишок) 4. Цю підмножину називають  класом четвіркових лишків за модулем m.

Усі числа класу Z₄ задовольняють рівняння в цілих числах:

x º 4(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m+4 º 4(mod m),

-2m+4  º 4(mod m),

-m+4 º4(mod m),

m+4  º 4(mod m),

2m+4  º 4(mod m),

і так далі.

Зрозуміло, продовжуючи так далі, ми згодом отримаємо останню підмножину.

Підмножина Z_m-1  складається з безлічі цілих чисел вигляду:

..., -2m-1, -m-1, -1, m-1, 2m-1, 3m-1, 4m-1, ...,

 - це числа, які при діленні  на m мають остачу(лишок) m-1. Цю підмножину називають  класом m-1-oкових лишків за модулем m.

Усі числа класу Z_m-1 задовольняють рівняння в цілих числах:

x º m-1(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m-1 º m-1(mod m),

-2m-1  º m-1(mod m),

-m-1 ºm-1(mod m),

-1  º m-1(mod m),

m-1  º m-1(mod m),

і так далі.

Досить часто в математичній літературі зустрічається термін «множина цілих чисел розбита на класи еквівалентності за модулем m», цей термін відповідає  такому змісту, «множина цілих чисел розбита на класи лишків за модулем m».

Наведемо приклади у вигляді таблиці 

1)Класи лишків за модулем 6.

Зверніть увагу на те, що в кожному стовпчику  наведеної таблиці знаходяться числа тільки одного класу лишків за модулем 6.

Зауваження. У двох класах лишків Z₁(сюди входять числа вигляду 6n+1), Z₅(сюди входять числа вигляду 6n+5) за модулем 6  знаходяться прості числа, окрім двох простих чисел 2 та 3. Але в усіх класах лишків за модулем 6   можна знайти  складені числа.

2)Класи лишків за модулем 5.

Зверніть увагу на те, що в кожному стовпчику  наведеної таблиці знаходяться числа тільки одного класу лишків за модулем 5.

Зауваження. В усіх класах лишків за модулем 5   можна знайти  складені та прості числа.

1)Класи лишків за модулем 5.

Дії над класами лишків

Над класами лишків виконуються дії додавання і множення.

Так як множина ціліих чисел  складається з  m класів лишків, представниками яких є лишки 0, 1, 2, 3, 4    ,...,m-1.

Додавання класів виконуємо так, що знаходимо суму k+n представників цих класів і потім знаходимо лишок від ділення k+n на m, тобто,

k+n º r(mod m),

Елемент r, де  0<r<m-1, є представником відповідного класу лишків за модулем m.

Приклад: Додамо два представники із класів лишків Z₂ та  Z₅ за модулем 6.

6n+2 + 6n+5 = 12n+7 = 6∙2n +6+1= 6(2n+1)+1 = 6k+1.

Отримали в сумі представників із класу лишків Z₁ за модулем 6.

Аналогічно виконуємо множення класів .

Добуток k∙n виконуємо так, що знаходимо добуток k∙n представників цих класів і потім знаходимо лишок від ділення k∙n на m, тобто

k∙n º s(mod m),

 знаходимо лишок s за модулем m .

Елемент 0<s<m-1 є представником одного з класів лишків за модулем m.

Приклад: Помножимо два представники із класів лишків Z₂ та  Z₅ за модулем 6.

(6n+2)(6n+5) = (6n+2)∙6n+(6n+2)∙5 = 36n²+ 12n+30n+10 =

= 36 n²+ 42n+10 = 6∙6n +6∙7n + 6 + 4= 6(6n²+7n+1) + 4 = 6k+4.

Отримали в добутку представників із класу лишків Z₄ за модулем 6.

Вправи для самостійного осмислення.

1. Утворити класи лишків за модулем 2:

•·         Знайти по одному найменшому від'ємному і додатному представнику з кожного класу;

_•·          Знайти представника класів Z₁   та Z₀;

•·         Виконати додавання та множення над представниками класу Z₁   та Z₀ і з'ясувати в якому класі знаходяться отримані сума та добуток.

•2.       Утворити класи лишків за модулем 3. Знайти по одному найменшому від'ємному і додатному представнику з кожного класу;

_•·          Знайти представника класів Z₁   та Z₂;

•·         Виконати додавання та множення над представниками класу Z₁   та Z₂ і з'ясувати в якому класі знаходяться отримані сума та добуток.

3. Утворити класи лишків за модулем 4.

•·         Знайти по одному найменшому від'ємному і додатному представнику з кожного класу;

_•·          Знайти представника класів Z₁   та Z₃;

•·         Виконати додавання та множення над представниками класу Z₂   та Z₃ і з'ясувати в якому класі знаходяться отримані сума та добуток.

4. Утворити класи лишків за модулем 7.

•·         Знайти по одному найменшому від'ємному і додатному представнику з кожного класу;

_•·          Знайти представника класів Z₃   та Z₆;

•·         Виконати додавання та множення над представниками класу Z₄   та Z₁ і з'ясувати в якому класі знаходяться отримані сума та добуток.

5. Утворити класи лишків за модулем 8.

•·         Знайти по одному найменшому від'ємному і додатному представнику з кожного класу;

_•·          Знайти представника класів Z₁   та Z₀;

•·         Виконати додавання та множення над представниками класу Z₁   та Z₀ і з'ясувати в якому класі знаходиться отримані сума та добуток.

6. Утворити класи лишків за модулем 9. Знайти по одному найменшому від'ємному і додатному представнику з кожного класу;

_•·          Знайти представника класів Z₁   та Z₇;

•·         Виконати додавання та множення над представниками класу Z₆   та Z₃ і з'ясувати в якому класі знаходиться отримані сума та добуток.

КОНГРУЕНТНІ ЧИСЛА ЗА МОДУЛЕМ m

ТА ЇХНІ ВЛАСТИВОСТІ.

Означення. Два цілих числа а і b називаються конгруентними за модулем m, якщо числа а і b при діленні на m дають однакові остачі.

Конгруентні числа за модулем m можна записати у вигляді:

a = mg+r, 

 b = mk+r,

де 0<r<m.

Модуль m є натуральним числом.

Конгруентність за модулем m чисел  a  та   b записуємо так:

а º b (mod m).

Конгруентність чисел а і b за модулем m рівнозначна:

а) рівності а = b+mk, де k=0, ± 1, ± 2, ... ;

б) подільності а-b на m; тобто, а-b ділиться націло на m.

Приклади конгруентних чисел за модулем 5

-7 º -2 (mod 5).

3 º 8 (mod 5).

13 º -12 (mod 5).

5 º 0 (mod 5).

Перевірити конгруентність за модулем 5 можна таким чином, відняти від лівої частини конгруенції -7 праву частину  конгруенції -2, тобто -7-(-2)=-5, це число ділиться націло на 5. Отже числа -7 та -2 є представниками одного класу лишків, а конкретно Z₃.

Приклади конгруентних чисел за модулем 7

6 º -1 (mod 7).

-4 º 3 (mod 7).

13 º 6 (mod 7).

7 º 0 (mod 7).

Властивості конгруентних чисел

1. Два цілих числа, які конгруентні третьому за модулем m, конгруентні між собою за цим самим модулем.

Якщо

а ºb (mod m),

с º b (mod m)

то

а º с (mod m).

Зауваження. У конгруенції будь-яке число можна замінити конгруентним йому.

Наприклад,

5 = 2 (mod 3),

5 = 8 (mod 3) .

Отже,

8 = 2 (mod 3).

2. Числа, конгруентні за модулем m, належать до одного й того самого класу чисел.

Отже, множину чисел розбиваємо на класи  Z_r за модулем m.
Всіх класів буде m Z₀, Z₁, Z₂, _{, ...,} Z_m-1.

3. Конгруенції за одним і тим самим модулем можна почленно додавати або віднімати. Наприклад,

а º b (mod m).

c º d (mod m).

а±c º b±d (mod m).

4. Конгруенції за одним і тим самим модулем можна почленно множити. Наприклад,

а º b (mod m).

c º d (mod m).

а∙c º b∙d (mod m).

5. Члени конгруенції можна переносити з однієї частини в другу, змінюючи їх знак на протилежний.

Якщо

а º b + с(mod m),

то також вірно

а-с º b (mod m),

або

а-b º с (mod m),

або

а - b- c º 0 (mod m).

6. До кожної з частин конгруенції можна додати (або відняти) число, кратне модулю.

Якщо

а º  b (mod m),

то

а + km º  b (mod m)

а º  b + km (mod m),

або

а - km º  b (mod m)

а º  b - km (mod m).

7. Обидві частини конгруенції можна помножити на одне й те саме ціле число.

Якщо

а º b (mod m),

то

аk º bk (mod m),

де k - ціле число.

•8.                  Обидві частини конгруенції можна піднести до одного й того самого степеня, показник якого є ціле невід'ємне число.

Якщо

 а º b (mod m),

то

а^k º b^k (mod m),

9.         Обидві частини конгруенції можна поділити на їх спільний дільник, якщо він взаємно простий з модулем m.

Якщо

а º b (mod m),

 НСД(k, m)=1, то

a:k º b:k (mod m),

10.       Обидві частини конгруенції і модуль можна помножити на одне й те саме натуральне число.

Якщо

а º b (mod m),

то

аk º bk (mod km),

11.       Обидві частини конгруенції і модуль можна поділити на будь-
який їх спільний дільник.

Якщо

а º b (mod m),

то

а:k º b:k (mod m:k),

12.       Якщо конгруенція має місце за модулем m, то вона матиме місце за будь-яким дільником k¹1 цього модуля.

а º b (mod m),

то

а º b (mod k),

13.  Якщо конгруенція має місце за кількома модулями, то вона матиме місце і за модулем, що дорівнює їх найменшому спільному кратному:  НСК (m;n) = k

Якщо

a º b (mod m),

а º b (mod n),

то

а º b (mod k).

14. Якщо одна частина конгруенції і модуль діляться на яке-небудь ціле число, то й друга частина конгруенції повинна ділитись на це число.

15. Якщо в многочлені f(х₁ х₂,..., х_n) від n цілих величин х₁ х₂,..., х_n з цілими коефіцієнтами ці величини і коефіцієнти замінити конгруентними з ними величинами і числами за модулем m, то в результаті дістанемо новий многочлен, конгруентний з попереднім за тим самим модулем m.

16. Китайська теорема про остачі. Якщо цілі числа m₁, m₂, m₃, m₄ , ... , m_{k ,} то для довільних цілих чисел а₁, а₂, а₃, а₄ , ... , а_k існує ціле число х, яке задовольняє умови х º а_і (mod m_і), де i=1,k,  При цьому число х можна вважати числом, яке належить довільному наперед заданому нівінтервалу довжиною, дорівнює добутку  m₁∙m₂∙m₃∙m₄∙ ... ∙m_k.

17. Теорема. Будь-яке натуральне число когруентне сумі своїх цифр у десятковій системі числення за модулем 9.

18. Теорема Ейлера. Функція кількості взаємно простих чисел для натурального числа n називається функцією Ейлера j(n), для неї виконується конгруенція

a^j(n)º1(mod n).

20. Теорема Ферма.  Для простого числа р виконується конгруенція

а^р-1º1(mod р)

або

а^рºа(mod р).

Задачі для самостійного осмислення.

1. Знайти остачу відділення 9⁴⁵+17 на 56.
2. Знайти остачу від ділення 7⁵⁰+3 на 43.
3. Знайти остачу від ділення 8¹⁰⁰+11¹⁰⁰ на 19.
4. Довести, що вираз 6⁵⁰+7²⁵ ділиться без остачі на 11.
5. Знайти останні три цифри числа 123⁴⁰².
6. Знайти останні дві цифри числа 3
7. Знайти останні дві цифри числа 4     .
8. Довести, що вираз 8¹⁶+8 ділиться без остачі на число 19.
9. Знайти останні дві цифри числа .

•10.          Довести, що вираз 4²⁰+4² ділиться без остачі на число 17.

•11.         Знайти таке а, при якому вираз 5²⁴+7а ділиться без остачі на число 23.

•12.         Знайти остачу від ділення 9⁹⁵+27 на 89.

•13.         Довести, що остача від ділення 3¹⁹+5⁴⁸ на 23 дорівнює 10.

•14.         Довести, що остача від ділення 7∙5⁶+21 на 29 дорівнює 8.

•15.         Довести, що остача від ділення 8∙12⁸+3 на 23 дорівнює 21.

•16.         Довести, що остача від ділення 9∙15¹¹+2 на 37 дорівнює 25.

      17. Довести, що остача відділення 17∙14⁹+5 на 45 дорівнює 33.

Зауваження. Нехай натуральне число m, більше 2. Зрозуміло, що різні цілі числа при ділення на m можуть давати довільні із остач: 1,2, 3,4, ..., m-1. Проте степені цілих чисел з фіксованим натуральним показником n>1 не обов'язково знову даватимуть при діленні на m будь-яку з цих остач.

Теорема  про остачі

 Квадратні лишки

Остачі при діленні квадратів на натуральні числа.

Якщо квадрат натурального числа, тобто,  m² = m∙m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1

4, то отримаємо остачі 0, 1;

5, то отримаємо остачі 0, 1, 4;

6, то отримаємо остачі 0, 1, 3, 4;

7, то отримаємо остачі  0, 1, 2, 4;

8, то отримаємо остачі  0, 1, 4;

9, то отримаємо остачі 0, 1, 4, 7;

10, то отримаємо остачі 0, 1, 4, 5, 6, 9;

11, то отримаємо остачі 0, 1, 3, 4, 5, 9;

12, то отримаємо остачі 0, 1, 4, 9;

13, то отримаємо остачі 0, 1, 3, 4, 9, 10, 12;

14, то отримаємо остачі 0, 1, 2, 4, 8, 9;

15, то отримаємо остачі 0, 1,4, 6,  9, 10;

16, то отримаємо остачі 0, 1, 4, 9;

17, то отримаємо остачі 0, 1, 4, 8, 9,15.

Кубічні лишки

Остачі при діленні кубів на натуральні числа.

Якщо куб натурального числа, тобто,  m³ = m∙m∙m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1, 2;

4, то отримаємо остачі 0, 1, 3;

5, то отримаємо остачі 0, 1, 2, 3, 4;

6, то отримаємо остачі 0, 1, 2, 3, 4, 5;

7, то отримаємо остачі  0, 1, 6;

8, то отримаємо остачі  0, 1, 3, 5, 7;

9, то отримаємо остачі  0, 1, 8;

10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9

Таблиця остач при діленні кубів на цифри

Четвіркові лишки

Остачі при діленні четвертих степенів на натуральні числа.

Якщо четверту степінь натурального числа, тобто,  m⁴ = m∙m∙m∙m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1

4, то отримаємо остачі 0, 1;

5, то отримаємо остачі 0, 1;

6, то отримаємо остачі 0, 1, 3, 4;

7, то отримаємо остачі  0, 1, 2, 4;

8, то отримаємо остачі  0, 1;

9, то отримаємо остачі 0, 1, 4, 7;

10, то отримаємо остачі 0, 1, 5, 6;

П'ятіркові лишки

Остачі при діленні п'ятих степенів на натуральні числа.

Якщо п'яту степінь натурального числа, тобто,  m⁵ = m∙m∙m∙m∙m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1, 2;

4, то отримаємо остачі 0, 1, 3;

5, то отримаємо остачі 0, 1, 2, 3, 4;

6, то отримаємо остачі 0, 1, 2, 3, 4, 5;

7, то отримаємо остачі  0, 1, 2, 3, 4, 5, 6;

8, то отримаємо остачі  0, 1, 3, 5, 7;

9, то отримаємо остачі  0, 1, 2, 4, 5, 7, 8;

10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9.

Розв'язування числових задач

 У цій таблиці наведено останні цифри натуральних чисел, квадратів, кубів, четвертих степенів і так далі.

Використовуємо цю таблицю для розв'язування задач.

Задача 1. Знайти остачу від ділення квадрата цілого числа на 5.

Розв'язання:

Квадрати натуральних чисел закінчуються цифрами: 0; 1; 4; 5; 6; 9.(колонка 2) то при їх діленні  на 5 одержуємо 0, 1 або 4.

Задача 2. Чи може число виду 1^k+5^m+6ⁿ, де k, m, n - довільні натуральні числа, бути довільним квадратом.

Розв'язання: Кожний доданок закінчується відповідно цифрами: 1, 5 і 6 (колонка 6) і тому їх сума закінчується цифрою 2, а таке число не може бути точним квадратом.

Задача 3. Довести, що число 53⁵³- 33³³ ділиться на 10.

Розв'язання: При виділенні показників степенів 53 і 33 на 4 в остачі одержуємо в кожному випадку 1. Отже, остання цифра числа 55⁵³ така сама, як числа 33³³, бо 53^4∙13+1 і 33^4∙8+1, отже, остання цифра різниці 0, і ця різниця ділиться на 10.

 Задача 4. Які остачі можуть мати точні квадрати при діленні на 3?

Відповідь: 0; 1; (3k±1)²=9k²±6k+1.    (3k)²=9k.

Задача 5. Які остачі не можуть мати точні квадрати при діленні на 4?

(2k)²=4k²

(2k+1)²=4k²+4k+1

Відповідь: 2; 3.

Задача 6. Які остачі не можуть мати точні квадрати при діленні на 5?

Відповідь:2 і 3. (5k)²=25k²+0

(5k±1)²=25k²±10k+1

(5k±2)²=25k²±20k+4

Задача 7. Довести, що при будь-якому цілому n число n(n-3)(n²-3n+14) ділиться на 24?

Доведення:

n (n-3)(n2-n-2n+2+12)=n(n-3)(n(n-1)-2(n-1)+12=n(n-3)(n-1)(n-2)+12n(n-3). Це число ділиться на 24, бо:

•1.       n(n-1)(n-2)(n-3) ділиться на 3і 8 Þділиться на 24.

•2.       12n(n-3) ділиться на 12 і 2, бо n(n-3)- просте число, отже, ділиться на 24.

•3.        

Властивості квадратних лишків

Теорема 1. Завжди знайдеться натуральний дільник  n, більшого 1,  для  довільного степеня натурального числа m^k, який при ділення степеня на цей дільник n дає остачу 1, (або завжди можна знайти такі  натуральні числа, що (m^k- 1):n - натуральне число).

Тобто рівняння з двома невідомими завжди має  розв'язки в натуральних числах

m^k - 1º0(mod m-1). 

Теорема 2. Завжди знайдеться натуральний дільник n, більший 5, для  довільного квадрату натурального числа, який при ділення квадрата на цей дільник дає остачу 4.

Тобто, рівняння з двома невідомими завжди має  розв'язки в натуральних числах

m² º4(mod m+2) або m² º4(mod m-2)  .

Теорема 3. Завжди знайдеться такий натуральний дільник n для  довільного квадрату натурального числа, який при ділення на цей натуральний дільник дає остачу 0.

Тобто рівняння з двома невідомими m i n завжди має  розв'язки в натуральних числах

m² º 0(mod n).

Теорема 4. Завжди знайдеться такий натуральний дільник n, більший 9,  для  довільного квадрату натурального числа, який при ділення на цей натуральний дільник n дає остачу 0.

Тобто рівняння з двома невідомими завжди має  розв'язки в натуральних числах

m² º9(mod n).

Тобто рівняння з двома невідомими m i n завжди має  розв'язки в натуральних числах

m² º9(mod m+3) або m² º9(mod m-3)  .

Задачі для самостійного осмислення

1. Рівняння з двома невідомими

m² º 3(mod n).

 має  розв'язки в цифрах тільки один розв'язок  m = 3, n = 6.

(Умова задачі на це рівняння. Знайти двоцифрове число, у якого квадрат цифри десятків при діленні на цифру одиниць дає остачу, що дорівнює половині цифри  одиниць. Відповідь: 36.)

2. Рівняння з двома невідомими

m² º2(mod n).

 має  розв'язки в цифрах тільки два розв'язки:  m = 3, n = 7. m = 4, n = 7.

(Умова задачі на це рівняння.  Знайти двоцифрові число, у яких  квадрат цифри десятків при діленні на цифру одиниць дає остачу 2. Відповідь: 37 та 47.)

3. Чи існує магічний квадрат 3х3 , складений з натуральних чисел так, щоб виконувалася умова на парність чисел? (У магічного квадрату суми чисел по двох діагоналях, трьох вертикалях та трьох горизонталях рівні).

Відповідь: існує, це магічний квадрат 3х3, з цифр 1, 2, 3, 4, 5, 6, 7, 8, 9.

4. Чи існує магічний квадрат 3х3, складений з натуральних чисел так, щоб виконувалася умова на парність чисел?(У магічного квадрату суми чисел по двох діагоналях, трьох вертикалях та трьох горизонталях рівні).

Відповідь: не існує.

•4. Чи існує така цифра, більша 1, яка ділиться на число вигляду m² - 8. Відповідь: не існує.

•5.  Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу 5. Відповідь: 58, 56.

•6.  Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу, що дорівнює цифрі одиниць, зменшеній на 1. Відповідь: 12, 32, 52, 72, 92. 23, 53, 83, 34, 74, 45, 56, 57, 78,  29, 89, 59.

•7.  Знайти двоцифрові числа, у яких куб цифри десятків  при діленні на цифру одиниць, дає остачу, що дорівнює цифрі десятків. Відповідь: 12, 23, 34, 45, 56, 67, 78, 89.

•8.  (Теорема: m³ = m(mod m +1) та m³ = m(mod m -1), де m >1 )Доведіть, що всі двоцифрові числа, у яких цифри розташовані послідовно у порядку зростання, володіють такою властивістю: «куб цифри десятків  при діленні на цифру одиниць, дає остачу, що дорівнює цифрі десятків.»

•9.    Знайти  усі двоцифрові числа, у яких куб цифри десятків  ділиться на цифру одиниць без остачі. Відповідь: 22,  42,  62,  82,  33,  44, 63,  93,  84,  64, 55,  66, 77, 88, 28, 48, 68,39, 69, 99.

•10.                Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу 6, що дорівнює цифрі одиниць, зменшеній на 1. Відповідь: 57, 67.

Теорема про остачі

Якщо остача від ділення числа а на b дорівнює с,  то остача від ділення числа аⁿ на b дорівнює остачі від ділення числа сⁿ на b.

Приклад 1. 13 : 5 = 2 (ост. 3), тоді 13ⁿ :5 дає таку саму остачу, як і 3ⁿ: 5.

Розв'язання.

1) n = 2, 13²:5 = 169:5 = 33 (ост. 4) і  3²:5 = 9:5 = 1 (ост. 4);

2) n = 3, 13³:5 = 2197:5 = 439 (ост. 2) і 3³:5 = 27:5 = 5 (ост. 2);

3) n = 4, 13⁴:5 = 28 561:5 = 5712 (ост. 1) і 3⁴:5 = 81:5 = 16(ост. 1);

4) n = 5, 13⁵:5 = 371 293:5 = 74 258 (ост. 3) і 3⁵:5 = 243:5 = 48 (ост. 3).

Приклад 2. Знайти остачу від ділення числа 2222ⁿ на 7.

Розв'язання.

1)         Знайдемо остачу від ділення 2222 на 7:  2222 : 7 = 317 (ост. 3).

2)         Остача від ділення 2222ⁿ на 7 така сама, як остача від ділення 3⁴ на 7, тобто 4, бо

3⁴:7 = 81:7 = 11 (ост. 4).

 Відповідь. 4.

Задача 1. Знайти остачу від ділення числа 2222⁵⁵⁵⁵  на 7.

Розв'язання.

1) Знайдемо остачу від ділення 2222 на 7: 2222 : 7 = 317 (ост. 3).

Остача від ділення 22225555 на 7 така сама, як остача від ділення 35555 на 7.

Знайдемо остачі від ділення 3n на 7 для різних значень n:

n=1, 3¹:7 = 3:7 = 0 (ост. 3);

n = 2, 3²:7 = 9:7 = 1 (ост. 2);

n = 3, 3³:7 = 27:7 = 3 (ост. 6);

n = 4, 3⁴:7 = 81:7 = 11 (ост. 4);

n = 5, 3⁵:7 = 243:7 = 34 (ост. 5);

n = 6, 3⁶:7 = 729:7 = 104 (ост. 1);

 n = 7, 3⁷:7 = 2187:7 = 312 (ост. 3).

Цикл дорівнює 6.

4)         Знайдемо кількість повних циклів у числі 5555.   5555 : 6 = 925 (ост. 5).

925 повних циклів відкидаємо.

Отже, ос­тача відділення 3⁵⁵⁵⁵ на 7 така сама, як від ділення 3⁵ на 7, тобто 5.

Отже, і остача від ділення 2222⁵⁵⁵⁵ на 7 до­рівнює 5.

Відповідь. 5.

Задача 2. Знайти остачу від ділення числа 5555²²²² на 7.

Розв'язання.

1) Знайдемо остачу від ділення 5555 на 7:

5555 : 7 = 793 (ост. 4).

Остача від ділення 5555²²²² на 7 така сама, як остача від ділення 4²²²² на 7.

Знайдемо остачі від ділення 4ⁿ на 7 для різних значень n:

n = 1, 4¹:7 = 4:7 = 0 (ост. 4);

n = 2, 4²:7 = 16:7 = 2 (ост. 2);

n = 3, 4³:7 = 64:7 = 9 (ост.1);

n = 4, 4⁴:7 = 256:7 = 36 (ост. 4).

Цикл дорівнює 3.

2)         Знайдемо кількість повних циклів у числі 2222.

2222 : 3 = 740 (ост. 2).

740 повних циклів відкидаємо.

Отже, ос­тача від ділення 4²²²² на 7 така сама, як і від ділення 4² на 7, тобто 2.

Отже, і остача відділення 5555²²²² на 7 до­рівнює 2.

Відповідь. 2.

Задача 3. Довести, що (2222⁵⁵⁵⁵+5555²²²²) ділиться  на 7 без остачі.

Доведення.

Оскільки 2222⁵⁵⁵⁵ при діленні на 7 дає оста­чу 5, а 5555²²²² при діленні на 7 дає остачу 2, а сума цих остач 5+2 = 7 ділиться на 7, то (2222⁵⁵⁵⁵ +5555²²²²) ділиться на 7 без остачі, що і треба було довести.

Задача 4. Знайти остачу від ділення числа 7 ²⁰⁰³ на 10.

Розв'язання.

1) Знайдемо остачу від ділення 7 на 10: 7: 10 = 0 (ост. 7).

2)Знайдемо остачі від ділення 7ⁿ  на 10 для різних значень n:

n = 1, 7¹:10 = 7:10 = 0 (ост. 7);

n = 2, 7²:10 = 49:10 = 4 (ост. 9);

n = 3, 7³:10 = 343:10 = 34 (ост. 3);

n = 4, 7⁴:10 = 2401:10 = 240(ост. 1);

n = 5, 7⁵ : 10 = 16 807:10 = 1680 (ост. 7).

Цикл дорівнює 4.

3)Знайдемо кількість повних циклів у числі 2003.

2003 : 4 = 500 (ост. 3).

4)500 повних циклів відкидаємо. Отже, ос­тача від ділення 7²⁰⁰³ на 10 така сама, як остача від ділення 73 на 10 , тобто 3.

Відповідь. 3.

5. Якою цифрою закінчується число 7²⁰⁰³ ?

Розв'язання. 

Остача відділення числа 7²⁰⁰³ на 10 є остан­ньою цифрою цього числа. Тобто число 7²⁰⁰³ закінчується цифрою 3.

Відповідь. 3.

Самостійно виконайте дві наступні вправи.

6.Знайти остачу від ділення числа 2006²⁰⁰⁷ на 3.

7. Якою цифрою закінчується 19²⁰⁰⁸ ?

Задачі для самостійного осмислення

1. a) Вираз х + 2 ділиться без остачі на 8. Як записати це твердження за допомогою  конгруенції? Знайти множину значень х.

б) Вираз х + 2 ділиться без остачі на 3. Як записати це твердження за допомогою  конгруенції? Знайти множину значень х.

2. a) Вираз 4х + 3 ділиться з остачею 2 на число 9. Як це записати за допомогою конгруенції? Знайти множину значень х.

б) Вираз 4х + 3 ділиться з остачею 2 на число 5. Як це записати за допомогою конгруенції? Знайти множину значень х.

3. a) Вираз 5х - 1 ділиться з остачею 3 на число 7. Як це записати за допомогою конгруенції? Знайти множину значень х.

б) Вираз 5х - 1 ділиться з остачею 3 на число 4. Як це записати за допомогою конгруенції? Знайти множину значень х.

4. a)  Вираз а +2 ділиться без остачі на 8. Як записати це твердження за допомогою конгруенції?

б)  Вираз а +2 ділиться без остачі на 3. Як записати це твердження за допомогою конгруенції?

5. a)  Які з чисел 22, 38, 6,-12, -13 конгруентні 9 за модулем 2, 3,7.

б)  Які з чисел 46, 37, 16, -17, -16 конгруентні 7 за модулем 2, 3, 5, 9.

6. Показати, що числа виду 8k+1, де k=0, 1, 2, ... конгруентні між собою за модулем 8.

7. Довести, що квадрат будь-якого непарного числа конгруентний
з одиницею за модулем 8.

8. Показати, що при n непарному, тобто n = 2k±1, число n³
конгруентне 6k+1 за модулем 4.

9. Довести, що якщо 50а+8b+с  º  0 (mod 21), то а+b+8с º 0(mod 21).

10.       Перевірити конгруенцію 8³⁰ º 34 (mod 55).

11.       Перевірити конгруенцію 5²¹º 27 (mod 77).

12.       З яким найменшим натуральним числом конгруентне число
N=8∙22∙1212∙17∙23 за модулем 9?

13.Чи вірно, що число 8754 конгруентне 4578 за модулем 9?

14. Чи вірно, що число 5647 конгруентне 22 за модулем 9?

15. Чи вірно, що m³-m+7 конгруентне 7 за модулем 6?

16. Чи вірно, що (2+7)⁵ = 2⁵+7⁵ (mod 5)?

Таблиця довжини двоцифрових періодів степенів цифр.

(Степеневі лишки при діленні на 100)

  mⁿ º ab(mod 100).

Отже, можливі тільки такі степеневі двоцифрові лишки  для степенів цифр: 00, 01,  02, 03, 04, 05, 06, 07, 08, 09, 12,16, 21,23, 24, 25, 27, 28, 29, 32, 36, 41, 43, 44, 47, 48, 49, 52,56, 61, 63, 64, 67, 68, 69, 72,76, 81,83,  84, 88, 89, 92, 96.

Задачі для самостійного осмислення

1. Довести, що рівняння з довільними натуральними показниками

   x^m º yⁿ º...º z^k (mod p)

має розв'язки в цілих числах  (x;y;z), де всі числа однакової парності.

2. Розв'язати рівняння в цифрах:

1) x^20m º y^20m º z^20m º 76(mod 100)

Відповіді: (2;4;8), (2;4;8), (4;2;8), (4;8;2), (8;2;4), (8;4;2).

2) x^20m º y^20m º z^20m º 1(mod 100)

Відповіді: (3;7;9), (3;9;7), (7;3;9), (7;9;3), (9;3;7), (9;7;3).

3) z^10m º 1(mod 100)

Відповіді: z = 9

4) m¹³ º m(mod 10)

Відповіді: m ={0; 1;2;3;4;5;6;7;8;9}

5) m⁵ º m(mod 10)

Відповіді: m ={0; 1;2;3;4;5;6;7;8;9}

6) m¹⁷º m(mod 10)

Відповіді: m ={0; 1;2;3;4;5;6;7;8;9}

7) m⁹º m(mod 10)

Відповіді: m ={0; 1;2;3;4;5;6;7;8;9}

8) m⁴ⁿ⁺¹º m(mod 10)

Відповіді: m ={0; 1;2;3;4;5;6;7;8;9}

9) m⁴ⁿ⁺²º m²(mod 10)

Відповіді: m ={0; 1;2;3;4;5;6;7;8;9}

10) m⁴ⁿ⁺³º m³(mod 10)

Відповіді: m ={0; 1;2;3;4;5;6;7;8;9}

10) m⁴⁽ⁿ⁺¹⁾º m⁴(modПавло

Коментар: 0 Переглядів: 390