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

1. Целые числа

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

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

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

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

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

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

1. Если в равенстве a+b=c два числа делятся на , то и третье число делится на .

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

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

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

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

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

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

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

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

Теорема (Эйлер). Для любых натуральных взаимно простых и 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} .$

То же для и . 2,3,5 — числа попарно взаимно простые.

4. Примеры решения нелинейных уравнений

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

4x^2-y^2=28 .

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

(2x-y)(2x+y)=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=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. Доказать, что уравнение 3x^2-4y^2=13 не имеет целых решений.

Решение. Сравнения по модулю : $-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. а) При каких натуральных значениях число 3^n-1 делится на ?

б) Докажите, что число $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. Решите уравнения в целых числах:

а) 3x^2+2xy-y^2=4 ; б) 3xy+16x+13y+61=0 .

7. Пусть — целое число, n>1 . Делится ли $n^{n-1}-1$ на (n-1)^2 ?

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

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

m^2+3mn-2n^2=122