неділя, 5 лютого 2017 р.

Тема: "Цілі числа" для олімпіадників



1. Цілі числа

1. Подільність цілих чисел. Властивості подільності. Теорема про розподіл із залишком
Визначення. Нехай a, b- цілі числа. Кажуть, що число aділиться на b, якщо aможна представити у вигляді a = nb, де n- ціле число.
Інакше: b- дільник a.
Позначення:a \ vdots b .
властивості подільності
Нехай a, b, c, d- цілі числа, число p- просте.
1. Якщо в рівності a + b = cдва числа діляться на d, то і третє число ділиться на d.
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} <br /> (a + b + c) ^ 2 = a ^ 2 + b ^ 2 + c ^ 2 + 2 (ab + ac + bc) \ Rightarrow2 (ab + ac + bc ) \ vdots m, \\ <br /> 4 (ab + bc + ac) ^ 2 = 4 (a ^ 2b ^ 2 + a ^ 2c ^ 2 + b ^ 2c ^ 2) + 8abc (a + b + c ), <br /> \ end {array}
звідки
2 (ab + bc + ac) ^ 2 = 2 (a ^ 2b ^ 2 + a ^ 2c ^ 2 + b ^ 2c ^ 2) + 4abc (a + b + c)
і
\ Begin {array} {l} <br /> 2 (a ^ 2b ^ 2 + a ^ 2c ^ 2 + b ^ 2c ^ 2) \ vdots m, \\ <br /> a ^ 4 + b ^ 4 + c ^ 4 = a ^ 2 + b ^ 2 + c ^ 2) ^ 2-2 (a ^ 2b ^ 2 + a ^ 2c ^ 2 + b ^ 2c ^ 2) <br /> \ Rightarrow \\ <br / > a ^ 4 + b ^ 4 + c ^ 4 \ vdots m. <br /> \ end {array}
Теорема. Будь-яке ціле aпредставляється єдиним способом за допомогою цілого b \ ne0рівністю виду a = bq + r, де q, r- цілі, 0 \ le r <| b |. Число qназивається приватним, r- залишком від ділення aна b.
Приклад. Чи може число ділитися на 8, а при діленні на 12давати в залишку 10?
Рішення. Числа, що діляться на 8, мають вигляд 8kk \ in \ mathbb {Z}, а при діленні на 12дають в залишку 10, - вид 12l + 10l \ in \ mathbb {Z}. Розглянемо всі залишки при діленні на Н.О.К. (12,8) = 24. Діляться на 8числа виду 24m, 24m + 8,24m + 16, і жодне з них при розподілі на 12це не дає в залишку 10.
2. Порівняння та їх властивості
Визначення. Нехай aі b- цілі числа, m- натуральне число. Кажуть, що aможна порівняти з bпо модулю m, якщо при розподілі на mвони дають однакові залишки.
Позначення: a \ equiv b \ pmod {m} або a \ equiv_m b.
Приклад. 45 \ equiv75 \ pmod {10}, 182 \ equiv-4 \ pmod {6}.
Теорема. aпорівняно з bпо модулю mтоді і тільки тоді, коли 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; куби цілих чисел при діленні на 7, на 9?
Приклад. Довести, що якщо p- просте число, то
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}),
залишається довести, що другий множник ділиться на p.
Оскільки 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. Теореми Ферма і Ейлера
Теорема (Ферма) Якщо pпросте і aне ділиться на p, то
a ^ {p-1} \ equiv 1 \ pmod {p}.
Теорема (Ейлер). Для будь-яких натуральних взаємно простих aі m> 1виконується
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}.
Те ж для bі c2,3,5- Числа попарно взаємно прості.
4. Приклади розв'язання нелінійних рівнянь
1. Вирішити рівняння в натуральних числах
4x ^ 2-y ^ 2 = 28.
Рішення. Розкладемо ліву частину рівняння на множники:
(2x-y) (2x + y) = 28.
Уявімо 28у вигляді добутку двох натуральних множників усіма можливими способами:
28 = 1 \ cdot28 = 2 \ cdot14 = 4 \ cdot7 = 7 \ cdot4 = 14 \ cdot2 = 28 \ cdot1.
Прирівнюємо один з множників зліва одному, інший - іншого. Вирішуємо отримані системи. Можливо спрощення: тут числа 2x + yі 2x-yоднаковою парності.
Відповідь. x = 4, y = 6.
Зауваження. При пошуку цілих рішень розглядали б також розкладання (-1) \ Cdot (-28) = (- 2) \ cdot (-14) =і т.д.
2. Вирішити в цілих числах рівняння
x ^ 2-xy-3y-4 = 0.
Рішення. На множники НЕ розкладається. висловимо y:
y = x-3 + \ frac {5} {x + 3} \ qquad (x \ ne-3).
При цілому xтакож yбуде цілим, якщо 5 \ vdots (x + 3), що можливо при x + 3 = \ pm1, \ pm5.
Відповідь. (\ Pm2,0), (- 4, -12), (- 8, -12).
3. Довести, що рівняння 3x ^ 2-4y ^ 2 = 13не має цілих рішень.
Рішення. Порівняння по модулю 3-y ^ 2 \ equiv1 \ pmod {3}, що неможливо, так як квадрати цілих чисел при діленні на 3можуть давати залишки або 0, або 1.
5. Теорема Вільсона
Теорема. Число p- просте тоді і тільки тоді, коли виконується порівняння
(P-1)! + 1 \ equiv0 \ pmod {p}.
Приклад (теорема Лейбніца). Довести, що число pпросте тоді і тільки тоді, коли
(P-2)! \ Equiv1 \ pmod {p}.
Рішення. За теоремою Вільсона 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} на 11б) 2 ^ {2000} на 50.
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. а) При яких натуральних значеннях nчисло 3 ^ n-1ділиться на 13?
б) Доведіть, що число A = \ underline {a_0a_1 \ dots a_ {n-2} a_ {n-1} a_n} _ {10}ділиться на 11тоді і тільки тоді, коли число \ Underline {a_0a_1 \ ldots a_ {n-2}} + \ underline {a_ {n-1} a_n}ділиться на 11.
6. Вирішіть рівняння в цілих числах:
а) 3x ^ 2 + 2xy-y ^ 2 = 4 ; б) 3xy + 16x + 13y + 61 = 0 .
7. Нехай n- ціле число, n> 1. Чи ділиться n ^ {n-1} -1на (N-1) ^ 2?
8. На 44 деревах, розташованих по колу, сиділи 44 веселих чижа (на кожному дереві - по Чижа). Час від часу два чижа одночасно перелітають на сусідні дерева в різних напрямках (один - за годинниковою стрілкою, а інший - проти). Доведіть, що чижі не зможуть зібратися на одному дереві.
9. Доведіть, що рівняння
m ^ 2 + 3mn-2n ^ 2 = 122
не має цілих рішень.
10. Нехай число p- просте, p = 4n + 3. Доведіть, що
\ Left [\ left (\ frac {p-1} {2} \ right)! \ Right] ^ 2-1 \ vdots p;
якщо ж p- просте, p = 4n + 1, доведіть, що
\ Left [\ left (\ frac {p-1} {2} \ right)! \ Right] ^ 2 + 1 \ vdots p.
11. Натуральне число n \ vdots24. Доведіть, що сума всіх натуральних дільників числа n-1(включно з 1і n-1) також ділиться на 24.
12. Знайдіть залишок від ділення цілої частини числа \ Displaystyle \ frac {10 ^ {20000}} {10 ^ {100} +3}на 10.
13. Знайдіть всі рішення рівняння
x ^ {n + 1} - (x + 1) ^ {n} = 2001
в натуральних числах x, n.