ТЕОРІЯ ЧИСЕЛ ДЛЯ ШКОЛЯРІВ: Подільність цілих чисел. Олімпіадні завдання.

1. Цілі числа

1. Подільність цілих чисел. Властивості подільності. Теорема про розподіл із залишком

Визначення. Нехай a, b

- цілі числа. Кажуть, що число

ділиться на

, якщо

можна представити у вигляді a = nb

, де

- ціле число.

Інакше:

- дільник

Позначення: $a \ vdots b$ .

властивості подільності

Нехай

- цілі числа, число

- просте.

1. Якщо в рівності a + b = c

два числа діляться на

, то і третє число ділиться на

2. Якщо $a \ vdots b$ , то $ac \ vdots bc$ .

3. Якщо $a \ vdots b$ і $b \ vdots c$ , то $a \ vdots c$ .

4. Якщо $ab \ vdots p$ , то або $a \ vdots p$ , або $b \ vdots p$ .

Приклад. Довести, що якщо $a + b + c \ vdots m$ і $a ^ 2 + b ^ 2 + c ^ 2 \ vdots m$ , то і $a ^ 4 + b ^ 4 + c ^ 4 \ vdots m$ .

Рішення.

$\ Begin {array} {l} (a + b + c) ^ 2 = a ^ 2 + b ^ 2 + c ^ 2 + 2 (ab + ac + bc) \ Rightarrow2 (ab + ac + bc ) \ vdots m, \\ 4 (ab + bc + ac) ^ 2 = 4 (a ^ 2b ^ 2 + a ^ 2c ^ 2 + b ^ 2c ^ 2) + 8abc (a + b + c ), \ end {array}$
звідки

2 (ab + bc + ac) ^ 2 = 2 (a ^ 2b ^ 2 + a ^ 2c ^ 2 + b ^ 2c ^ 2) + 4abc (a + b + c)

$\ Begin {array} {l} 2 (a ^ 2b ^ 2 + a ^ 2c ^ 2 + b ^ 2c ^ 2) \ vdots m, \\ a ^ 4 + b ^ 4 + c ^ 4 = a ^ 2 + b ^ 2 + c ^ 2) ^ 2-2 (a ^ 2b ^ 2 + a ^ 2c ^ 2 + b ^ 2c ^ 2) \ Rightarrow \\ a ^ 4 + b ^ 4 + c ^ 4 \ vdots m. \ end {array}$

Теорема. Будь-яке ціле

представляється єдиним способом за допомогою цілого $b \ ne0$ рівністю виду a = bq + r

, де

- цілі, $0 \ le r <| b |$ . Число

називається приватним,

- залишком від ділення

на

Приклад. Чи може число ділитися на

, а при діленні на

давати в залишку

Рішення. Числа, що діляться на 8, мають вигляд

, $k \ in \ mathbb {Z}$ , а при діленні на

дають в залишку

, - вид

, $l \ in \ mathbb {Z}$ . Розглянемо всі залишки при діленні на Н.О.К. (12,8) = 24

. Діляться на

числа виду 24m, 24m + 8,24m + 16

, і жодне з них при розподілі на

це не дає в залишку

2. Порівняння та їх властивості

Визначення. Нехай

- цілі числа,

- натуральне число. Кажуть, що

можна порівняти з

по модулю

, якщо при розподілі на

вони дають однакові залишки.

Позначення: $a \ equiv b \ pmod {m}$ або $a \ equiv_m b$ .

Приклад. $45 \ equiv75 \ pmod {10}, 182 \ equiv-4 \ pmod {6}$ .

Теорема.

порівняно з

по модулю

тоді і тільки тоді, коли $ab \ vdots m$ .

властивості порівнянь

1) $a \ equiv a \ pmod {m}$ (рефлексивність).

2) $a \ equiv b \ pmod {m} \ Longrightarrow b \ equiv a \ pmod m$ (симетричність).

3) $a \ equiv b \ pmod {m}, b \ equiv c \ pmod {m} \ Longrightarrow a \ equiv c \ pmod {m}$ (транзитивність).

4) $a \ equiv b \ pmod {m}, c \ equiv d \ pmod {m} \ Longrightarrow a + c \ equiv b + d \ pmod {m}$ , $ac \ equiv bd \ pmod {m}$ , $ac \ equiv bd \ pmod {m}$ .

5) $ac \ equiv bc \ pmod {m}$ , \ nod $(C, m) = 1 \ Longrightarrow a \ equiv b \ pmod {m}$ .

Вправа. Які залишки можуть давати квадрати цілих чисел при діленні на 3, 4, 5, 8, 9

; куби цілих чисел при діленні на

, на

Приклад. Довести, що якщо

- просте число, то

$a \ equiv b \ pmod {p ^ n} \ Rightarrow a ^ p \ equiv b ^ p \ pmod {p ^ {n + 1}}.$

Рішення. За умовою, $ab \ vdots p ^ n$ . Тоді так як

$a ^ pb ^ p = (ab) (a ^ {p-1} + a ^ {p-2} b + a ^ {p-3} b ^ 2 + \ dots + b ^ {p-1}),$

залишається довести, що другий множник ділиться на

Оскільки $a \ equiv b \ pmod {p}$ , маємо

$a ^ {p-1} + a ^ {p-2} b + a ^ {p-3} b ^ 2 + \ dots + b ^ {p-1} \ equiv pa ^ {p-1} \ pmod { p}.$

Звідси отримуємо необхідну.

3. Теореми Ферма і Ейлера

Теорема (Ферма) . Якщо

просте і

не ділиться на

, то

$a ^ {p-1} \ equiv 1 \ pmod {p}.$

Теорема (Ейлер). Для будь-яких натуральних взаємно простих

виконується

$a ^ {\ phi (m)} \ equiv1 \ \ pmod {m}.$

Слідство. Нехай $a \ equiv b \ pmod {m}$ , $p \ equiv n \ pmod {\ varphi (m)}$ , Н.О.Д. (A, m) = 1

. Тоді $a ^ n \ equiv b ^ p \ pmod {m}$ .

Приклад. Знайти $2 ^ {2000} \ pmod {25}$ .

Рішення.

$\ Varphi (25) = 20,2000 \ equiv0 \ pmod {20}, 2 ^ {2000} \ equiv2 ^ 0 \ pmod {20} \ equiv1 \ pmod {20}.$

Приклад. Довести, що якщо $a + b + c \ vdots30$ , то $a ^ 5 + b ^ 5 + c ^ 5 \ vdots30$ .

Рішення. $30 = 2 \ cdot3 \ cdot5$ .

$a ^ 5 \ equiv a \ pmod {2,3,5}.$

Те ж для

- Числа попарно взаємно прості.

4. Приклади розв'язання нелінійних рівнянь

1. Вирішити рівняння в натуральних числах

Рішення. Розкладемо ліву частину рівняння на множники:

Уявімо

у вигляді добутку двох натуральних множників усіма можливими способами:

$28 = 1 \ cdot28 = 2 \ cdot14 = 4 \ cdot7 = 7 \ cdot4 = 14 \ cdot2 = 28 \ cdot1.$

Прирівнюємо один з множників зліва одному, інший - іншого. Вирішуємо отримані системи. Можливо спрощення: тут числа 2x + y

однаковою парності.

Відповідь. x = 4, y = 6

Зауваження. При пошуку цілих рішень розглядали б також розкладання $(-1) \ Cdot (-28) = (- 2) \ cdot (-14) =$ і т.д.

2. Вирішити в цілих числах рівняння

Рішення. На множники НЕ розкладається. висловимо

$y = x-3 + \ frac {5} {x + 3} \ qquad (x \ ne-3).$

При цілому

також

буде цілим, якщо $5 \ vdots (x + 3)$ , що можливо при $x + 3 = \ pm1, \ pm5$ .

Відповідь. $(\ Pm2,0), (- 4, -12), (- 8, -12)$ .

3. Довести, що рівняння 3x ^ 2-4y ^ 2 = 13

не має цілих рішень.

Рішення. Порівняння по модулю

: $-y ^ 2 \ equiv1 \ pmod {3}$ , що неможливо, так як квадрати цілих чисел при діленні на

можуть давати залишки або

, або

5. Теорема Вільсона

Теорема. Число

- просте тоді і тільки тоді, коли виконується порівняння

$(P-1)! + 1 \ equiv0 \ pmod {p}.$

Приклад (теорема Лейбніца). Довести, що число

просте тоді і тільки тоді, коли

$(P-2)! \ Equiv1 \ pmod {p}.$

Рішення. За теоремою Вільсона

- просте $\ Leftrightarrow$

$(P-1)! + 1 \ equiv0 \ pmod {p}.$

тоді маємо

$(P-1)! + 1 = (p-2)! (P-1) + 1 = p (p-2)! - (P-2)! + 1 \ equiv- (p-2)! + 1 \ pmod {p}.$

Завдання.

1. Знайдіть залишок від ділення

а) $36 ^ {2002} + 95 ^ {2002}$ на

; б) $2 ^ {2000}$ на

2. Знайдіть

а) останню цифру числа $1989 ^ {1989}$ ;

б) дві останні цифри числа $9 ^ {9 ^ {9 ^ 9}}$ .

3. Доведіть (без калькулятора), що такі числа складові:

а) $711 \ dots117$ (усього 2004 одиниці);

б) $2 \ cdot2006 ^ 2 + 13 \ cdot2005 \ cdot2006 + 11 \ cdot2005 ^ 2$ .

в) $4 ^ {545} + 545 ^ 4$ .

4. Доведіть, що в послідовності $11,111,1111,11111, \ ldots$ немає квадратів цілих чисел.

5. а) При яких натуральних значеннях

число

ділиться на

б) Доведіть, що число $A = \ underline {a_0a_1 \ dots a_ {n-2} a_ {n-1} a_n} _ {10}$ ділиться на

тоді і тільки тоді, коли число $\ Underline {a_0a_1 \ ldots a_ {n-2}} + \ underline {a_ {n-1} a_n}$ ділиться на

6. Вирішіть рівняння в цілих числах:

а)

; б)

7. Нехай

- ціле число, n> 1

. Чи ділиться $n ^ {n-1} -1$ на (N-1) ^ 2

8. На 44 деревах, розташованих по колу, сиділи 44 веселих чижа (на кожному дереві - по Чижа). Час від часу два чижа одночасно перелітають на сусідні дерева в різних напрямках (один - за годинниковою стрілкою, а інший - проти). Доведіть, що чижі не зможуть зібратися на одному дереві.

9. Доведіть, що рівняння