1. Принцип математической индукции
2. Теорема о делении целых чисел с остатком
3. НОД целых чисел и алгоритм Евклида
4. Решение ур-ний вида ax + by = c в целых числах
5. Основная теорема арифметики
6. Теорема Евклида о бесконечности множества простых чисел. Решето Эратосфена
7. Теорема Эйлера и малая теорема Ферма
8. Комплексные числа и операции над ними
9. Тригонометрическая формула комплексных чисел. Формула Муавра
10. Сопряжённые числа и их основные св-ва
11. Извлечение корня n-ой степени из комплексного числа. Корни из единицы
12. Многочлены и операции над ними
13. Теорема о делении многочлена с остатком
14. НОД многочленов и алгоритм Евклида
15. Теорема Безу и метод Горнера деления многочлена на линейный двучлен
16. Кратные корни. Теорема о корнях первой производной
17. Основная теорема алгебры и следствия из неё для многочленов с действительными коэффициентами
18. Интерполяционная формула Лагранжа
19. Формула Виета

№1. Док-те неравенство Коши.

Если a₁, ... , a_n > 0, то

Вспомогательная лемма:
если произведение n положительных чисел равно 1, то их сумма больше или равна n.

Пусть a₁, ... , a_n > 0, причём a₁*...*a_n = 1. Тогда a₁+...+a_n ≥ n.
Докажем по индукции:
База: при n=1 утверждение очевидно
Шаг: пусть утверждение верно для n=k, т.е. a₁*...*a_k=1 => a₁+...+a_k ≥ k. Заметим, что среди чисел a₁, ... , a_k найдётся пара (для определённости a₁, a₂) такая, что a₁≥1, a₂≤1:

(a₁-1)(a₂-1) ≤ 0
a₁*a₂+1 ≤ a₁+a₂

Пусть теперь имеется (k+1) число, тогда a₁*...*a_k+1 = 1. Мы хотим док-ть, что a₁+...+a_k+1 ≥ k+1. Как уже было показано, из a₁, ... , a_k+1 найдутся два числа такие, что

a₁*a₂+1 ≤ a₁+a₂

Прибавим к обеим частям этого неравенства a₃+...+a_k+1. Получим

a₁+...+a_k+1 ≥ a₁*a₂+a₃+...+a_k+1+1 ≥ k+1,
где a₁*a₂+a₃+...+a_k+1 - сумма k чисел, произведение которых равно 1

Теперь докажем неравенство Коши. Пусть a₁*...*a_n = А. Тогда

По вспомогательной лемме получаем:

№2. Известно, что некоторый многочлен в рациональных точках принимает рациональные значения. Док-те, что все его коэффициенты рациональны.

Пусть F(x)=a_oxⁿ+a₁x^n-1+...+a_n-1x¹+a_nx⁰. Тогда x є Q, F(x) є Q => a_i є Q, где i = 0, 1, ... , n
Проведём доказательство по индукции
База: n=0: F(x)=a_o, F(x) є Q => a_o є Q
Шаг: Пусть утв. верно при k ≥ 0, т.е.

F_k(x)=a_ox^k+a₁x^k-1+...+a_k-1x¹+a_kx^o
x є Q, F_k(x) є Q => a_i є Q, где i = 0, 1, ... , k

Покажем, что верно

F_k+1(x)=a_ox^k+1+a₁x^k+...+a_kx¹+a_k+1x^o
x є Q, F_k+1(x) є Q => a_i є Q, где i = 0, 1, ... , k+1

Действительно,

F_k+1(x)=xF_k(x)+a_k+1,
где F_k(x), F_k+1(x), x є Q => a_k+1 є Q

№3. Док-те, что если и d|a_i, где i=1, 2, ... , n, то d|b.

Согласно условию

a_i=dq_i
b=a₁+a₂+...+a_n=dq₁+dq₂+...+dq_n=d(q₁+q₂+...+q_n)=dq'

Отсюда получаем: d|b

№4. Док-те, что если a и b - целые взаимно простые числа, то ур-ние ax+by=1 разрешимо в целых числах.

Ясно, что можно считать, что a, b є N.
Будем док-ть с помощью индукции по величине суммы a+b=n.
База: a+b=2 => a=b=1. Решением ур-ния является, например, пара (0,1)
Шаг: предположим истинность утв. для всех пар (a,b)=1 с суммой a+b<k (k>2). Покажем, что тогда утв. справедливо и для пар a и b таких, что (a,b)=1 и a+b≤k
Рассмотрим два случая:
1) (a,b)=1, a+b<k - утв. верно по предположению;
2) (a,b)=1, a+b=k

Без ограничения общности будем считать, что a>b. Тога (a-b,b)=1 и к тому же (a-b)+b=a<k. Тогда по предположению ур-ние

(a-b)U+bV=1 разрешимо в целых числах. Тогда
aU+b(V-U)=1 также разрешимо в целых числах
или ax+by=1

№5. Док-те, что если a, b и c - целые числа, причём (a,b)=1 и b|ac, то b|c

b|ac => ac=bq
Поскольку (a,b)=1, то c=b(q/a)=bq' => b|c

№6. Док-те, что наименьший отличный от 1 делитель натурального числа n>1 есть простое число

Пусть q≠1 - наименьший делитель некоторого натурального числа n>1. Предположим, что q-составное, т.е.

q=ab, где 1<a<q, 1<b<q

Но тогда по одной из лемм: q|n, a|q => a|n. К тому же a<q => a - наименьший делитель n. Полученное противоречие завершает док-во: q-простое

№7. Док-те, что наименьший простой делитель составного числа n не превосходит .

Пусть q-наименьший ≠1 делитель числа n. Тогда q-простое. При этом n=qa, где a≥q. Следовательно

aq≥q² => n≥q² => ≥q

№8. Док-те, что если p-простое число, то любое целое число a либо взаимно просто с p, либо делится на p

Поскольку, p-простое число, тогда
  либо (a,p)=1 => a взамно просто с p;
  либо (a,p)=p => a делится на p

№9. Док-те, что является иррациональным числом

Предположим, что - рациональное число, т.е. = a/b. Можем считать, что все сокращения произведены и числа a и b не имеют общих множителей. Возводя в квадрат это соотношение, получаем:

По теореме о единственности разложения число a делится на 2, следовательно, a² делится на 4. И вновь по теореме о единственности разложения, применённой к числу b², получаем, что b делится на 2, что противоречит предположению о том, что числа a и b не имеют общих множителей. Полученное противоречие показывает, что - число иррациональное.

О. Оре 'Приглашение в теорию чисел' (стр. 122-123)

№10. Док-те, что при n>1 справедлива формула

,

  где произведение берётся по всем простым числам, не превосходящим числа n.

Нам необходимо найти наибольшую степень числа p, на которую делится n!. Каждое p-ое число: p, 2p, 3p, ... - делится на p. Всего таких чисел, не превосходящих числа n, [n/p]. Однако некоторые из них делятся на вторую степень числа p, а именно: p², 2p², 3p², ... . Таких чисел существует [n/p²]. Некоторые из них делятся на третью степень числа p , т.е. на p³: p³, 2p³, 3p³, ... - их существует [n/p³] и т.д.
Это показывает, что выражение для точной степени числа p, делящей число n! таково:

Таким образом,

,

  где произведение берётся по всем простым числам, не превосходящим числа n.

№11. Пусть каноническое разложение числа n имеет вид

Док-те, что число его делителей:

Если число d является делителем числа n, т.е. n=dd₁, то единственными простыми числами, на которые может делиться число d, будут только те, которые делят число n, а именно: p₁, ... , p_r. Таким образом, мы можем записать разложение числа d на простые множители в виде

Простое число p₁ может содержаться не более раз, как и в самом числе n; аналогично - для p₂ и других простых чисел. Это значение для числа мы можем выбрать +1 способом: =0, 1, ... , . Аналогично и для других простых чисел. Так как каждое из +1 значений, которые может принимать число , может сочетаться с любым из +1 возможных значений числа и т.д., то мы видим, что общее число делителей числа n задаётся формулой

№12. Док-те, что

n=d₁d₂
Пусть d₁≤d₂. Тогда d₁≤≤d₂. Отсюда все делители числа n разбиваются на две группы - меньшие и большие корня из n. Причём каждому делителю из 1ой группы соответствует делитель из 2ой группы и наоборот. Пусть D₁ и D₂ кол-во делителей в каждой из групп (D₁=D₂). Тогда

№13. Док-те, что существуют сколь угодно длинные отрезки натурального ряда, не содержащие ни одного простого числа

При n>2 (n є N): N_k=n!+k, k=2, 3, ... , n
Числа N_k представляют собой (n-1) последовательно идущих натуральных чисел, при этом все они составные, поскольку k|N_k

№14. Док-те, что при n>2 между n и n! содержится по крайней мере одно простое число

Предположим обратное.
Пусть p₁, ... , p_k - все простые числа ≤n. Возъмём число N=p₁...p_k+1. Видно, что n<N<n!, причём N-простое число. Полученное противоречие завершает док-во: мы нашли простое число между n и n!

№15 - №21. Сравнения. Леммы

Для док-ва используем определение сравнения: a ≡ b (mod m) <=> a=mq₁+r, b=mq₂+r <=> a-b=mq

№22. Док-те, что если a²+b² делится на 3, то a и b оба делятся на 3

Поскольку 3|(a²+b²), то можно рссмотреть две возможные ситуации:
  1) 3|a => 3|b;
  2) a не делится на 3: рассмотрим разные представления чисел a и b:
    2.1) a=3k+1, b=3n+1
    2.2) a=3k+1, b=3n+2
    2.3) a=3k+2, b=3n+2
  как нетрудно заметить, сумма квадратов a²+b² во всех трёх случаях (2.1, 2.2, 2.3) не делится на 3

№23. Док-те, что все числа Ферма (F_n = 2²ⁿ+ 1), начиная с n = 2, оканчиваются цифрой 7.

2²ⁿ+ 1 ≡ 7 (mod 10)
2²ⁿ ≡ 6 (mod 10)

Докажем по индукции:
База: n=2     2²ⁿ ≡ 6 (mod 10) - истина
Шаг: предположим истинность утверждения при k ≥ 2:
2^2k ≡ 6 (mod 10)    (*)
Покажем, что верно:
2^2k+1 ≡ 6 (mod 10)
Возведём (*) в квадрат:
2^2k+1 ≡ 36 ≡ 6 (mod 10)

№24. Док-те, что если a и b - взаимно простые целые числа, то каждый простой нечётный делитель числа a²+b² имеет вид 4n+1.

Пусть p - простой нечётный делитель a²+b². Тогда

Причём p не делит ни a, ни b.
Возведём сравнение в степень (p-1)/2:

Тогда 1 ≡ (-1)^(p-1)/2 (mod p). Следовательно

№25. Док-те, что существует бесконечно много простых чисел вида 4n+3

Пусть утв. неверно и p₁, p₂, ... , p_r - все простые вида 4n+3
Рассмотрим число N=4p₁p₂...p_r-1 - это число вида 4n+3, оно нечётное. Следовательно, все его простые делители - нечётные числа, которые могут иметь вид либо 4n+1, либо 4n+3.
Произведение чисел вида 4n+1 есть число того же вида => у числа N имеется простой делитель вида 4n+3. Обозначим его за p. Очевидно, что p≠p_i, i=1, 2, ... , r => есть ещё одно простое число вида 4n+3

№26. Док-те, что существует бесконечно много простыхчисел вида 6n+5

Предположим, что простых чисел вида 6n+5 конечное число: p₁, p₂, ... , p_r.
Рассмотрим число N=6p₁p₂...p_r-1. Это число вида 6n+5.
Произведение чисел вида 6n+1 есть число того же вида => у числа N имеется простой делитель вида 6n+5 (или 6n-1=6n-1+6-6=6(n-1)+5). Обозначим его через p. Очевидно, что p≠p_i, i-1, 2, ... , r => есть ещё одно простое число вида 6n+5

№27. Док-те, что существует бесконечно много простых чисел вида 4n+1

Пусть утв. неверно: p₁, ... , p_r - все простые вида 4n+1
Рассмотрим N=(2p₁p₂...p_r)²+1=a²+b²
Данное число имеет простой делитель вида 4n+1. Этот делитель будет очевидно отличен от p₁, ... , p_r.

№28. Док-ть, что натуральное число n делится на 3 (на 9) тогда и только тогда, когда на 3 (на 9) делится сумма его цифр

, a_i-цифры, a_n≠0
N=a_n*10ⁿ+a_n-1*10^n-1+...+a₁*10+a₀
Пусть сумма a_n+a_n-1+...+a₁+a₀ делится на 3. Тогда (99..99+1)a_n+(99..99+1)a_n-1+...+(9+1)a₁+a₀=
=9(11..11a_n+11..11a_n-1+...+a₁)+a_n+a_n-1+...+a₁+a₀, т.е. 3|N

№29. Док-ть, что для того, чтобы натуральное число n делилось на 11, необходимо и достаточно, чтобы разность сумм цифр, стоящих на чётных и нечётных местах в записи данного числа, делилась на 11.

1 ≡ 1 (mod 11)
10 ≡ -1 (mod 11)
100 ≡ 1 (mod 11)
1000 ≡ -1 (mod 11)
И вообще
10²ⁿ ≡ 1 (mod 11)
10²ⁿ⁺¹ ≡ -1 (mod 11)

1, -1, 1, -1 - характеристический ряд модуля 11
N=a_n*10ⁿ+a_n-1*10^n-1+...+a₁*10+a₀ ≡ (-1)ⁿa_n+(-1)^n-1a_n-1+...-a₁+a₀ (mod 11)

№30. Док-те, что корень n-ой степени из единицы ε тогда и только тогда будет первообразным, когда его степени ε^k, k=0,1, ... , k-1, различны

Если все степени ε^k различные, то ε-первообразный корень
Пусть теперь ε-первообразный корень, ε^k=ε^m, где k≥0, m≥0, m≤n-1, k≠m. Пусть для определённости k>m. Тогда

ε^k-m=ε^k/ε^m=1 => ε-не может быть первообразным

№31. Док-те, что если ε етсь первообразный корень n-ой степени из единицы, то ε^k тогда и только тогда является первообразным корнем n-ой степени из единицы, когда (k, n)=1

Пусть ε-первообразный корень n-ой степени из единицы, (k, n)=d
Пусть d>1. Тогда k=dk₁, n=dn₁
  (ε^k)^n₁=ε^dk₁n₁=(εⁿ)^k₁=1 => ε^k-не является первообразным
Пусть d=1, ε^k-корень m-ой степени из единицы, где m<n. Тогда
  (ε^k)^m=ε^km=1, а т.к. εⁿ=1, то n|km
 Такого быть не может, т.к. (k,n)=1, m<n. Противоречие с предположением о том, что существует m<n: (ε^k)^m=1

№32. Найдите сумму и произведение всех корней n-ой степени из единицы (n>1)

Док-во с помощью следующего утв.: все корни n-ой степени из единицы явл. вершинами правильного n-угольника, вписанного в ок-сть

№33. Док-те, что -первообразный корень 8-й степени из единицы