Тема ТЕОРИЯ ЧИСЕЛ

Остатки и сравнения по модулю → .02 Выбор модуля для доказательства делимости / простоты / степени

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория чисел

Разделы подтемы Остатки и сравнения по модулю

Базовый аппарат сравнений по модулю

Выбор модуля для доказательства делимости / простоты / степени

Малая теорема Ферма

Функция Эйлера и теорема Эйлера из ТЧ

Китайская теорема об остатках

Обратные остатки

Квадратичные вычеты

Показатели и первообразные корни

Лемма об уточнении показателя

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 61#89720Максимум баллов за задание: 7

Найдите наименьшее натуральное число, представимое в виде $20x2+ 80xy+ 95y2$ для целых $x$ и $y.$

Подсказки к задаче

Подсказка 1

Давайте рассмотрим число, полученное из данного путем деления на 5. Если для нового выражения мы найдем минимальное число, представимое таким образом, то и для изначально уравнения минимальным будет данное, умноженное на 5.

Подсказка 2

Итак, мы получили выражение 4x² + 16xy + 19y². Первые два слагаемых похожи на формулу полного квадрата. Как насчёт того, чтобы его выделить? Сумму квадратов оценить не так уж трудно. Хм, а для чего мы это сделали..?

Показать ответ и решение

Поделим все на $5.$

2 2 2 2 4x +16xy+ 19y = 4(x+ 2y) + 3y

По модулю $4$ полученное выражение сравнимо либо с $0,$ либо с $3.$ Тогда это выражение, раз оно принимает натуральное значение, хотя бы $3.$ Причем значение, равное $3,$ достигается при $y = 1,x= −2.$ Тогда минимальное натуральное значение исходного выражения равно $15.$

Ответ:

$15$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 62#79756Максимум баллов за задание: 7

Натуральные числа $x$ и $y$ равны $2014$ соответственно в десятичной и восьмеричной системе. Будет ли число $x2000− y1000$ точным квадратом?

Подсказки к задаче

Подсказка 1

Удобно ли нам работать с выражением, когда слагаемые записаны в разных системах счисления? Тогда вспоминаем алгоритм и переводим всё в привычную нам форму!

Подсказка 2

Большие степени явно намекают на то что вычислить выражение напрямую нам вряд ли удастся. Общий множитель, который можно вынести за скобки, конечно есть, но тоже вряд ли облегчит нам задачу. Что же остаётся делать?

Подсказка 3

Кажется, пора подумать о делимости и сравнениях по модулю! А что мы вообще хотим достичь? Какая (не)делимость поможет нам прийти к противоречию?

Подсказка 4

Может ли быть так, что точный квадрат делится на какое-то простое n, но не делится на n²? Осталось просто удачно подобрать это самое n!

Показать ответ и решение

Речь идёт о числе $20142000 − 10361000.$ Покажем, что оно делится на $3,$ но не делится на $9.$ Действительно, $20142000 ≡ 12000 (mod 3).$ То же самое можно сказать про $1000 1036 .$ В то время как

2000 2000 2000 1000 1000 2014 ≡ 7 ≡ 2 (mod 9),1036 ≡ 1 ≡1 (mod 9)

То есть по модулю $9$ число сравнимо с $22000− 1.$ Учитывая, что $26 ≡ 1 (mod 9),$ имеем $22000− 1≡ 22 − 1= 3.$ Значит, $3$ входит в это число в $1$ степени, то есть оно не квадрат.

Ответ:

Нет

Ошибка.
Попробуйте повторить позже

Задача 63#77848Максимум баллов за задание: 7

Докажите, что число $22014+1$ можно представить в виде произведения трех натуральных чисел, больших 1.

Подсказки к задаче

Подсказка 1

Число из условия очень похоже на многочлен, а какие делители точно есть у многочлена вида a^n +1?

Подсказка 2

Если n - нечетно, то a^n+1 делится на a+1. Попробуем таким способов найти хотя бы 1 делитель!

Подсказка 3

Заметим, что 2^2014+1 делится 2^38+1. выходит, теперь у нас есть 2 делителя. А на какие делители можно разбить 2^38+1?

Показать доказательство

Напомним, что при нечётном $n$ число $an+ 1$ делится на $a+ 1$ при любом натуральном $a.$

Так как $2014=2 ⋅19⋅53,$ то взяв $2⋅19 a= 2 ,n= 53,$ получаем, что число $2014 2 +1$ делится на $2⋅19 2 + 1.$

Взяв $2 a= 2,n= 19$ , получаем, что $2⋅19 2 +1$ делится на $2 2 + 1= 5.$

В итоге

2014 22014+ 1 238+1 2 + 1= -238+-1-⋅--5---⋅5,

причём каждый из трёх множителей в разложении это натуральное число больше единицы (у двух данных сократимых дробей, очевидно, числитель больше знаменателя).

Ошибка.
Попробуйте повторить позже

Задача 64#101216Максимум баллов за задание: 7

При каком наибольшем натуральном значении $n$ число $n!+ 5n +52$ является точным квадратом?

Подсказки к задаче

Подсказка 1

Как можно выявлять точные квадраты?

Подсказка 2

Попробуйте посмотреть на остатки.

Подсказка 3

Например, 5n всегда делится на 5. А что тогда можно сказать про n! ?

Подсказка 4

Если n ≥ 5, то остаток при делении на 5 выражения будет равен 2, но ни один точный квадрат не даёт такой остаток по модулю 5. Осталось рассмотреть n < 5.

Показать ответ и решение

Заметим, что при $n≥ 5$ $n!$ делится на 5. Отсюда

n!+5n+ 52≡ 2 (mod 5)

Рассмотрим таблицу остатков квадратов по модулю 5:


$x$	$x2$

$0$	$0$

$1$	$1$

$2$	$4$

$3$	$4$

$4$	$1$

Из таблицы видно, что квадрат не может давать остаток 2 по модулю 5, а, значит, при $n≥ 5$ число $n!+ 5n +52$ не является квадратом. Осталось рассмотреть $n <5.$

При $n =4 :n!+ 5n+ 52 =24+ 20+ 52 =96$ — не квадрат.

При $n =3 :n!+ 5n+ 52 =6 +15+ 52= 73$ — не квадрат.

При $2 n =2 :n!+ 5n+ 52 =2 +10+ 52= 64 =8$ — квадрат.

Итак, наибольшее натуральное значение $n,$ при котором число $n!+5n +52$ является точным квадратом, равно 2.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 65#64855Максимум баллов за задание: 7

Найдите все пары взаимно простых натуральных чисел $a$ и $b$ такие, что $2a2 +3b2$ делится на $2a+3b.$

Подсказки к задаче

Подсказка 1

Пусть m = 2а+3b. Тогда отсюда выражается, например, 2а, которое при возведении в квадрат превращается в 4а^2. А у нас в изначальном выражении есть 2а^2, значит таким образом мы сможем узнать что-то о соотношении b и m. Аналогично узнаем про число а и m.

Подсказка 2

Верно, и 15b^2 кратно m, и 10a^2. Используя понимание взаимной простоты чисел а и b мы должны осознать, какие простые делители есть у m.

Подсказка 3

Могут ли простые делители числа m входить в него больше, чем в первой степени? Получив ответ на этот вопрос, мы найдем единственно возможные варианты числа m = 2а+3b и проверим их, помня, что работаем с натуральными числами.

Показать ответ и решение

Заметим, что $4a2− 9b2 = (2a+ 3b)(2a − 3b) ≡ 0, 2a+3b$ отсюда $4a2 − 9b2− 2(2a2+3b2)=− 15b2 ≡ 0 2a+3b$ и $4a2− 9b2+ 3(2a2+ 3b2)= 10a2 ≡ 0. 2a+3b$ Пусть $2a+ 3b$ содержит некоторый делитель $d,$ который взаимно прост с $10$ и $15$ — тогда на это число должны делиться $a2$ и $b2,$ что невозможно, поскольку $(a2,b2)= 1.$ Отсюда $2a +3b$ делится только на $2,3,5$ (из простых чисел). Если какое-то простое число $p$ входит в него большей степени $q > 1,$ то $pq−1$ делит $a2$ и $b2,$ значит, степень каждого простого не больше первой. То есть $2a+ 3b$ может принимать значения $1,2,3,5,6,10,15,30.$ Первые три невозможны, пятёрка даёт нам $a= b= 1,$ что подходит. Пятый случай также невозможен, в шестом $a =b =2,$ условие взаимной простоты не выполнено. Для $15$ есть случаи $a =b =3$ и $a= 6,b= 1,$ нам подойдёт только второй. Для $30$ получаем $(3,8),(6,6),(9,4)$ — подойдут первый и третий случаи. Остаётся выписать ответ.

Ответ:

$(1,1),(6,1),(3,8),(9,4)$

Ошибка.
Попробуйте повторить позже

Задача 66#89719Максимум баллов за задание: 7

Целые числа $x,y,z$ таковы, что $(x− y)(y− z)(z− x)=x +y+ z.$ Докажите, что тогда $x+ y+ z$ делится на $27.$

Источники: Всеросс., 1993, ЗЭ, 9.4(см. math.ru)

Подсказки к задаче

Подсказка 1

Предположим, что данное число не кратно 3. Что можно сказать про числа x-y, y-z, z-x?

Подсказка 2

Никакое из них не кратно 3, то есть числа x, y, z дают различные остатки по модулю 3. Как можно получить противоречие исходя из этого?

Подсказка 3

В этом случае число x+y+z сравнимо с числом 1+2+3 по модулю 3, то есть кратно ему, что невозможно. Так, мы поняли, что среди чисел x, y, z найдутся хотя бы два с одинаковым остатком при делении 3. Как это можно использовать, чтобы доказать делимость на 27?

Показать доказательство

Докажем, что числа $x,y$ и $z$ дают одинаковые остатки при делении на $3.$ Тогда из условия будет следовать, что число $x+ y+z$ делится на $27.$

Если числа $x,y$ и $z$ дают различные остатки при делении на три, то число $(x− y)(y− z)(z− x)$ не делится на $3,$ а число $x+ y+z,$ наоборот, делится на $3.$ Следовательно, по крайней мере, два из трех чисел $x,y,z$ дают одинаковые остатки при делении на $3.$ Но тогда число $x+ y+ z = (x − y)(y − z)(z− x)$ делится на $3,$ а для этого необходимо, чтобы и третье число давало тот же остаток при делении на $3,$ что и первые два числа.