МАТЕМАТИЧНІ ШКІЛЬНІ ОЛІМПІАДИ.: Олімпіадні задачі на властивості цілих чисел(рос. мова)

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

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

Определение. Пусть a,b

— целые числа. Говорят, что число

делится на

, если

можно представить в виде a=nb

, где

— целое число.

Иначе:

— делитель

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

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

Пусть

— целые числа, число

— простое.

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

, где

— целые, $0\le r<|b|$ . Число

называется частным,

— остатком от деления

на

Пример. Может ли число делиться на

, а при делении на

давать в остатке

Решение. Числа, делящиеся на 8, имеют вид

, $k\in\mathbb{Z}$ , а при делении на

дающие в остатке

, — вид

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

Теорема (Эйлер). Для любых натуральных взаимно простых

выполняется

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

То же для

— числа попарно взаимно простые.

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

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

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

Представим

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

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

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

одинаковой четности.

Ответ. x=4,y=6

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

число

делится на

б) Докажите, что число $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>1

. Делится ли $n^{n-1}-1$ на (n-1)^2

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

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