Основы

Основы Теорий чисел - Делимость, Свойства сравнений, Теоремы Ферма и Эйлера, Вильсон

1. Делимость целых чисел. Свойства делимости. Теорема о делении с остатком

Определение. Пусть — целые числа. Говорят, что число делится на , если можно представить в виде , где — целое число.

Иначе: — делитель .

Обозначение: $a\vdots b$ .

Свойства делимости

Пусть — целые числа, число — простое.

1. Если в равенстве два числа делятся на , то и третье число делится на .

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}$
откуда

и

$\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$ равенством вида , где — целые, $0\le r<|b|$ . Число называется частным, — остатком от деления на .

Пример. Может ли число делиться на , а при делении на давать в остатке ?

Решение. Числа, делящиеся на 8, имеют вид , $k\in\mathbb{Z}$ , а при делении на дающие в остатке , — вид , $l\in\mathbb{Z}$ . Рассмотрим все остатки при делении на Н.О.К.. Делятся на числа вида , и ни одно из них при делении на не дает в остатке .

2. Сравнения и их свойства

Определение. Пусть и — целые числа, — натуральное число. Говорят, что сравнимо с по модулю , если при делении на они дают одинаковые остатки.

Обозначение: $a\equiv b\pmod{m}$ или $a\equiv_m b$ .

Пример. $45\equiv75\pmod{10},182\equiv-4\pmod{6}$ .

Теорема. сравнимо с по модулю тогда и только тогда, когда $a-b\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}$ , $a-c\equiv b-d\pmod{m}$ , $ac\equiv bd\pmod{m}$ .

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

Упражнение. Какие остатки могут давать квадраты целых чисел при делении на ; кубы целых чисел при делении на , на ?

Пример. Доказать, что если — простое число, то

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

Решение. По условию, $a-b\vdots p^n$ . Тогда так как

$a^p-b^p=(a-b)(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^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.$

Приравниваем один из множителей слева одному, другой — другому. Решаем полученные системы. Возможно упрощение: здесь числа и одинаковой четности.

Ответ. .

Замечание. При поиске целых решений рассматривали бы также разложения $(-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. Доказать, что уравнение не имеет целых решений.

Решение. Сравнения по модулю : $-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^{n-1}-1$ на ?

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

9. Докажите, что уравнение

не имеет целых решений.

10. Пусть число — простое, . Докажите, что

$\left[\left(\frac{p-1}{2}\right)!\right]^2-1\vdots p;$

если же — простое, , докажите, что

$\left[\left(\frac{p-1}{2}\right)!\right]^2+1\vdots p.$

11. Натуральное число $n\vdots24$ . Докажите, что сумма всех натуральных делителей числа (включая и ) также делится на .

12. Найдите остаток от деления целой части числа $\displaystyle\frac{10^{20000}}{10^{100}+3}$ на .

13. Найдите все решения уравнения

$x^{n+1}-(x+1)^{n}=2001$

в натуральных числах .

источник: hijos.ru
- Для комментирования войдите или зарегистрируйтесь
Несколько полезных неравенств

1. $a^2+b^2+c^2\ge ab+bc+ac$ .

Доказательство.

$\begin{array}{l} \displaystyle a^2+b^2+c^2-ab-bc-ac={1\over 2}(2a^2+2b^2+2c^2 -2ab-2ac-2bc)=\\[3mm] \displaystyle ={1\over 2}[(a^2-2ab+b^2)+(a^2-2ac+c^2) +(b^2-2bc+c^2)]=\\[3mm] \displaystyle ={1\over 2}[(a-b)^2+(a-c)^2+(b-c)^2]\ge0. \end{array}$

2. $\displaystyle a,b>0\Rightarrow {a+b\over 2}\ge\sqrt{ab}$ .

Доказательство.

$\displaystyle {a+b\over 2}-\sqrt{ab}={a+b-2\sqrt{ab}\over 2}={(\sqrt{a}-\sqrt{b})^2\over 2}\ge0 .$

3. $\displaystyle a,b,c,d>0\Rightarrow {a+b+c+d\over 4}\ge\sqrt[4]{abcd}$ .

Доказательство.

$\begin{array}{l} \displaystyle {a+b+c+d\over 4}={{a+b\over 2}+{c+d\over 2}\over 2}\ge{\sqrt{ab}+\sqrt{cd}\over 2}\ge\\[3mm] \ge\sqrt{\sqrt{ab}\cdot\sqrt{cd}}=\sqrt[4]{abcd}. \end{array}$

4. $\displaystyle a,b,c>0\Rightarrow {a+b+c\over 3}\ge\sqrt[3]{abc}$ .

Доказательство. Положим

$\displaystyle m={a+b+c\over 3} .$

Тогда
$\begin{array}{l} \displaystyle m={a+b+c+m\over 4}\ge\sqrt[4]{abcm},\\[2mm] m^4\ge abcm,\\ m^3\ge abc,\\ m\ge\sqrt[3]{abc}. \end{array}$

Примеры. Доказать

1. $a^4+b^4+c^4\ge abc(a+b+c)$ .

$\begin{array}{l} a^4+b^4+c^4\ge a^2b^2+b^2c^2+a^2c^2\ge ab\cdot bc+ab\cdot ac+ ac\cdot bc=abc(a+b+c). \end{array}$

2. $a,b,c\ge0\Rightarrow (a+b)(a+c)(b+c)\ge8abc$ .

$\left.\begin{array}{l} a+b\ge2\sqrt{ab},\\ b+c\ge2\sqrt{bc},\\ a+c\ge2\sqrt{ac}, \end{array}\right|\Rightarrow (a+b)(a+c)(b+c)\ge8abc.$

3. $\displaystyle a,b,c>0\Rightarrow(a+b+c)\left({1\over a}+{1\over b}+{1\over c}\right)\ge9$ .

$\begin{array}{l} a+b+c\ge3\sqrt[3]{abc},\\ \displaystyle {1\over a}+{1\over b}+{1\over c}\ge3\sqrt[3]{{1\over a}\cdot{1\over b}\cdot{1\over c}},\\[3mm] \displaystyle (a+b+c)\left({1\over a}+{1\over b}+{1\over c}\right)\ge9. \end{array}$

Задачи.

Докажите неравенства:

1. $a_1,a_2,\dots,a_n\ge0,a_1a_2\dots a_n=1$

$(1+a_1)(1+a_2)\dots(1+a_n)\ge2^n.$

2. $a,b,c\ge0\Rightarrow ab+ac+bc\ge a\sqrt{bc}+b\sqrt{ac}+c\sqrt{ab}$ .

3. $a,b,c\ge0\Rightarrow a^{16}+b^{16}+c^{16}\ge a^5b^5c^5(a+b+c)$ .

4. $a^4+b^4+2c^4\ge4abc^2$ .

5 $^{*}$ . $x,y,z\ge0,x+y+z=1\Rightarrow$

$\displaystyle \left(1+{1\over x}\right)\left(1+{1\over y}\right)\left(1+{1\over z}\right)\ge64 .$

6. $\displaystyle {a^3+b^3\over 2}\ge\left({a+b\over 2}\right)^3\ (a,b>0)$ .

7. $\sqrt[n]{2+\sqrt{3}}+\sqrt[n]{2-\sqrt{3}}>2$ .

8. Докажите, что если для уравнения дискриминант ${\cal D}$ неотрицателен, то это же верно и для уравнения

9. Пусть . Докажите, что по крайней мере одно из уравнений

$x^2+p_1x+q_1=0,\qquad x^2+p_2x+q_2=0$

имеет неотрицательный дискриминант.

10. Докажите, что

а) при любом значении $\lambda\ne-1$ дискриминант ${\cal D}$ уравнения

$(x-a)(x-c)+\lambda(x-b)(x-d)=0,$

где , положителен.

б) при любых значениях дискриминант уравнения

неотрицателен.
- Для комментирования войдите или зарегистрируйтесь
Свойства неравенств

Определение. означает, что — положительное число, означает, что — отрицательное число, $a\ge b$ означает, что или .

Свойства неравенств

Свойства неравенств следуют из свойств вещественных чисел.

1. Для любых чисел и справедливо одно и только одно из следующих трех утверждений (трихотомия)

2. положительно $\Leftrightarrow a>0$ ,

отрицательно $\Leftrightarrow a<0$ .

3. Транзитивность

$\left.\begin{array}{l} a>b\\ b>c \end{array}\right|\Rightarrow a>c.$

4. $a>b\Leftrightarrow b<a$ .

Доказательство.

$\begin{array}{l} a>b\Rightarrow a-b>0\Rightarrow b-a<0\Rightarrow b<a,\\ b<a\Rightarrow b-a<0\Rightarrow a-b>0\Rightarrow a>b. \end{array}$

5. $a>b\Rightarrow a+c>b+c$ .

Доказательство. $a>b\Rightarrow a-b>0\Rightarrow (a+c)-(b+c)>0\Rightarrow a+c>b+c.$

6. $a>b,c>d\Rightarrow a+c>b+d$ .

Доказательство.

$\begin{array}{l} a>b\Rightarrow a-b>0,\\ c>d\Rightarrow c-d>0. \end{array}$

Сложение положительных чисел

$(a-b)+(c-d)>0\Rightarrow a+c>b+d.$

7. а) $a>b,c>0\Rightarrow ac>bc$ ,

б) $a>b,c<0\Rightarrow ac<bc$ .

Доказательство. $a>b\Rightarrow a-b>0$ . Пользуемся свойствами умножения положительных чисел.

Если , то $(a-b)c>0\Rightarrow ac-bc>0\Rightarrow ac>bc$ ,

если $c<0, то (a-b)c<0\Rightarrow ac-bc<0\Rightarrow ac<bc$ .

8. $a>b\ge0,c>d\ge0\Rightarrow ac>bd$ .

Доказательство.

$\left.\begin{array}{l} a>b,c>0\Rightarrow ac>bc,\\ c>d,b\ge0\Rightarrow bc\ge bd, \end{array}\right|\Rightarrow ac>bd.$

Следствие. $a>b\ge0,n\in\mathbb{N}\Rightarrow a^n>b^n$ .

Доказательство. Нужно перемножить неравенство раз.

9. $\displaystyle a>b,a,b>0\Rightarrow {1\over a}<{1\over b}$ .

Доказательство.

$\displaystyle\left.\begin{array}{l} \displaystyle {1\over a}-{1\over b}={b-a\over ab},\\[3mm] b-a<0,\ ( a>b),\\ ab>0 \end{array}\right|\Rightarrow {b-a\over ab}<0\Rightarrow {1\over a}<{1\over b}.$
- Для комментирования войдите или зарегистрируйтесь
Решений: 1
Неравенство Коши – Буняковского

$\displaystyle\sum_{i=1}^na_i^2\cdot\sum_{i=1}^nb_i^2\ge\left(\sum_{i=1}^na_ib_i\right)^2,$

В основе доказательства лежит утверждение, что дискриминант неотрицательной квадратичной функции неположителен.

Рассмотрим функцию

$\displaystyle f(x)=\sum_{i=1}^n(a_ix-b_i)^2=x^2\cdot\sum_{i=1}^na_i^2-2x\cdot \sum_{i=1}^na_ib_i+\sum_{i=1}^nb_i^2\ge 0.$

Неположительность дискриминанта этой функции и есть требуемое неравенство.

На неравенстве Коши основан один полезный прием оценки выражений вида $\displaystyle\sum_{i=1}^n{x_i\over y_i}$ :

$\displaystyle\sum_{i=1}^n{x_i\over y_i}\ge{\displaystyle\left(\sum_{i=1}^nx_i\right)^2\over \displaystyle\sum_{i=1}^nx_iy_i}\quad (x_1,x_2,\ldots ,x_n,y_1,y_2,\ldots ,y_n>0).$

Действительно,
$\begin{array}{l} \displaystyle\sum_{i=1}^n{x_i\over y_i}\cdot\sum_{i=1}^nx_iy_i=\sum_{i=1}^n \left(\sqrt{x_i\over y_i}\right)^2\cdot\sum_{i=1}^n \left(\sqrt{x_iy_i}\right)^2 \\[5mm] \displaystyle\ge\left(\sum_{i=1}^n\sqrt{x_i\over y_i}\cdot\sqrt{x_iy_i}\right)^2=\left(\sum_{i=1}^nx_i\right)^2. \end{array}$

Задачи.

1. Пусть $a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n$ — вещественные числа. Доказать, что

$\displaystyle\sqrt{\sum_{i=1}^na_i^2}+\sqrt{\sum_{i=1}^nb_i^2}\ge\sqrt{\sum_{i=1}^n(a_i+b_i)^2}$

(неравенство треугольника).

2. Пусть $a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n$ — вещественные числа. Доказать, что

$\displaystyle\left|\sqrt{\sum_{i=1}^na_i^2}-\sqrt{\sum_{i=1}^nb_i^2}\right| \le\sum_{i=1}^n|a_i-b_i|.$

3. Пусть $\alpha_1,\alpha_2,\ldots ,\alpha_n$ — вещественные числа. Доказать, что

$\displaystyle\left|\prod_{i=1}^n\sin\alpha_i+\prod_{i=1}^n\cos\alpha_i\right|\le 1.$

4. Пусть $a_k=\displaystyle{\sum_{i=1}^{100}}{i^k\over i+1}$ . Доказать, что

$a_k\cdot a_{k+2}>a_{k+1}^2.$

5. Пусть — положительные числа. Доказать, что

$\displaystyle {a\over 2b+c}+{b\over 2c+a}+{c\over 2a+b}\ge 1.$

6. Пусть — положительные числа. Доказать, что

$\displaystyle{a\over 2b+c}+{b\over 2c+d}+{c\over 2d+a}+{d\over 2a+b}\ge {4\over3}.$

7. Пусть $a_1,a_2,\ldots ,a_n$ — положительные числа. Доказать, что

$\displaystyle\sum_{i=1}^n{a_i\over a_{i+1}+a_{i+2}}\ge{\displaystyle\left( \sum_{i=1}^na_i\right)^2\over\displaystyle\sum_{i=1}^na_i(a_{i+1}+a_{i+2})}\quad (a_{n+1}=a_1,a_{n+2}=a_2).$
- Для комментирования войдите или зарегистрируйтесь
Линейное представление НОД. Простые и составные числа

Теорема. Пусть – целые числа, НОД. Число можно представить в виде

$d=am+bn,\mbox{ \rm где }m,n$ — целые числа

Доказательство. Пусть — множество всех чисел, которые можно получить из и с помощью сложения и вычитания. Тогда, если $x\in A,y\in A$ , то $x-y\in A,x+y\in A$ . Так как в алгоритме Евклида

$r_1=a-bq_1,r_2=b-r_1q_2,r_3=r_1-r_2q_3,\dots,r_n=r_{n-2}-r_{n-1}q_n,$

то

$r_1\in A\Longrightarrow r_2\in A\Longrightarrow r_3\in A\Longrightarrow\dots\Longrightarrow r_n\in A.$

Но .

Следствия.

1. НОД двух чисел делится на любой общий делитель этих чисел.

2. Уравнение , где — целые коэффициенты, — целочисленные неизвестные, разрешимо в том и только в том случае, если делится на НОД.

Простые и составные числа

Определение. Целое число называется составным, если оно делится на какое-нибудь целое число, отличное от и , 1 и -1.

Целое число называется простым, если оно не является составным и не равно $\pm1$ .

Теорема. Всякое составное натуральное число можно представить в виде произведения простых натуральных чисел.

Доказательство. Пусть есть такие составные натуральные числа, которые нельзя представить в виде произведения простых. Выберем из этих чисел самое маленькое и обозначим его через . Так как — составное число, то у него есть делитель , который больше 1 и меньше .

$\begin{array}{l} m\vdots a,\quad 1<a<m\\ m=ab,1<b<m. \end{array}$

Числа натуральные. Каждое из чисел либо является простым, либо это составное, меньшее , которое поэтому раскладывается на простые множители. Но тогда и раскладывается на простые множители. Получили противоречие.

Теорема. Если – целые числа, — простое число, $ab\vdots p$ , то $a\vdots p$ или $b\vdots p$ .

Доказательство. Пусть ни , ни не делятся на . Тогда
НОД,НОД. Следовательно, можно подобрать такие целые числа и и такие целые числа и , что

Перемножим эти равенства почленно:

Каждое слагаемое в левой части равенства делится на , а $1\not\vdots p$ . Получили противоречие.

Теорема. Пусть — составное натуральное число и

$n=p_1p_2\cdot\ldots\cdot p_k,\ n=q_1q_2\cdot\ldots\cdot q_l,$

где $p_1,\dots,p_k,q_1,\ldots,q_l$ — простые натуральные числа. Пусть

$p_1\le p_2\le\ldots\le p_k,\ q_1\le q_2\le\ldots\le q_l.$

Тогда и $p_1=q_1,p_2=q_2,\ldots,p_k=q_k$ .

Доказательство. $p_1p_2\ldots p_k=q_1q_2\ldots q_l$
Если в левой и правой части есть равные сомножители, сократим на них и получим равенство такого же вида, в котором ни один сомножитель в левой части не равен ни одному сомножителю в правой части (если не все сомножители сократятся).

Правая часть равенства делится на . Так как — простое число, то хотя бы один сомножитель в правой части делился на (по предыдущей теореме). В то же время все сомножители в правой части — это простые числа, не равные . Следовательно, они не делятся на . Противоречие.

Пусть

$a=p_1^{k_1}p_2^{k_2}\ldots p_s^{k_s},\ b=q_1^{l_1}q_2^{l_2}\ldots p_t^{l_t}$

— канонические разложения чисел и .

В каноническое разложение НОД входят те и только те простые числа, которые входят в оба разложения, причем из двух показателей выбирается меньший.

Простое число входит в каноническое разложение числа с показателем, равным

$\displaystyle\left[{n\over p}\right]+\left[{n\over p^2}\right]+\left[{n\over p^3}\right]+\left[{n\over p^4}\right]+\ldots,$

где суммирование ведется до тех пор, пока целая часть не станет равной нулю.

Задачи.

1. Доказать, что делится на 30 для любого целого .

2. Доказать, что $n^3+3n^2+5n+3\vdots3$ для любого целого .

3. Доказать, что сумма кубов трех последовательных чисел кратна 9.

4. Доказать, что для любого целого

$7\cdot5^{2n}+12\cdot 6^n\vdots19.$

5. Доказать, что для любого целого

$6^{2n}+19^n-2^{n+1}\vdots17.$

6. Доказать, что при любом простом натуральном число $p^2-1\vdots24$ .

7. Доказать, что для любого натурального

$4^{n}+15n-1\vdots9.$

8. Доказать, что для любого натурального нечетного

$n^3+3n^2-n-3\vdots48.$

9. Какие остатки могут давать при делении на 9 кубы целых чисел?

10. Доказать, что для любого натурального

$n^3+5n\vdots3.$

11. Доказать, что для любого натурального

$5^{n+2}+26\cdot5^{n}+8^{2n+1}\vdots59.$

12. Доказать, что ни при каком целом не делится на 169.

13. Доказать, что если $m^2+n^2\vdots3$ , то целые числа и также делятся на 3.

14. Доказать, что для любого целого

$n^5+4n^3+3n{ \rm и } n^4+3n^2+1$

не имеют общих делителей, отличных от 1.

15. Два двузначных числа, оканчивающихся одной и той же цифрой, таковы, что при делении на 9 частное каждого из них равно остатку другого. Найти все числа, удовлетворяющие этим условиям.

16. Доказать, что в любой из последовательностей

а) $2^2+1,4^2+1,6^2+1,8^2+1,\ldots$

б) $4^2+1,14^2+1,24^2+1,34^2+1,\ldots$

содержится бесконечно много составных чисел.

17. Разложить число $2^{1982}+1$ на два натуральных множителя, каждый из которых не меньше 1000.

18. Доказать, что число $4^{545}+545^4$ составное.

19*. Натуральные числа такие, что . Доказать, что число

— составное.

20. Доказать, что число $1010\ldots101$ ( нулей и единиц) составное $(k\ge2)$ .

21. Доказать, что число

$\underbrace{11\ldots1}_{n { \rm цифр } }2\underbrace{11\ldots1}_{n { \rm цифр }}$

(цифр там, где отмечено фигурной скобкой, по ) составное.

22. Представить в каноническом виде, найти НОД

а) 4828896 и 27147960;

б) 22754277 и 7484400.

23. Доказать, что для любого натурального

$10^{n}+45n-1\vdots27.$

24. Доказать, что для любого натурального

$3^{3n+2}+7^{n}\vdots10.$

25. Доказать, что нечетная степень 48, увеличенная на 1, кратна 7.

26. Найти все простые , для которых и также являются простыми.

27. Натуральные числа таковы, что ,

$a+b\vdots c,a+c\vdots b,b+c\vdots a.$

Доказать, что .

28. На какую наибольшую степень числа 3 делится произведение всех четных четырехзначных чисел?

источник; http://hijos.ru/
- Для комментирования войдите или зарегистрируйтесь
Метод математической индукции (ММИ)

Рассмотрим на примере, как работает метод.

Задача. Доказать, что для всех натуральных справедливо равенство

$\displaystyle {1\over 1\cdot2\cdot3}+{1\over 2\cdot3\cdot4}+\dots+{1\over n(n+1)(n+2)}= {n(n+3)\over 4(n+1)(n+2)}.$

Решение. Обозначим через левую часть равенства, а через — его правую часть.

1) Докажем сначала, что .

Доказательство.

$\begin{array}{l} \displaystyle s_1={1\over 1\cdot2\cdot3}={1\over 6}\\[3mm] \displaystyle z_1={1\cdot(1+3)\over 4\cdot(1+1)\cdot(1+2)}={1\cdot4\over 4\cdot2\cdot3}={1\over 6}. \end{array}$

2) Дано: . Нужно доказать: $s_{k+1}=z_{k+1}$ .

Доказательство.

$\begin{array}{l} \displaystyle z_k={k(k+3)\over 4(k+1)(k+2)}; z_{k+1}={(k+1)(k+4)\over 4(k+2)(k+3)}\\[3mm] \displaystyle s_{k+1}=s_k+{1\over (k+1)(k+2)(k+3)}=z_k+{1\over (k+1)(k+2)(k+3)}=\\[3mm] \displaystyle ={k(k+3)\over 4(k+1)(k+2)}+{1\over (k+1)(k+2)(k+3)}={k(k+3)^2+4\over 4(k+1)(k+2)(k+3)}=\\[3mm] \displaystyle ={k^3+9k+6k^2+4\over 4(k+1)(k+2)(k+3)}\\[3mm] \displaystyle z_{k+1}={(k+1)^2(k+4)\over 4(k+1)(k+2)(k+3)}={k^3+6k^2+9k+4\over 4(k+1)(k+2)(k+3)}\\[3mm] s_{k+1}=z_{k+1}. \end{array}$

Тем самым, утверждение доказано для любого , поскольку из его истинности для следует, что оно истинно для , из его истинности при следует его истинность для и т.д.

Предположим, что нам нужно доказать последовательность утверждений

$T_1,T_2,\dots,T_n,\dots$

Для того чтобы доказать все эти утверждения, достаточно доказать две теоремы:

1. — верное утверждение.

2. Если для какого-либо натурального верно утверждение , то верно и утверждение $T_{k+1}$ .

Такой способ доказательства последовательности утверждений называется методом математической индукции. Первая часть метода называетсябазой индукции, вторая — индукционным переходом.

Теорема. Если последовательности и таковы, что , и для любого натурального

$s_{k+1}-s_k=z_{k+1}-z_k,$

то для всех натуральных выполняется равенство .

С помощью метода математической индукции можно также доказывать неравенства.

Теорема. Если последовательности и таковы, что , и для любого натурального

$s_{k+1}-s_k>z_{k+1}-z_k,$

то для всех натуральных выполняется неравенство .

Пример. Доказать, что для всех натуральных $n\ge2$

$\displaystyle {1\over 1^2}+{1\over 2^2}+{1\over 3^2}+\dots+{1\over n^2}<2-{1\over n}.$

Доказательство.
1.

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

$\left.\begin{array}{l} \displaystyle s_2=1+{1\over 4}={5\over 4}\\[3mm] \displaystyle z_2=2-{1\over 2}={3\over 2} \end{array}\right|\Longrightarrow s_2<z_2$

2.

$\begin{array}{l} \displaystyle s_{k+1}-s_k={1\over (k+1)^2},\\[3mm] \displaystyle z_{k+1}-z_k=2-{1\over k+1}-\left(2-{1\over k}\right) ={1\over k}-{1\over k+1}={1\over k(k+1)},\\[3mm] s_{k+1}-s_k<z_{k+1}-z_k. \end{array}$

Теорема. Если последовательности и с положительными членами таковы, что , и для любого натурального

$\displaystyle {s_{k+1}\over s_k}>{z_{k+1}\over z_k},$

то для всех натуральных выполняется неравенство .

Задачи. Доказать

1. $\displaystyle 1^2+2^2+\dots+n^2={n(n+1)(2n+1)\over 6}$ .

2. $1+2+2^2+\dots+2^{n-1}=2^n-1$ .

3. $2!\cdot4!\times\dots\times(2n)!>[(n+1)!]^n$ при .

4. $\displaystyle 1+{1\over \sqrt{2}}+{1\over \sqrt{3}}+\dots+{1\over \sqrt{n}}>\sqrt{n}$ при $n\ge2$ .

5. Доказать, что сумма всевозможных произведений квадратов натуральных чисел, взятых по два (от 1 до ), равна

$\displaystyle {n(n^2-1)(4n^2-1)(5n+6)\over 360}.$

6. Доказать, что для всех натуральных

$\sqrt{\displaystyle\underbrace{4+\sqrt{4+\sqrt{4+\dots+\sqrt{4}}}}_{n}}<3$ (четверок — ).

7. Доказать, что для всех натуральных

$\displaystyle 1^5+2^5+\dots+n^5={1\over 12}n^2(n+1)^2(2n^2+2n-1).$

8. Доказать, что для всех натуральных

$\displaystyle {1^2\over 1\cdot3}+{2^2\over 3\cdot5}+\dots+{n^2\over(2n-1)(2n+1)}={n(n+1)\over 2(2n+1)}.$

9. Доказать, что для всех натуральных $\displaystyle2^{n-1}\cdot n!\le n^n.$

10. Доказать, что сторона правильного вписанного в окружность -угольника выражается формулой
$a_{2^n}=R\sqrt{2-\sqrt{\displaystyle\underbrace{2+\sqrt{2+\dots+\sqrt{2}}}_{n-2}}},$ где — радиус этой окружности (двоек — ).

11. Доказать, что прямых, пересекающихся в одной точке и лежащих в одной плоскости, делят эту плоскость на частей.

12. Доказать, что различных прямых, лежащих в одной плоскости, разбивают эту плоскость на области, которые могут быть закрашены красной и синей краской так, что все смежные области (т.е. области, имеющие общий отрезок прямой) будут закрашены разными красками.

13. Доказать, что если $S_1,S_2,S_3,\dots,S_n$ — суммы членов геометрических прогрессий, у которых первые члены 1, а знаменатели соответственно равны $1,2,3,\dots,n$ , то

$S_1+S_2+2S_3+3S_4+\dots+(n-1)S_n=1^n+2^n+3^n+\dots+n^n.$

14. Доказать, что сумма всех членов каждой горизонтальной строки таблицы

$\begin{array}{lllllll} 1&&&&&&\\ 2&3&4&&&&\\ 3&4&5&6&7&&\\ 4&5&6&7&8&9&10\\ \dots&&&&&& \end{array}$

равна квадрату нечетного числа.

15. Доказать, что произведение

$ P=(1+2)(3+4+5)(6+7+8+9)\ldots, $

состоящее из сомножителей, равно

$\displaystyle {(n!)^3(n+1)^2(n+2)\over 2^{n+1}}. $

16. Доказать, что сумма всевозможных парных произведений натуральных чисел $1,2,\ldots,n$ равна

$\displaystyle {(n-1)n(n+1)(3n+2)\over 24}. $

17. Доказать, что для любого натурального

$\displaystyle {4^n\over n+1}<{(2n)!\over (n!)^2}. $

источник: http://hijos.ru/izuchenie-matematiki/algebra-10-klass/2-metod-matematich...
- Для комментирования войдите или зарегистрируйтесь
Целые числа. Делимость

Определение. Пусть и — целые числа. Говорят, что число делится на число , если можно представить в виде , где – целое число.
Обозначение. $a\vdots b$ .

Теорема. Пусть – целые числа. Тогда

1. $a\vdots m,b\vdots m\Longrightarrow (a+b)\vdots m,(a-b)\vdots m$ ;

2. $a\vdots m\Longrightarrow ab\vdots m$ ;

3. $a\vdots b,b\vdots c\Longrightarrow a\vdots c$ .

Доказательство.

1. Так как $a\vdots m$ , то – целое;
так как $b\vdots m$ , то – целое.

Следовательно,
, где – целое число;
, где – целое число.

Значит, $(a+b)\vdots m,(a-b)\vdots m$ .

Наибольший общий делитель

Определение. Говорят, что — делитель , если $a\vdots b$ .

Определение. Число называется общим делителем чисел и , если оно является как делителем , так и делителем .

Определение. Самый большой из всех общих делителей и называется их наибольшим общим делителем.

Обозначение. НОД, GCD, gcd или просто .

Теорема о делении с остатком. Пусть – целое число, – натуральное. Тогда существует единственная пара чисел , удовлетворяющих условиям

1. – целые числа;

2. ;

3. $0\le r\le b$ .

Доказательство.

Существование.

Пусть $q=\left[{a\over b}\right]$ — целая часть числа ${a\over b}$ , т.е. наибольшее целое число, не превосходящее ${a\over b}$ . Тогда

$\begin{array}{l} \displaystyle q\le{a\over b}<q+1,\\[2mm] bq\le a<bq+b,\\[1mm] 0\le a-bq<b. \end{array}$

Пусть . Найденные и удовлетворяют всем условиям теоремы.

Единственность.

Предположим, что нашлась другая пара чисел , удовлетворяющая тем же условиям. Тогда
$\begin{array}{l} bq+r=bq’+r’\\ bq-bq’=r’-r\\ b(q-q’)=r’-r. \end{array}$
Если $q\ne q’$ , то левая часть этого равенства по модулю не меньше . В то же время правая часть по модулю меньше , так как $0\le r$ . Получили противоречие. Значит, . Следовательно, $\Longrightarrow$ .

Значит, — та же пара чисел, что и .

Число называется остатком от деления на , — неполным частным.

Алгоритм Евклида

Древнегреческая геометрия достигла своего апогея в III в. до н.э. в работах знаменитого математика Евклида, написавшего 13 книг, объединенных общим названием “Начала”. В трудах Евклида логическая сторона геометрии была доведена до очень высокого уровня.

Однажды на вопрос царя Птолемея I Сотера (305–283 до н.э.), — не существует ли более короткого пути для изучения геометрии, чем штудирование “Начал”, — Евклид сказал в ответ: “В геометрии нет царского пути!” В Египте же того времени были две системы дорог: одна для царя и его курьеров, другая для всего населения.

В другой раз один из учеников, выучив первое предложение “Начал”, спросил Евклида: “А что я могу заработать, выучив все это?” Евклид позвал своего раба и сказал: “Дай ему три обола, так как бедняжка хочет заработать деньги своим учением (Примечание. Обол — мелкая серебряная монета в Древней Греции.)”.

Из ответов Евклида видно, что величайший геометр требовал должного уважения и даже благоговения к математике.

Лемма. Пусть , где – целые числа. Тогда любой общий делитель чисел и является общим делителем чисел и . Обратно: любой общий делитель чисел и является общим делителем чисел и .
$\begin{array}{ll} a=bq_1+r_1,&0\le r_1< b,\\ b=r_1q_2+r_2,&0\le r_2<r_1,\\ r_1=r_2q_3+r_3,&0\le r_3<r_2\\ \ldots&\\ r_{n-2}=r_{n-1}q_n+r_n,&0\le r_n<r_{n-1},\\ r_{n-1}=r_nq_{n+1}& \end{array}$

Пусть – натуральные числа. Разделим на с остатком. Если $r_1\ne0$ , то разделим на с остатком. Если $r_2\ne0$ , то разделим на с остатком и т.д. Этот процесс оборвется, так как каждый следующий остаток меньше предыдущего и неотрицателен. Так что некоторый остаток $r_{n-1}$ разделится на остаток без остатка.

Из леммы следует, что
НОД НОДНОД $(r_1,r_2)=\dots=$ НОД $(r_{n-1},r_n)=r_n$ .

Пример. Найти НОД.

$\begin{tabular}{l|l} 7007&4459\\ \cline{2–2} 4459&1\\ \cline{1–1} \end{tabular}$

$\begin{tabular}{l|l} 4459&2548\\ \cline{2–2} 2548&1\\ \cline{1–1} \end{tabular}$

$\mbox{}\hskip8.25cm\begin{tabular}{l|l} 2548&1911\\ \cline{2–2} 1911&1\\ \cline{1–1} \end{tabular}$

$\mbox{}\hskip7.3cm\begin{tabular}{r|l} 1911&637\\ \cline{2–2} 1911&3\\ \cline{1–1} 0& \end{tabular}$

Ответ. НОД.

Задача.Найти НОД.

Задачи

.

1. Доказать теорему.

2. Найти НОД.

3. Найти НОД $(2^{40}-1,2^{30}-1)$ .

4. Доказать, что для всех натуральных несократима дробь

$\displaystyle{6n+5\over 9n+7}.$
- Для комментирования войдите или зарегистрируйтесь
Функциональные уравнения

Функциональное уравнение — это уравнение, в котором неизвестными являются функции (одна или несколько). Например,

$\begin{array}{l} f(x)+xf(x+1)=1,\\[2mm] \displaystyle f(x)+g(1-x)=f\left( g\left({2\over x+1}\right)\right). \end{array}$

Решить функциональное уравнение — значит, найти неизвестную функцию, при подстановке которой в исходное функциональное уравнение оно обращается в тождество (если неизвестных функций несколько, то необходимо найти их все).

Соотношения, задающие функциональные уравнения, являются тождествами относительно некоторых переменных, а уравнениями их называют потому, что неизвестные функции — искомые.

Многие функциональные уравнения содержат несколько переменных. Все эти переменные, если на них не наложены какие-то ограничения, являются независимыми.

Всегда четко должно быть оговорено, на каком множестве функциональное уравнение задается, т.е. какова область определения каждой неизвестной функции. Общее решение функционального уравнения может зависеть от этого множества.

Кроме области определения функций, важно знать, в каком классе функций ищется решение. Количество и поведение решений очень строго зависит от этого класса.

Вообще для функциональных уравнений, не сводящихся к дифференциальным или интегральным, известно очень мало общих методов решения. Рассмотрим основные приемы, помогающие найти решения таких уравнений.

Идея непрерывности

Определение. Функция называется непрерывной в точке , если выполняются следующие два условия:

1) точка принадлежит области определения функции $(x_0\in D_f)$ ;

2) $\displaystyle\lim_{x\to x_0}f(x)=f(x_0)$ , разумеется, в предположении, что этот предел существует.

Если хотя бы одно из этих условий нарушается, функция не является непрерывной в точке , она будет разрывной в этой точке.

Определение. Функция называется непрерывной на отрезке , если она непрерывна во всех точках этого отрезка.

Справедлива следующая теорема:

Теорема Больцано — Коши. Если функция непрерывна на отрезке и на концах этого отрезка принимает неравные значения и , то она принимает все промежуточные между и значения на отрезке .

Пример 1. Функция непрерывна на всей вещественной прямой и удовлетворяет равенству для всех . Доказать, что уравнение имеет хотя бы одно решение.

Решение. Рассмотрим функцию . Предположим, что $f(x)\ne x$ для всех . Тогда в силу непрерывности либо для всех , либо для всех . (Если бы существовали такие и , что , то по теореме Больцано — Коши, внутри отрезка была бы точка, в которой обращалась бы в нуль, что противоречит предположению.

Пусть для определенности , то есть для всех . Обозначим . Тогда, так как , то , что противоречит тому, что . Значит, при некотором имеем .

Пример 2. Функция задана на всей вещественной оси, причем выполняется равенство

Доказать, что не может быть непрерывной.

Решение. Функция не может принимать значение . Действительно, при имеем . Значит, для всех или . Выразим из нашего равенства :

$\displaystyle f(x+1)=-{1\over f(x)+1}.$

Значит, неравенство невозможно, иначе .

Если же , то должно выполняться неравенство $\displaystyle -{1\over f(x)+1}>-1$ , откуда и

$\displaystyle f(x+2)=-{1\over f(x+1)+1}=-{1\over -{1\over f(x)+1}+1}=-{f(x)+1\over f(x)}= -\left(1+{1\over f(x)}\right).$

следовательно, получаем, что . Противоречие.

Пример 3. Найти все непрерывные функции , удовлетворяющие соотношению для любого .

Решение. В данное уравнение подставим вместо (это можно сделать, так как функция определена для всех ), и еще несколько раз проделаем то же самое, получим

$\displaystyle f(x)=f\left({x\over 2}\right)=f\left({x\over 4}\right)=\ldots=f\left({x\over 2^n}\right)=\ldots$

По непрерывности функции в нуле имеем

$\displaystyle f(x)=\lim_{n\to\infty}f(x)=\lim_{n\to\infty}f\left({x\over 2^n}\right)=f\left(\lim_{n\to\infty}{x\over 2^n}\right)=f(0).$

Получили, что , то есть функция — постоянная.

Уравнения Коши

1. Уравнение

в классе непрерывных функций имеет решение .

Такое же решение оно имеет и в классе монотонных функций.

2. Уравнение

в классе непрерывных функций имеет решение (если не считать $f(x)\equiv0)$ .

3. Уравнение

$f(xy)=f(x)+f(y),\qquad x,y>0$

в классе непрерывных функций имеет решение $f(x)=\log_ax$ (если не считать $f(x)\equiv0$ ).

4. Уравнение

$f(xy)=f(x)f(y),\qquad x,y>0$

в классе непрерывных функций имеет решение (если не считать $f(x)\equiv0$ ).

Метод сведения функционального уравнения к известному с помощью замены переменной и функции

Пример 4. Найти все непрерывные функции, удовлетворяющие уравнению

Решение. В качестве вспомогательной функции возьмем функцию

Подставляя в исходное уравнение , получаем

$\begin{array}{l} g(x+y)+(x+y)^2=g(x)+x^2+g(y)+y^2+2xy,\\ g(x+y)=g(x)+g(y), \end{array}$
то есть функция удовлетворяет первому уравнению Коши, откуда .

Пример 5. Найти все непрерывные функции $f:(0,+\infty)\to\mathbb{R}$ , удовлетворяющие уравнению

Решение. Поделим уравнение на , получим

$\displaystyle {f(xy)\over xy}={f(y)\over y}+{f(x)\over x}.$

Введем вспомогательную функцию $\displaystyle g(x)={f(x)\over x}$ , тогда получим уравнение

то есть функция удовлетворяет третьему уравнению Коши, откуда $f(x)=x\log_ax$ .

Метод подстановок

Пример 6. Найти все решения функционального уравнения

$f(xy)=y^kf(x)\qquad(k\in\mathbb{N}).$

Решение. Положим , имеем . Поскольку произвольно, то .

Пусть теперь $x\ne0$ . Подставив в уравнение , получим

$\displaystyle f(1)=\left({1\over x}\right)^kf(x),$

откуда , где .

Нетрудно убедиться, что эта функция действительно удовлетворяет исходному функциональному уравнению.

Пример 7. Пусть $a\ne\pm1$ — некоторое вещественное число. Найти функцию , определенную при всех $x\ne1$ и удовлетворяющую уравнению

$\displaystyle f\left({x\over x-1}\right)=af(x)+\varphi(x),$

где $\varphi(x)$ — заданная функция, определенная при всех $x\ne1$ .

Решение. При замене $\displaystyle x\to{x\over x-1}$ выражение $\displaystyle {x\over x-1}$ переходит в . Получаем систему уравнений

$\left\{\begin{array}{l} \displaystyle f\left({x\over x-1}\right)=af(x)+\varphi(x),\\[3mm] \displaystyle f(x)=af\left({x\over x-1}\right)+\varphi\left({x\over x-1}\right), \end{array}\right.$

решением которой при $a^2\ne1$ является функция

$\displaystyle f(x)={a\varphi(x)+\varphi\left({x\over x-1}\right)\over 1-a^2}.$

Предельный переход

Пример 8. Функция $f:\mathbb{R}\to\mathbb{R}$ непрерывна в точке и $\forall x\in\mathbb{R}$ выполняется равенство

Найти все такие .

Решение. Пусть функция удовлетворяет условию задачи. Тогда

$\begin{array}{l} \displaystyle f(x)={1\over 2}f\left({x\over 2}\right)+{x\over 4}={1\over 2}\left({1\over 2}\left( f\left({x\over 4}\right)+{x\over 8}\right)\right)+{x\over 4}=\\[3mm] \displaystyle ={1\over 4}f\left({x\over 4}\right)+{x\over 16}+{x\over 4}=\ldots={1\over 2^n}f\left({1\over 2^n}\right)+{x\over 2^{2n}}+{x\over 2^{2n-2}}+\dots+{x\over 4}=\\[3mm] \displaystyle =\lim_{n\to\infty}{1\over 2^n}f\left({1\over 2^n}\right)+\lim_{n\to\infty}\sum_{k=1}^n{x\over 4^k}={x\over 3}. \end{array}$

Проверка показывает, что действительно является решением.

Пример 9. Найти функцию , ограниченную на любом конечном интервале и удовлетворяющую уравнению

$\displaystyle f(x)-{1\over 2}f\left({x\over 2}\right)=x-x^2.$

Решение. $x=0\Rightarrow f(x)=0$ .

$\begin{array}{l} \displaystyle {1\over 2}f\left({x\over 2}\right)-{1\over 4}f\left({x\over 4}\right)={x\over 4}-{x^2\over 8},\\[3mm] \displaystyle {1\over 4}f\left({x\over 4}\right)-{1\over 8}f\left({x\over 8}\right)={x\over 16}-{x^2\over 64},\\[3mm] \ldots,\\ \displaystyle {1\over 2^n}f\left({1\over 2^n}\right)-{1\over 2^{n+1}}f\left({x\over 2^{n+1}}\right)={x\over 4^n}-{x\over 8^n}. \end{array}$

Сложим все эти равенства:

$\displaystyle f(x)-{1\over 2^{n+1}}f\left({x\over 2^{n+1}}\right)=$

$\displaystyle =x\left(1+{1\over 4}+{1\over 4^2}+\dots+{1\over 4^n}\right)-x^2\left(1+{1\over 8}+{1\over 8^2}+\dots+{1\over 8^n}\right) .$

Перейдем к пределу при $n\to\infty$ . Учитывая ограниченность в нуле и то, что , получаем

$\displaystyle f(x)={4\over 3}x-{8\over 7}x^2.$

Производная и функциональные уравнения

Пример 10. Найти все вещественные дифференцируемые функции , удовлетворяющие уравнению

$\displaystyle f(x+y)={f(x)+f(y)\over 1-f(x)f(y)}.$

Решение. Пусть . Имеем $\displaystyle f(0)={2f(0)\over 1-f^2(0)}$ , откуда .

После преобразований имеем

$\displaystyle {f(x+h)-f(x)\over h}={f(h)\over h}\cdot{1+f^2(x)\over 1-f(x)f(h)} .$

Переходим к пределу при $h\to0$ , учитывая, что $\displaystyle \lim_{h\to0}f(h)=0$ , получаем

$f^{\prime}(x)=c(1+f^2(x)) ,$

где $c=f^{\prime}(0)$ . Интегрируем:

$\displaystyle \int{dy\over 1+y^2}=\int cdx,$

откуда ${\rm arctg}\, f(x)=cx+c_1$ и $f(x)={\rm tg}\, (cx+c_1)$ . Так как , то , и $f(x)={\rm tg}\, (cx)$ .

Проверкой убеждаемся, что все эти функции — решения исходного уравнения.

Пример 11. Найти все функции , являющиеся решениями уравнения

$f^{\prime}(x)+xf(-x)=ax,\quad x\in\mathbb{R},\ a=const$

Решение. $x\to-x$ : $f^{\prime}(-x)-xf(x)=-ax$ .

Введем новые функции:

$\displaystyle F(x)={f(x)+f(-x)\over 2},\ G(x)={f(x)-f(-x)\over 2}.$

Функция — четная, а — нечетная, , и для этих функций имеем

$\begin{array}{cc} G^{\prime}(x)-xG(x)=0&F’(x)+xF(x)=ax,\\[3mm] \displaystyle G(x)=ce^{x^2\over 2}&F(x)=a+Ae^{-{x^2\over 2}}. \end{array}$

Поскольку , то $G(x)\equiv0$ и $\displaystyle f(x)=a+Ae^{-{x^2\over 2}}$ .

Проверкой убеждаемся, что все такие — действительно решение.

Решение функциональных уравнений на множестве натуральных чисел

Пример 12. Каждому натуральному числу поставлено в соответствие целое неотрицательное число так, что выполняются следующие условия:

1) для любых двух натуральных чисел и ;

2) , если последняя цифра в десятичной записи числа равна ;

3) .

Доказать, что для любого натурального .

Решение. Поскольку , , $f(5)\ge0$ , $f(2)\ge0$ , то .

Любое натуральное число можно представить в виде , где Н.О.Д., иначе $b=10l\pm1$ или $b=10l\pm3$ . Отсюда $b^4\equiv1\pmod{10}$ или . , откуда .

Задачи

1. $\forall x,y\in\mathbb{R}$

Найдите , если .

2. Найти все непрерывные функции такие, что

3. Пусть $X=\mathbb{R}\setminus\{0,1\}$ . Найти все вещественнозначные функции на :

$\displaystyle f(x)+f\left( 1-{1\over x}\right)=1+x\ \forall x\in X.$

4. Найдите все функции такие, что

$\displaystyle 3f(-x)+f\left({1\over x}\right)+f(x)=x.$

5. Найти все непрерывные функции , удовлетворяющие уравнению

$\displaystyle f(x)=x(x+1)+f\left({x\over 2}\right).$

6. Решите уравнение

7. Найдите решение уравнения

, если

— постоянная, в классе функций натурального аргумента.

8. Найти все полиномы : и

9. Существует ли непрерывная функция , определенная на всей вещественной оси $\mathbb{R}$ , такая, что $f(f(x))=e^{-x}$ для всех $x\in\mathbb{R}$ ?

10. Пусть функция $f:[a,b]\to\mathbb{R}$ при всех $x,y\in[a,b]$ удовлетворяет соотношению

$|f(x)-f(y)|\le M|x-y|^{\alpha},\qquad M>0,\alpha>1.$

Докажите, что — постоянная функция.

11. Найдите непрерывно-дифференцируемое решение функционального уравнения

$\displaystyle f(x+y)=f(x)+f(y)+xy\left({x^2\over 3}+{xy\over 2}+{y^2\over 3}\right),\quad x,y\in\mathbb{R},$

удовлетворяющее условию .

12. В предположении, что существует единственная функция , такая, что

$\displaystyle f(0)=1,\ f^{\prime}(x)=f(x)+\int_0^1f(t)dt,$

надите ее.

13. Пусть $\alpha\in\mathbb{R}$ . Найдите все непрерывные функции $f:[0,1]\to(0,+\infty)$ :

$\displaystyle \int_0^1f(x)dx=1,\int_0^1xf(x)dx=\alpha,\int_0^1x^2f(x)dx=\alpha^2.$

14. Найдите все дважды дифференцируемые функции $f:\mathbb{R}\to\mathbb{R}$ такие, что

источник: http://hijos.ru/
- Для комментирования войдите или зарегистрируйтесь
Теорема Вильсона

Теорема. Число  — простое тогда и только тогда, когда выполняется сравнение

$(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^{n-1}-1$ на ?

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

9. Докажите, что уравнение

не имеет целых решений.

10. Пусть число  — простое, . Докажите, что

$\left[\left(\frac{p-1}{2}\right)!\right]^2-1\vdots p;$

если же  — простое, , докажите, что

$\left[\left(\frac{p-1}{2}\right)!\right]^2+1\vdots p.$

11. Натуральное число $n\vdots24$ . Докажите, что сумма всех натуральных делителей числа  (включая  и ) также делится на .

12. Найдите остаток от деления целой части числа $\displaystyle\frac{10^{20000}}{10^{100}+3}$ на .

13. Найдите все решения уравнения

$x^{n+1}-(x+1)^{n}=2001$

в натуральных числах .
- Для комментирования войдите или зарегистрируйтесь
Примеры решения нелинейных уравнений

1. Решить уравнение в натуральных числах

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

Представим  в виде произведения двух натуральных множителей всеми возможными способами:

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

Приравниваем один из множителей слева одному, другой — другому. Решаем полученные системы. Возможно упрощение: здесь числа и  одинаковой четности.

Ответ. .

Замечание. При поиске целых решений рассматривали бы также разложения $(-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. Доказать, что уравнение  не имеет целых решений.

Решение. Сравнения по модулю : $-y^2\equiv1\pmod{3}$ , что невозможно, так как квадраты целых чисел при делении на  могут давать остатки либо , либо .
- Для комментирования войдите или зарегистрируйтесь