Теория чисел: приёмы: формулы

В задачах про целые числа ищут оценку («не больше») и пример, где оценка достигается; опираются на делимость, остатки и перебор делителей.

Подходит для: ЕГЭ профиль, ЕГЭ база. Раздел: алгебра.

• $$f\le M\ \text{и пример с } f=M\ \Rightarrow\ \max f=M$$схема «оценка плюс пример»: нужны обе части, иначе ответ не доказан
• $$xy=N\ \Rightarrow\ (d,\ N/d)$$пары множителей перебирают по делителям $d\le\sqrt{N}$, не забывая про отрицательные при целых $x$, $y$
• $$xy+px+qy=c\iff(x+q)(y+p)=c+pq$$разложение на множители для целых решений
• $$a\mid x\ \text{и}\ a\mid y\Rightarrow a\mid(x\pm y)$$делимость суммы и разности; если $a\mid x$, $a\nmid y$, то $a\nmid(x+y)$
• $$x=x_0+\dfrac{b}{d}t,\quad y=y_0-\dfrac{a}{d}t$$все целые решения $ax+by=c$ по частному решению $(x_0,y_0)$, $d=\text{НОД}(a,b)$, $t\in\mathbb{Z}$
• $$x^{2}-y^{2}=(x-y)(x+y)$$множители одной чётности, поэтому $N=x^{2}-y^{2}$ в целых числах невозможно при $N=4k+2$
• $$n^{2}<m^{2}<(n+1)^{2}$$между квадратами соседних натуральных чисел нет квадрата
• $$S\ge\dfrac{n(n+1)}{2}$$наименьшая сумма $n$ различных натуральных чисел ($1,2,\ldots,n$)
• $$x_1+\ldots+x_n=n\bar{x}$$если известно среднее арифметическое, то известна сумма; при целых числах сумма целая
• $$\left\lfloor\dfrac{b}{k}\right\rfloor-\left\lfloor\dfrac{a-1}{k}\right\rfloor$$сколько чисел, кратных $k$, среди целых от $a$ до $b$
• $$\left\lfloor\dfrac{n}{5}\right\rfloor+\left\lfloor\dfrac{n}{25}\right\rfloor+\left\lfloor\dfrac{n}{125}\right\rfloor+\ldots$$число нулей на конце $n!$
• $$a_n=a_1+d(n-1),\quad S_n=\dfrac{a_1+a_n}{2}n$$прогрессии часто встречаются в «числовых» задачах: подбор $n$ из неравенств и делимости
• $$a^{n}-b^{n}\ \vdots\ (a-b)$$делимость разности степеней; $a^{n}+b^{n}\ \vdots\ (a+b)$ при нечётном $n$
• $$n=mk+r,\ r\in\{0,\ldots,m-1\}$$перебор остатков по модулю $m$: рассматривают каждый случай отдельно
• $$ax+by=c\ \text{разрешимо в целых}\iff\text{НОД}(a,b)\mid c$$линейное диофантово уравнение
• $$n+1\to n$$если $n+1$ предмет разложить в $n$ ящиков, в каком-то окажется не менее двух предметов (принцип Дирихле)