Целые числа | Математика, которая мне нравится

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} (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}$

откуда

$2(ab+bc+ac)^2=2(a^2b^2+a^2c^2+b^2c^2)+4abc(a+b+c)$

$\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}$

Теорема. Всякое целое $a$ представляется единственным способом с помощью целого $b\ne0$ равенством вида $a=bq+r$ , где $q,r$ — целые, $0\le r<|b|$ . Число $q$ называется частным, $r$ — остатком от деления $a$ на $b$ .

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

Решение. Числа, делящиеся на $8$ , имеют вид $8k$ , $k\in\mathbb{Z}$ , а при делении на $12$ дающие в остатке $10$ , — вид $12l+10$ , $l\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$ тогда и только тогда, когда $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}$ , Н.О.Д. $(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}}.$

Решение. По условию, $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}),$

остается доказать, что второй множитель делится на $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$ и $c$ . $2,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$