Теория чисел · Module 1

Делимость и разложение на простые множители

Определения, свойства делимости, простые числа, разложение, количество делителей, основы НОД и НОК.

Что означает делимость

Для целых чисел \(a\) и \(b\), где \(a\ne0\), запись \(a\mid b\) означает, что существует целое \(k\), такое что \(b=ak\). Делимость говорит о точной целочисленной структуре.

Основные свойства

Если \(a\mid b\) и \(a\mid c\), то \(a\mid b+c\), \(a\mid b-c\), и вообще \(a\mid xb+yc\) для любых целых \(x,y\).

Простые числа

Простое число имеет ровно два положительных делителя: \(1\) и само себя. Число \(1\) не считается простым, чтобы разложение на простые множители было единственным.

Разложение на простые множители

Каждое число \(n>1\) единственным образом представляется в виде \(p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\), где \(p_i\) — различные простые числа.

Количество делителей

Если \(n=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\), то \(\tau(n)=(a_1+1)(a_2+1)\cdots(a_m+1)\).

Если \(6\mid n\), докажите \(3\mid n\).

Запишите \(n=6k=3(2k)\).

Найдите разложение \(840\).

\(840=2^3\cdot3\cdot5\cdot7\).

Посчитайте делители \(840\).

Так как \(840=2^3\cdot3\cdot5\cdot7\), получаем \((3+1)(1+1)^3=32\).

Найдите \(\gcd(84,126)\).

\(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\), значит НОД равен \(42\).

Найдите \(\operatorname{lcm}(84,126)\).

Берем максимальные показатели: \(2^2\cdot3^2\cdot7=252\).

Докажите: если \(a\mid b\), то \(a\mid bc\).

Если \(b=ak\), то \(bc=a(kc)\).

Докажите \(a\mid b\) и \(a\mid c\Rightarrow a\mid5b-2c\).

Пусть \(b=ax\), \(c=ay\). Тогда \(5b-2c=a(5x-2y)\).

Найдите наименьшее число только из простых \(2\) и \(3\), имеющее \(12\) делителей.

Сравните наборы показателей. Минимум: \(2^5\cdot3=96\).

Докажите, что \(n^2-n\) четно.

\(n^2-n=n(n-1)\), произведение соседних чисел.

Докажите \(3\mid n^3-n\).

\(n^3-n=n(n-1)(n+1)\), три последовательных числа.

Найдите простые \(p\), для которых \(p,p+2,p+4\) простые.

Рассмотрение по модулю \(3\) показывает, что подходит только \(p=3\).

Перечислите положительные делители \(24\).

\(1,2,3,4,6,8,12,24\).

Если \(a\mid b\) и \(b\mid a\), докажите \(a=\pm b\).

Используйте \(b=ak\), \(a=bm\), тогда \(km=1\).

Найдите показатель \(2\) в \(100!\).

\(50+25+12+6+3+1=97\).

Объясните лемму Евклида.

Если простое \(p\) появляется в \(ab\), оно появляется в \(a\) или \(b\).

NT-01-001

Точная делимость

Уровень 1

Divisibility

definition integer

Определите, верно ли \(8\mid 120\), \(8\mid 122\) и \(9\mid 117\). Объясните каждый ответ.

Подсказка

Используйте определение: \(a\mid b\) означает, что \(b=ak\) для некоторого целого \(k\).

Решение

\(120=8\cdot15\), значит \(8\mid120\). Так как \(122=8\cdot15+2\), то \(8\nmid122\). Также \(117=9\cdot13\), значит \(9\mid117\).

NT-01-002

Делимость из произведения

Уровень 1

Divisibility

proof definition

Докажите, что если \(12\mid n\), то \(3\mid n\).

Подсказка

Запишите \(n=12k\).

Решение

Если \(12\mid n\), то \(n=12k=3(4k)\) для некоторого целого \(k\). Следовательно, \(3\mid n\).

NT-01-003

Линейная комбинация

Уровень 1

Divisibility Laws

proof linear-combination

Если \(7\mid a\) и \(7\mid b\), докажите, что \(7\mid 4a+5b\).

Подсказка

Положите \(a=7x\) и \(b=7y\).

Решение

Пусть \(a=7x\) и \(b=7y\). Тогда \(4a+5b=28x+35y=7(4x+5y)\), значит \(7\mid4a+5b\).

NT-01-004

Проверка утверждения о делимости

Уровень 2

Divisibility Laws

proof difference

Если \(11\mid 3x+2\) и \(11\mid x-3\), обязательно ли \(11\mid 11x-7\)? Дайте доказательство или контрпример.

Подсказка

Проверьте значение \(x\), которое удовлетворяет обоим данным условиям.

Решение

Так как \(11\mid3x+2\) и \(11\mid x-3\), любая целая линейная комбинация этих выражений делится на \(11\). Например, \((3x+2)+8(x-3)=11x-22=11(x-2)\). Но \((11x-7)-(11x-22)=15\), поэтому исходное заключение не следует. При \(x=3\) имеем \(x-3=0\), \(3x+2=11\), но \(11x-7=26\), что не делится на \(11\). Значит утверждение ложно.

NT-01-005

Разложение числа 420

Уровень 1

Prime Factorisation

factorisation

Найдите разложение числа \(420\) на простые множители.

Подсказка

Разбейте \(420\) как \(42\cdot10\).

Решение

\(420=42\cdot10=(2\cdot3\cdot7)(2\cdot5)=2^2\cdot3\cdot5\cdot7\).

NT-01-006

Разложение числа 756

Уровень 2

Prime Factorisation

factorisation

Найдите разложение числа \(756\) на простые множители.

Подсказка

Сначала разделите на \(2\), затем проверяйте делимость на \(3\).

Решение

\(756=2\cdot378=2^2\cdot189=2^2\cdot3^3\cdot7\).

NT-01-007

Количество делителей

Уровень 1

Number of Divisors

divisors tau-function

Сколько положительных делителей имеет число \(360\)?

Подсказка

Сначала разложите \(360\) на степени простых чисел.

Решение

\(360=2^3\cdot3^2\cdot5\). Поэтому \(\tau(360)=(3+1)(2+1)(1+1)=24\).

NT-01-008

Квадрат и нечетное число делителей

Уровень 2

Number of Divisors

divisors squares

Объясните, почему каждый полный квадрат имеет нечетное число положительных делителей.

Подсказка

В разложении полного квадрата все показатели степеней четные.

Решение

Если \(n=m^2\), то все показатели степеней в разложении \(n\) на простые множители четные. Значит каждый множитель \(a_i+1\) в формуле \(\tau(n)=\prod(a_i+1)\) нечетен, а произведение нечетных чисел нечетно.

NT-01-009

НОД по разложениям

Уровень 1

GCD and LCM

gcd factorisation

Найдите \(\gcd(144,180)\).

Подсказка

Берите минимальный показатель степени каждого простого числа.

Решение

\(144=2^4\cdot3^2\), а \(180=2^2\cdot3^2\cdot5\). Поэтому \(\gcd(144,180)=2^2\cdot3^2=36\).

NT-01-010

НОК по разложениям

Уровень 1

GCD and LCM

lcm factorisation

Найдите \(\operatorname{lcm}(144,180)\).

Подсказка

Берите максимальный показатель степени каждого простого числа.

Решение

Так как \(144=2^4\cdot3^2\) и \(180=2^2\cdot3^2\cdot5\), получаем \(\operatorname{lcm}(144,180)=2^4\cdot3^2\cdot5=720\).

NT-01-011

Формула произведения

Уровень 2

GCD and LCM

gcd lcm identity

Проверьте равенство \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\) для \(a=48\), \(b=180\).

Подсказка

Найдите и \(\gcd\), и \(\operatorname{lcm}\).

Решение

\(48=2^4\cdot3\), \(180=2^2\cdot3^2\cdot5\). Тогда \(\gcd=2^2\cdot3=12\), а \(\operatorname{lcm}=2^4\cdot3^2\cdot5=720\). Получаем \(12\cdot720=8640=48\cdot180\).

NT-01-012

Произведение соседних чисел

Уровень 1

Divisibility Proofs

consecutive-integers proof

Докажите, что \(2\mid n(n+1)\) для любого целого \(n\).

Подсказка

Из двух соседних целых чисел одно четное.

Решение

Числа \(n\) и \(n+1\) соседние, значит одно из них четное. Поэтому их произведение делится на \(2\).

NT-01-013

Три последовательных числа

Уровень 1

Divisibility Proofs

consecutive-integers proof

Докажите, что \(3\mid n(n+1)(n+2)\) для любого целого \(n\).

Подсказка

Среди любых трех последовательных целых чисел есть кратное \(3\).

Решение

Числа \(n,n+1,n+2\) дают все возможные остатки при делении на \(3\). Одно из них делится на \(3\), значит произведение делится на \(3\).

NT-01-014

Делимость произведения на шесть

Уровень 2

Divisibility Proofs

consecutive-integers proof

Докажите, что \(6\mid n(n+1)(n+2)\) для любого целого \(n\).

Подсказка

Докажите делимость на \(2\) и на \(3\).

Решение

Среди трех последовательных чисел одно делится на \(3\), и хотя бы одно четное. Так как \(2\) и \(3\) взаимно просты, произведение делится на \(6\).

NT-01-015

Разность квадратов

Уровень 2

Factorisation Methods

factorisation proof

Докажите: если \(a-b\) делится на \(5\), то \(a^2-b^2\) делится на \(5\).

Подсказка

Разложите \(a^2-b^2\) на множители.

Решение

Так как \(a^2-b^2=(a-b)(a+b)\) и \(5\mid a-b\), произведение \((a-b)(a+b)\) делится на \(5\).

NT-01-016

Простое или составное

Уровень 1

Primes

prime classification

Определите, какие числа простые, а какие составные: \(37, 49, 57, 83\).

Подсказка

Для проверки числа \(n\) достаточно проверять простые делители не больше \(\sqrt n\).

Решение

\(37\) простое. \(49=7^2\) составное. \(57=3\cdot19\) составное. \(83\) простое, так как оно не делится на \(2,3,5,7\), а \(\sqrt{83}<10\).

NT-01-017

Наименьшее число с восемью делителями

Уровень 2

Number of Divisors

optimization divisors

Найдите наименьшее положительное целое число, имеющее ровно \(8\) положительных делителей.

Подсказка

Разложите \(8\) как \(8\), \(4\cdot2\) или \(2\cdot2\cdot2\).

Решение

Возможные наборы показателей: \(7\), \(3,1\), \(1,1,1\). Минимальные кандидаты: \(2^7=128\), \(2^3\cdot3=24\), \(2\cdot3\cdot5=30\). Наименьшее число равно \(24\).

NT-01-018

Ровно девять делителей

Уровень 2

Number of Divisors

optimization divisors

Найдите наименьшее положительное целое число, имеющее ровно \(9\) положительных делителей.

Подсказка

Наборы показателей получаются из \(9\) и \(3\cdot3\).

Решение

Возможные наборы: \(8\) и \(2,2\). Минимальные кандидаты: \(2^8=256\) и \(2^2\cdot3^2=36\). Следовательно, ответ \(36\).

NT-01-019

Уравнение с делимостью

Уровень 2

Divisibility

equation divisors

Найдите все положительные целые \(n\), такие что \(n\mid 30\).

Подсказка

Перечислите положительные делители числа \(30\).

Решение

Так как \(30=2\cdot3\cdot5\), его положительные делители: \(1,2,3,5,6,10,15,30\).

NT-01-020

Остаток линейного выражения

Уровень 2

Remainders

remainders expression

Если \(n\) дает остаток \(2\) при делении на \(5\), какой остаток дает \(3n+1\) при делении на \(5\)?

Подсказка

Запишите \(n=5k+2\).

Решение

Пусть \(n=5k+2\). Тогда \(3n+1=15k+7=5(3k+1)+2\), значит остаток равен \(2\).

NT-01-021

Остаток квадрата

Уровень 2

Remainders

remainders squares

Докажите, что квадрат целого числа дает остаток \(0\) или \(1\) при делении на \(4\).

Подсказка

Рассмотрите четные и нечетные числа.

Решение

Если \(n=2k\), то \(n^2=4k^2\), остаток \(0\). Если \(n=2k+1\), то \(n^2=4k^2+4k+1\), остаток \(1\).

NT-01-022

Квадрат не дает остаток два

Уровень 2

Remainders

remainders squares impossibility

Докажите, что квадрат целого числа не может давать остаток \(2\) при делении на \(4\).

Подсказка

Используйте факт, что остатки квадратов по модулю \(4\) бывают только \(0\) и \(1\).

Решение

Из рассмотрения четного и нечетного случая следует, что любой квадрат имеет вид \(4k\) или \(4k+1\). Поэтому остаток \(2\) невозможен.

NT-01-023

Простой делитель

Уровень 2

Primes

prime divisibility

Пусть \(p\) простое число. Если \(p\mid 35\), найдите все возможные значения \(p\).

Подсказка

Разложите \(35\) на множители.

Решение

Так как \(35=5\cdot7\), простые делители числа \(35\) равны \(5\) и \(7\). Поэтому \(p\in\{5,7\}\).

NT-01-024

Тройка простых чисел

Уровень 3

Primes

prime remainders proof

Найдите все простые \(p\), для которых \(p\), \(p+2\) и \(p+4\) также простые.

Подсказка

Посмотрите на остатки при делении на \(3\).

Решение

Если \(p>3\), то числа \(p,p+2,p+4\) покрывают все остатки по модулю \(3\), значит одно из них делится на \(3\). Оно больше \(3\), поэтому не может быть простым. Проверяем \(p=3\): получаем \(3,5,7\), все простые. Следовательно, \(p=3\).

NT-01-025

Показатель простого в факториале

Уровень 3

Prime Factorisation

factorial exponent

Найдите показатель степени \(5\) в разложении \(50!\) на простые множители.

Подсказка

Посчитайте кратные \(5\), затем дополнительные множители из кратных \(25\).

Решение

Показатель равен \(\left\lfloor50/5\right\rfloor+\left\lfloor50/25\right\rfloor=10+2=12\).

NT-01-026

Нули в конце факториала

Уровень 3

Prime Factorisation

factorial trailing-zeros

Сколькими нулями оканчивается число \(60!\)?

Подсказка

Каждый ноль требует множитель \(10=2\cdot5\). Какой простой множитель встречается реже?

Решение

Число нулей в конце равно показателю степени \(5\) в \(60!\), потому что двоек больше. Получаем \(\lfloor60/5\rfloor+\lfloor60/25\rfloor=12+2=14\).

NT-01-027

Контрпример к делимости

Уровень 2

Divisibility

counterexample

Верно ли утверждение: если \(a\mid bc\), то \(a\mid b\) или \(a\mid c\)? Дайте доказательство или контрпример.

Подсказка

Попробуйте составное значение \(a\).

Решение

Утверждение ложно. Возьмем \(a=6\), \(b=2\), \(c=3\). Тогда \(6\mid bc\), потому что \(bc=6\), но \(6\nmid2\) и \(6\nmid3\).

NT-01-028

Пример к лемме Евклида

Уровень 2

Primes

prime euclid-lemma

Пусть \(p\) простое и \(p\mid ab\). Объясните через разложение на простые множители, почему естественен вывод: \(p\mid a\) или \(p\mid b\).

Подсказка

Простой множитель, который появился в \(ab\), должен прийти из одного из множителей.

Решение

В разложении \(ab\) на простые множители все простые множители приходят из разложений \(a\) и \(b\). Если простой \(p\) встречается в \(ab\), он должен встречаться в \(a\) или в \(b\). Значит \(p\mid a\) или \(p\mid b\).

NT-01-029

Произведение взаимно простых делителей

Уровень 3

GCD and LCM

coprime divisibility

Если \(\gcd(a,b)=1\), \(a\mid n\) и \(b\mid n\), докажите, что \(ab\mid n\).

Подсказка

Используйте разложение на простые множители: взаимно простые числа не имеют общих простых делителей.

Решение

Так как \(a\) и \(b\) не имеют общих простых множителей, простые степени, нужные для \(a\), и простые степени, нужные для \(b\), независимы. Если \(n\) делится на оба числа, то \(n\) содержит все простые степени из \(a\) и все из \(b\), значит \(ab\mid n\).

NT-01-030

Найти неизвестный показатель

Уровень 2

Number of Divisors

divisors exponents

Для \(n=2^3\cdot3^a\) найдите все положительные целые \(a\), при которых \(n\) имеет \(20\) положительных делителей.

Подсказка

Используйте \((3+1)(a+1)=20\).

Решение

\(\tau(n)=(3+1)(a+1)=4(a+1)\). Решаем \(4(a+1)=20\), откуда \(a+1=5\) и \(a=4\).

NT-01-031

Общие делители

Уровень 2

GCD and LCM

gcd divisors

Сколько положительных общих делителей имеют числа \(84\) и \(126\)?

Подсказка

Общие делители двух чисел — это ровно делители их \(\gcd\).

Решение

\(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\), значит \(\gcd(84,126)=2\cdot3\cdot7=42\). Так как \(42=2\cdot3\cdot7\), у него \((1+1)^3=8\) положительных делителей.

NT-01-032

Все делители через показатели

Уровень 1

Prime Factorisation

divisors listing

Перечислите все положительные делители числа \(2^2\cdot3\).

Подсказка

Выберите показатель у \(2\) из \(0,1,2\), а показатель у \(3\) из \(0,1\).

Решение

Число равно \(12\). Его положительные делители: \(1,2,3,4,6,12\).

NT-01-033

Признак делимости на девять

Уровень 1

Divisibility Tests

divisibility-test digits

Используйте сумму цифр, чтобы определить, делится ли \(738\) на \(9\).

Подсказка

Сложите цифры числа.

Решение

Сумма цифр равна \(7+3+8=18\), а \(9\mid18\). Следовательно, \(9\mid738\).

NT-01-034

Сделать число делящимся

Уровень 2

Divisibility Tests

digits divisibility-test

Найдите все цифры \(x\), при которых число \(45x2\) делится на \(3\).

Подсказка

Число делится на \(3\), если сумма его цифр делится на \(3\).

Решение

Сумма цифр равна \(4+5+x+2=11+x\). Нужно \(11+x\equiv0\pmod3\). Так как \(11\equiv2\pmod3\), получаем \(x\equiv1\pmod3\). Возможные цифры: \(1,4,7\).

NT-01-035

Четные делители

Уровень 3

Number of Divisors

divisors counting

Сколько положительных четных делителей имеет число \(720\)?

Подсказка

Сначала разложите \(720\). Для четного делителя показатель степени \(2\) должен быть хотя бы \(1\).

Решение

\(720=2^4\cdot3^2\cdot5\). У четного делителя показатель у \(2\) может быть \(1,2,3\) или \(4\): \(4\) варианта. У показателя \(3\) есть \(3\) варианта, у показателя \(5\) — \(2\) варианта. Всего \(4\cdot3\cdot2=24\).

NT-01-036

Нечетные делители

Уровень 2

Number of Divisors

divisors counting

Сколько положительных нечетных делителей имеет число \(720\)?

Подсказка

Нечетные делители не используют множитель \(2\).

Решение

Так как \(720=2^4\cdot3^2\cdot5\), нечетный делитель должен содержать \(2^0\). Тогда у показателя \(3\) есть \(3\) варианта, а у показателя \(5\) — \(2\) варианта. Всего \(3\cdot2=6\) положительных нечетных делителей.

NT-01-037

Цепочка делимости

Уровень 2

Divisibility

proof transitivity

Докажите, что если \(a\mid b\) и \(b\mid c\), то \(a\mid c\).

Подсказка

Запишите \(b=ak\) и \(c=bm\).

Решение

Если \(a\mid b\), то \(b=ak\). Если \(b\mid c\), то \(c=bm\). Следовательно, \(c=akm=a(km)\), значит \(a\mid c\).

NT-01-038

Взаимная делимость

Уровень 3

Divisibility

proof absolute-value

Пусть \(a\) и \(b\) — положительные целые числа. Докажите: если \(a\mid b\) и \(b\mid a\), то \(a=b\).

Подсказка

Используйте \(b=ak\) и сравните размеры чисел.

Решение

Так как \(a\mid b\), запишем \(b=ak\), где \(k\) — положительное целое число. Так как \(b\mid a\), запишем \(a=bm\), где \(m\) — положительное целое число. Тогда \(a=akm\). Поскольку \(a>0\), получаем \(km=1\), значит \(k=m=1\), и \(a=b\).

NT-01-039

Найти НОД и НОК

Уровень 2

GCD and LCM

gcd lcm

Найдите \(\gcd(210,330)\) и \(\operatorname{lcm}(210,330)\).

Подсказка

Сначала разложите оба числа на простые множители.

Решение

\(210=2\cdot3\cdot5\cdot7\), а \(330=2\cdot3\cdot5\cdot11\). Поэтому \(\gcd=2\cdot3\cdot5=30\), а \(\operatorname{lcm}=2\cdot3\cdot5\cdot7\cdot11=2310\).

NT-01-040

Олимпиадная разминка

Challenge

Divisibility Proofs

proof factorisation consecutive-integers

Докажите, что \(24\mid n(n^2-1)(n+2)\) для любого целого \(n\).

Подсказка

Разложите выражение в произведение четырех последовательных целых чисел.

Решение

Имеем \(n(n^2-1)(n+2)=n(n-1)(n+1)(n+2)\), то есть произведение четырех последовательных целых чисел. Среди них есть число, кратное \(4\), еще одно четное число и хотя бы одно число, кратное \(3\). Поэтому произведение делится на \(8\cdot3=24\).

Лист

Печатные PDF и DOCX-листы будут прикреплены здесь.

Методичка

Методичка видна только аккаунтам teacher/admin.

Войти