Практика
Докажите, что \(n^2+n\) чётно при любом целом \(n\).
Вынесите \(n\).
\(n^2+n=n(n+1)\). Из двух соседних чисел одно чётно, значит произведение чётно.
Найдите последнюю цифру \(2^{2026}\).
Цикл последних цифр степеней \(2\): \(2,4,8,6\).
Так как \(2026\equiv2\pmod4\), последняя цифра равна \(4\).
Докажите, что любые два соседних нечётных числа взаимно просты или имеют НОД \(2\)? Исправьте формулировку и докажите верное утверждение.
Два нечётных числа не могут быть соседними целыми; вероятно, речь о числах, отличающихся на \(2\).
Верная формулировка: любые два нечётных числа, отличающиеся на \(2\), взаимно просты или имеют общий делитель? Пусть числа \(n\) и \(n+2\), где \(n\) нечётно. Их общий делитель делит \(2\). Так как оба числа нечётны, общий делитель не делится на \(2\). Значит НОД равен \(1\).
Какие остатки может давать квадрат целого числа по модулю \(3\)?
Проверьте \(0,1,2\).
Если \(n\equiv0,1,2\pmod3\), то \(n^2\equiv0,1,1\pmod3\). Возможны только \(0\) и \(1\).
Найдите цифру \(x\), если число \(72x5\) делится на \(9\).
Сумма цифр должна делиться на \(9\).
Сумма цифр равна \(7+2+x+5=14+x\). Нужно \(14+x\equiv0\pmod9\). Так как \(x\) — цифра, \(x=4\).
Докажите, что \(24\mid n(n+1)(n+2)(n+3)\) для любого целого \(n\).
Докажите делимость на \(8\) и на \(3\).
Среди четырёх последовательных чисел одно делится на \(3\). Также среди них есть два чётных, причём одно из них делится на \(4\), поэтому произведение делится на \(8\). Так как \(8\) и \(3\) взаимно просты, произведение делится на \(24\).
Решите в натуральных числах \(xy+x+y=47\).
Добавьте \(1\).
Получаем \((x+1)(y+1)=48\). Пары делителей \(48\), большие \(1\), дают \((x,y)=(1,23),(2,15),(3,11),(5,7),(7,5),(11,3),(15,2),(23,1)\).
Найдите \(\gcd(n^2+n+1,n+1)\).
Замените \(n\) на \(-1\) по модулю \(n+1\).
По модулю \(n+1\) имеем \(n\equiv-1\). Тогда \(n^2+n+1\equiv1-1+1=1\). Значит общий делитель делит \(1\), и НОД равен \(1\).
Докажите, что уравнение \(x^2=3y^2\) не имеет решений в натуральных числах.
Если \(3\mid x^2\), то \(3\mid x\).
Из \(x^2=3y^2\) следует \(3\mid x^2\), значит \(3\mid x\). Пусть \(x=3t\). Тогда \(9t^2=3y^2\), откуда \(y^2=3t^2\), значит \(3\mid y\). Получили меньшее решение \((t,\frac{y}{3})\). Повторяя, получаем бесконечное деление на \(3\), невозможное для натуральных чисел.
Найдите все натуральные \(n\), для которых \(n+3\mid n^2+2\).
По модулю \(n+3\): \(n\equiv-3\).
Имеем \(n^2+2\equiv9+2=11\pmod{n+3}\). Поэтому \(n+3\mid11\). Так как \(n\ge1\), \(n+3\ge4\), значит \(n+3=11\), \(n=8\). Проверка проходит.
Найдите последние две цифры \(11^{2025}\).
Проверьте закономерность \(11^k\pmod{100}\).
Для \(k=1,\ldots,10\) получаем \(11,21,31,\ldots,91,01\), то есть цикл длины \(10\). Так как \(2025\equiv5\pmod{10}\), последние две цифры равны \(51\).
Решите систему \(n\equiv2\pmod5\), \(n\equiv3\pmod7\).
Пусть \(n=5k+2\).
Подставим: \(5k+2\equiv3\pmod7\), значит \(5k\equiv1\pmod7\). Обратный к \(5\) по модулю \(7\) равен \(3\), поэтому \(k\equiv3\pmod7\). Тогда \(n=5(7t+3)+2=35t+17\).
Найдите все \(n\pmod3\), для которых \(3\mid n^2+n+1\).
Проверьте остатки \(0,1,2\).
При \(n\equiv0\) получаем \(1\), при \(n\equiv1\) получаем \(3\equiv0\), при \(n\equiv2\) получаем \(7\equiv1\pmod3\). Значит подходит только \(n\equiv1\pmod3\).
Пусть нечётное простое \(p\) делит \(a^2+1\). Докажите, что \(p\equiv1\pmod4\).
Из \(a^2\equiv-1\pmod p\) следует \(a^4\equiv1\pmod p\).
Так как \(p\mid a^2+1\), имеем \(a^2\equiv-1\pmod p\). Тогда \(a^4\equiv1\pmod p\), но \(a^2 ot\equiv1\pmod p\). Значит порядок \(a\) по модулю \(p\) равен \(4\). Порядок делит \(p-1\), следовательно, \(4\mid p-1\), то есть \(p\equiv1\pmod4\).
Найдите все натуральные \(n\), для которых \(2n-1\mid n^2+1\).
Умножьте на \(4\).
Пусть \(d=2n-1\). Если \(d\mid n^2+1\), то \(d\mid4(n^2+1)\). Но \(4(n^2+1)=d^2+2d+5\). Поэтому \(d\mid5\). Возможны \(d=1\) и \(d=5\), откуда \(n=1\) или \(n=3\). Оба подходят.
Найдите все натуральные \(x>y\), для которых \(x^2-y^2=840\).
Положите \(x-y=2u\), \(x+y=2v\).
Так как \(x-y\) и \(x+y\) одной чётности, а произведение равно \(840\), оба множителя чётны. Пусть \(x-y=2u\), \(x+y=2v\). Тогда \(uv=210\), \(u
Докажите, что \(5\mid2^{4n}-1\) для любого натурального \(n\).
Найдите \(2^4\pmod5\).
Так как \(2^4=16\equiv1\pmod5\), то \(2^{4n}=(2^4)^n\equiv1^n\equiv1\pmod5\). Значит \(5\mid2^{4n}-1\).
Пусть \(\gcd(m,10)=1\). Докажите, что существует число, состоящее только из цифр \(0\) и \(1\), которое делится на \(m\).
Достаточно построить число из одних единиц.
По принципу Дирихле среди \(R_1,\ldots,R_m\) либо одно число делится на \(m\), либо два имеют одинаковый остаток. Во втором случае их разность равна \(10^iR_j\) для некоторого \(j\) и делится на \(m\). Так как \(10^i\) обратимо по модулю \(m\), получаем \(m\mid R_j\). Число \(R_j\) состоит только из единиц, значит также только из цифр \(0\) и \(1\).
Опишите все натуральные числа, имеющие ровно \(6\) положительных делителей.
Используйте формулу \( au(n)=(\alpha_1+1)\cdots(\alpha_s+1)\).
Если \(n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\), то число делителей равно \((\alpha_1+1)\cdots(\alpha_s+1)\). Нужно получить \(6\). Возможны разложения \(6=6\) и \(6=3\cdot2\). Поэтому \(n=p^5\) или \(n=p^2q\), где \(p,q\) — разные простые.
Докажите, что если квадрат натурального числа оканчивается цифрой \(5\), то его последние две цифры — \(25\).
Число, квадрат которого оканчивается на \(5\), само оканчивается на \(5\).
Пусть число равно \(10a+5\). Тогда \((10a+5)^2=100a^2+100a+25=100a(a+1)+25\). Значит последние две цифры квадрата равны \(25\).
Пусть \(n\) — нечётное натуральное число. Докажите, что \(n\mid1^n+2^n+\cdots+(n-1)^n\).
Сгруппируйте \(a\) и \(n-a\).
Для каждого \(a=1,\ldots,n-1\) число \(n-a\) тоже входит в сумму. Так как \(n\) нечётно, \(a^n+(n-a)^n\equiv a^n+(-a)^n=0\pmod n\). Все слагаемые разбиваются на такие пары, значит вся сумма делится на \(n\).
Найдите все простые \(p\), для которых \(p\mid2^p+1\).
Для нечётного простого используйте малую теорему Ферма.
При \(p=2\) имеем \(2^2+1=5\), не делится на \(2\). Пусть \(p\) нечётное. По малой теореме Ферма \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\). Значит нужно \(p\mid3\), откуда \(p=3\). Проверка: \(3\mid9\).
Докажите, что существует бесконечно много чисел, состоящих только из цифр \(0\) и \(1\), которые делятся на \(2027\).
Сначала постройте одно кратное из единиц, затем дописывайте нули справа.
Так как \(\gcd(2027,10)=1\), существует репьюнит \(R_s\), делящийся на \(2027\). Тогда для любого \(t\ge0\) число \(R_s\cdot10^t\) тоже делится на \(2027\) и состоит из единиц, после которых идут нули. При разных \(t\) получаем бесконечно много разных чисел.
Докажите, что для любого \(k\ge1\) существуют \(k\) последовательных натуральных чисел, каждое из которых делится на квадрат некоторого простого числа.
Выберите разные простые \(p_1,\ldots,p_k\) и задайте \(n+i\equiv0\pmod{p_i^2}\).
Выберем попарно различные простые \(p_1,\ldots,p_k\). Рассмотрим систему \(n\equiv-1\pmod{p_1^2}\), \(n\equiv-2\pmod{p_2^2}\), \(\ldots\), \(n\equiv-k\pmod{p_k^2}\). Модули \(p_i^2\) попарно взаимно просты, поэтому по CRT существует решение \(n_0\). Тогда каждое число \(n_0+i\) делится на \(p_i^2\). Прибавив к \(n_0\) достаточно большое кратное \(p_1^2\cdots p_k^2\), получаем положительные последовательные числа.