Математика · объяснение и практика
Когда простой делитель произведения делит один из множителей
Проверяем обязательное условие леммы о делителе произведения, выводим её из взаимной простоты и понимаем, почему составной делитель ведёт себя иначе.

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Если d делит ab и НОД(d,a) = 1, то d делит b. В частности, простой p, делящий произведение, делит хотя бы один множитель. Для произвольного составного делителя без условия взаимной простоты такой вывод неверен.
Почему произведение может обмануть
Число шесть делит произведение 2·3, но не делит ни двойку, ни тройку. Его простые части распределились между множителями. Поэтому из делимости произведения нельзя без дополнительного условия заключать, что весь делитель находится внутри одного множителя. У простого числа нет такого разбиения на две нетривиальные части, что и делает его особым.
Более общая формулировка использует взаимную простоту: если d и a не имеют общего делителя больше единицы, а d делит ab, то d делит b. Делитель d здесь может быть составным. Например, девять взаимно просто с четырьмя, поэтому из делимости 4b на девять следует делимость самого b на девять.
Как взаимная простота даёт доказательство
Для взаимно простых целых d и a существуют целые u и v, для которых ud+va = 1. Это тождество можно получить обратными подстановками в алгоритме Евклида. Умножим его на b: udb+vab = b. Слагаемое udb делится на d по записи, а vab делится на d по исходному условию. Значит, их сумма b тоже делится на d.
В конкретной задаче не всегда нужно заново искать коэффициенты u и v. Для чисел девять и четыре подходит 9−2·4 = 1. Если 4b кратно девяти, умножаем на b и видим b = 9b−2·4b, разность двух кратных девяти. Такая короткая проверка показывает, какую работу выполняет условие НОД = 1.
Пример
Известно, что 35 делит 12x. Докажите, что 35 делит x, для целого x.
Числа 35 и 12 взаимно просты: 3·12−35 = 1. Умножаем на x: x = 3·12x−35x. Оба слагаемых справа кратны 35, поэтому x тоже кратно 35.
Как получить частный случай для простого
Пусть простой p делит ab. Если он уже делит a, требуемый вывод выполнен. Если не делит, то НОД(p,a) = 1, ведь положительные делители p — только единица и само p. Применяем общую лемму и получаем p, делящее b. Утверждение допускает и делимость обоих множителей; слова «хотя бы один» не означают «ровно один».
При работе с составным d сначала вычисляют НОД с выбранным множителем. Например, из 12, делящего 8b, нельзя вывести делимость b на 12: значение b = 3 даёт контрпример. Зато после сокращения общей части можно получить делимость b на три. Проверка условий полезнее механического переноса простого правила на любое число.
От чтения к действию
А теперь — вы
Частые вопросы
Может простой делитель делить оба множителя?
Да. Например, 3 делит и 6, и 9. Лемма утверждает наличие хотя бы одного подходящего множителя и не запрещает второй.
Составной делитель всегда исключает применение леммы?
Нет. Общая версия работает и для составного d, если он взаимно прост с одним из множителей.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Обратный элемент по модулю: условие существования и проверка
Находим обратный множитель по модулю, проверяем условие взаимной простоты и отличаем обратный остаток от обычной дроби.
Открыть темуКогда в сравнении по модулю можно сократить множитель
Сокращаем множитель в сравнении по модулю с проверкой НОД и понимаем, почему обычное деление обеих сторон может потерять классы решений.
Открыть тему