Лінійне уявлення нод
Теорема. Нехай - цілі числа, НСД. Число можна представити у вигляді
Доведення. Нехай - множина всіх чисел, які можна отримати з і за допомогою додавання і віднімання. Тоді, якщо, то. Так як в алгоритмі Евкліда
A \ Longrightarrow \ dots \ Longrightarrow r_n \ in A. "title =" r_1 \ in A \ Longrightarrow r_2 \ in A \ Longrightarrow r_3 \ in
A \ Longrightarrow \ dots \ Longrightarrow r_n \ in A. "style =" vertical-align: -4px; border: none; ">
1. НСД двох чисел ділиться на будь-який спільний дільник цих чисел.
2. Рівняння, де - цілі коефіцієнти, - цілочисельні невідомі, вирішується в тому і тільки в тому випадку, якщо ділиться на НСД.
Прості і складені числа
Визначення. Ціле число називається складовим. якщо воно ділиться на яке-небудь ціле число, відмінне від і, 1 і -1.
Ціле число називається простим. якщо воно не є складовим і не дорівнює.
Теорема. Будь-яке складене натуральне число можна подати у вигляді добутку простих натуральних чисел.
Доведення. Нехай є такі складові натуральні числа, які не можна представити у вигляді добутку простих. Виберемо з цих чисел найменше і позначимо його через. Так як - складене число, то у нього є дільник, який більше 1 і менше.
m \ vdots a, \ quad 1
m \ vdots a, \ quad 1
Числа натуральні. Кожне з чисел або є простим, або це складене, менше, яке тому розкладається на прості множники. Але тоді і розкладається на прості множники. Отримали протиріччя.
Теорема. Якщо - цілі числа, - просте число,, то чи.
Доведення. Нехай ні, ні не діляться на. тоді
НСД, НСД. Отже, можна підібрати такі цілі числа і і такі цілі числа і, що
Перемножимо ці рівності почленно:
Кожне складова в лівій частині рівності ділиться на, а. Отримали протиріччя.
Теорема. Нехай - складене натуральне число і
де - прості натуральні числа. нехай
Доведення.
Якщо в лівій і правій частині є рівні множники, скоротимо на них і отримаємо рівність такого ж виду, в якому жоден співмножник в лівій здебільшого не дорівнює жодному співмножником в правій частині (якщо не всі співмножники скоротяться).
Права частина рівності ділиться на. Так як - просте число, то хоча б один співмножник у правій частині ділився на (за попередньою теоремою). У той же час всі співмножники в правій частині - це прості числа, не рівні. Отже, вони не діляться на. Протиріччя.
b = q_1 ^ q_2 ^ \ ldots p_t ^ "title =" a = p_1 ^ p_2 ^ \ ldots p_s ^, \
b = q_1 ^ q_2 ^ \ ldots p_t ^ "style =" vertical-align: -6px; border: none; ">
- канонічні розкладання чисел і.
У канонічний розклад НСД входять ті і тільки ті прості числа, які входять в обидва розкладання, причому з двох показників вибирається менший.
Просте число входить в канонічний розклад числа з показником, рівним
p ^ 3> \ right] + \ left [\ right] + \ ldots, "title =" \ displaystyle \ left [\ right] + \ left [\ right] + \ left [p ^ 3> \ right] + \ left [\ right] + \ ldots, "style =" vertical-align: -17px; border: none; ">
де підсумовування ведеться до тих пір, поки ціла частина не стане рівною нулю.
1. Довести, що ділиться на 30 для будь-якого цілого.
2. Довести, що для будь-якого цілого.
3. Довести, що сума кубів трьох послідовних чисел кратна 9.
4. Довести, що для будь-якого цілого невід'ємного
5. Довести, що для будь-якого цілого невід'ємного
6. Довести, що при будь-якому простому натуральному число.
7. Довести, що для будь-якого натурального
8. Довести, що для будь-якого натурального непарного
9. Які залишки можуть давати при розподілі на 9 куби цілих чисел?
10. Довести, що для будь-якого цілого
11. Довести, що для будь-якого натурального
12. Довести, що ні при якому цілому не ділиться на 169.
13. Довести, що якщо, то цілі числа і також діляться на 3.
14. Довести, що для будь-якого цілого
не мають спільних дільників, відмінних від 1.
15. Два двозначних числа, що закінчуються однією і тією ж цифрою, такі, що при розподілі на 9 приватна кожного з них дорівнює залишку іншого. Знайти всі числа, що задовольняють цим умовам.
16. Довести, що в будь-який з послідовностей
міститься нескінченно багато складових чисел.
17. Розкласти число на два натуральних множника, кожен з яких не менше 1000.
18. Довести, що число складене.
19 *. Натуральні числа такі, що. Довести, що число
20. Довести, що число (нулів і одиниць) складене.
21. Довести, що число
(Цифр там, де зазначено фігурною дужкою, по) складене.
22. Уявити в канонічному вигляді, знайти НСД
а) 4828896 та 27147960;
б) 22754277 і 7484400.
23. Довести, що для будь-якого натурального
24. Довести, що для будь-якого натурального
25. Довести, що непарна ступінь 48, збільшена на 1, кратна 7.
26. Знайти всі прості, для яких і також є простими.
27. Натуральні числа такі, що,
28. На яку найбільшу ступінь числа 3 ділиться твір всіх парних чотиризначних чисел?