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}<br />
(a+b+c)^2=a^2+b^2+c^2+2(ab+ac+bc)\Rightarrow2(ab+ac+bc)\vdots m,\\<br />
4(ab+bc+ac)^2=4(a^2b^2+a^2c^2+b^2c^2)+8abc(a+b+c),<br />
\end{array}
откуда

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

и

\begin{array}{l}<br />
2(a^2b^2+a^2c^2+b^2c^2)\vdots m,\\<br />
a^4+b^4+c^4=a^2+b^2+c^2)^2-2(a^2b^2+a^2c^2+b^2c^2)<br />
\Rightarrow\\<br />
a^4+b^4+c^4\vdots m.<br />
\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}, \nod(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

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

10. Пусть число p — простое, p=4n+3. Докажите, что

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

если же p — простое, p=4n+1, докажите, что

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

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

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

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

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

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

Комментариев: 2

  1. 1 Zhumakhan:

    Лучше чем учетеля

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо :-)

    [Ответить]

Оставьте свой отзыв

Добавить изображение