Как доказать что числа не взаимно простые

Взаимно простые числа

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

• Например, 13 является простым, так как нацело делится только на 1 и на 13.

Таких чисел немного, большинство все-таки можно разделить на другие числа. В простых числах самое важное — это деление нацело. Дробные частные и деление с остатком не рассматриваем.

Понятие взаимно простых чисел можно применить для двух целых чисел или для большего количества. Сформулируем, какие числа называются взаимно простыми.

Взаимно простые числа

Два целых числа a и b называются взаимно простыми, если их наибольший общий делитель равен единице — то есть НОД (a, b) = 1.

Проще говоря, взаимно простые числа — это целые числа, у которых нет общих делителей, кроме единицы.

Наибольшим общим делителем двух чисел a и b называется наибольшее число, на которое a и b делятся без остатка. Для записи может использоваться аббревиатура НОД. Для двух чисел можно записать так: НОД (a, b).

Числа, которые содержат больше двух множителей, то есть делятся на несколько чисел, называют сложными . Сложные числа состоят из перемноженных простых.

Наибольший общий делитель взаимно простых чисел — это единица, что следует из определения взаимно простых чисел.

Из определения взаимно простых чисел можно сделать вывод, что у двух взаимно простых чисел может быть только один положительный общий делитель, который равен единице. А всего общих делителей у двух взаимно простых чисел два — это 1 и -1.

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

• Числа 13 и 16 взаимно простые потому, что их положительный общий делитель — единица, что подтверждает взаимную простоту чисел 13 и 16.

Заметим, что два простых числа всегда являются взаимно простыми. Однако, два числа не обязательно должны быть простыми, чтобы быть взаимно простыми. Вот такая математика в 5 классе. И еще раз: либо одно из них, либо они оба могут быть составными и при этом являться взаимно простыми. Приведем пример.

• Два составных числа 8 и -9 являются взаимно простыми. Как доказать что числа взаимно простые? Объясним:

Сначала найдем НОД этих чисел, то есть запишем все делители чисел 8 и -9.

Делители 8: ±1, ±2, ±4, ±8.

Делители -9: ±1, ±3, ±9.

Из этого следует, НОД (8, -9) = 1, поэтому, по определению 8 и -9 — два взаимно простых числа.

• А вот числа 45 и 500 нельзя назвать взаимно простыми, так как у них есть положительный общий делитель, отличный от единицы — это число 5. Числа 3 и -201 тоже не взаимно простые, так как у них общий положительный делитель — тройка.

На математике в 5 и 6 класса часто встречаются задания, в которых нужно доказать, что конкретные целые числа являются взаимно простыми. Из чего обычно состоит такое доказательство:

• вычисление наибольшего общего делителя заданных чисел,
• проверка НОД на его равенство единице.

Перед вычислением НОД можно заглянуть в таблицу простых чисел и проверить, вдруг исходные целые числа можно назвать простыми. Тогда решение будет проще, так как мы знаем, что НОД простых чисел равен единице.

Онлайн-подготовка к ОГЭ по математике — отличный способ снять стресс и закрепить знания перед экзаменом.

Повторим еще раз. Что значит взаимно простые числа? Это целые числа, у которых нет общих делителей, кроме единицы.

Пример 1

Доказать, что числа 84 и 275 являются взаимно простыми.

Сверяемся с таблицей простых чисел. 84 и 275 не являются простыми, поэтому нельзя сразу сказать об их взаимной простоте.

Вычислим НОД. Используем алгоритм Евклида для нахождения НОД:

Доказали, что числа 84 и 275 взаимно простые.

Определение взаимно простых чисел можно расширить для трех и большего количества чисел.

Целые числа a ₁ , a ₂ ,…, a _k , где k > 2 называются взаимно простыми , если наибольший общий делитель этих чисел равен единице.

То есть если у некоторого набора целых чисел есть положительный общий делитель, отличный от единицы, то эти целые числа не являются взаимно простыми.

Любая совокупность простых чисел составляет набор взаимно простых чисел, например, 2, 3, 11, 19, 151, 293 и 677 — взаимно простые числа. А четыре числа 12, −9, 900 и −72 не являются взаимно простыми, так как у них есть положительный общий делитель 3. Числа 17, 85 и 187 тоже не взаимно простые, потому что каждое из них можно разделить на 17.

Как определить взаимно простые числа:

• найти наибольший общий делитель этих чисел,
• сделать вывод на основании определения взаимно простых чисел.

Пример 2

Являются ли числа 331, 463 и 733 взаимно простыми?

Заглянем в таблицу простых чисел. Видим, что 331, 463 и 733 — простые. Значит, у них есть единственный положительный общий делитель — единица. Поэтому, 331, 463 и 733 есть взаимно простые числа.

Пример 3

Доказать, что числа −14, 105, −2 107 и −91 не являются взаимно простыми.

Найдем НОД заданных чисел и убедимся, что он не равен единице.

Делители целых отрицательных чисел совпадают с делителями соответствующих противоположных чисел. Поэтому НОД (−14, 105, 2 107, −91) = НОД (14, 105, 2 107, 91). Посчитаем:

НОД (14, 105, 2 107, 91) = 7.

Мы получили, что наибольший общий делитель исходных чисел равен семи, поэтому эти числа не являются взаимно простыми. Доказали.

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

У взаимно простых чисел есть определенные свойства. Рассмотрим основные свойства взаимно простых чисел.

Свойство 1

Числа, которые получились при делении целых чисел a и b на их наибольший общий делитель, называются взаимно простыми. То есть, a : НОД (a, b) и b : НОД (a, b) — взаимно простые.

Это свойство взаимно простых чисел помогает находить пары взаимно простых чисел. Для этого достаточно взять два любых целых числа и разделить их на наибольший общий делитель. В результате получим взаимно простые числа.

Свойство 2

Необходимое и достаточное условие взаимной простоты чисел a и b — это наличие таких целых чисел u₀ и v₀ , при которых будет верным равенство au₀ + bv₀ = 1.

Докажем эту необходимость:

Пусть числа a и b взаимно простые. Тогда по определению взаимно простых чисел НОД (a, b) = 1. А из свойств НОД мы знаем, что для целых чисел a и b верно соотношение Безу au₀ + bv₀ = НОД (a, b). Следовательно, au₀ + bv₀ = 1.

Соотношение Безу — представление НОД целых чисел в виде их линейной комбинации с целыми коэффициентами.

Докажем достаточность:

Пусть верно равенство au₀ + bv₀ = 1. Так как НОД (a, b) делит и a и b, то НОД (a, b) в рамках свойств делимости может делить сумму au₀ + bv₀ , а значит, и единицу. А это возможно только когда НОД (a, b) = 1. Следовательно, a и b — взаимно простые числа.

Свойство 3

Если числа a и b взаимно простые, и произведение ac делится на b — значит c делится на b.

Действительно, так как a и b взаимно простые, то из предыдущего свойства у нас есть равенство au₀ + bv₀ = 1. Если умножть обе части этого равенства на c, получится acu₀ + bcv₀ = c.

Первое слагаемое суммы acu₀ + bcv₀ делится на b, так как ac делится на b по условию, второе слагаемое этой суммы также делится на b, так как один из множителей равен b. Можно сделать вывод, что вся сумма делится на b. А так как сумма acu₀ + bcv₀ равна c, то и c делится на b.

Свойство 4

Если числа a и b взаимно простые, то НОД (ac, b) = НОД (c, b).

Покажем, во-первых, что НОД (ac, b) делит НОД (c, b), а во-вторых, что НОД (c, b) делит НОД (ac, b), это и будет доказывать равенство НОД (ac, b) = НОД (c, b).

НОД (ac, b) делит и ac и b, а так как НОД (ac, b) делит b, то он также делит и bc. То есть, НОД (ac, b) делит и ac и bc, следовательно, в силу свойств наибольшего общего делителя он делит и НОД (ac, bc), который по свойствам НОД равен c * НОД (a, b) = c. Таким образом, НОД (ac, b) делит и b и c, следовательно, делит и НОД (c, b).

С другой стороны, НОД (c, b) делит и c и b, а так как он делит с, то также делит и ac. Поэтому НОД (c, b) делит и ac и b, следовательно, делит и НОД (ac, b).

Так мы показали, что НОД (ac, b) и НОД (c, b) взаимно делят друг друга, значит, они равны.

Свойство 5

Если числа из последовательности a₁ , a₂ , …, a_k будут взаимно простыми с каждым из чисел b₁ , b₂, …, b_m (где k и m — некоторые натуральные числа), то произведения a₁ * a₂ *…*a_k и b₁ *b₂ *…*b_m есть взаимно простые. В частности, если a₁ = a₂ =…= a_k = a и b₁ = b₂ =…= b_m = b, то a_k и b_m — взаимно простые числа.

Предыдущее свойство взаимно простых чисел поможет намзаписать ряд равенств вида:

НОД (a₁ *a₂ *…*a_k , b_m ) = НОД (a₂ *…*a_k , b_m ) =…= НОД (a_k , b_m ) = 1, где последний переход возможен, так как a_k и b_m взаимно простые по условию.

Так мы получили равенство НОД (b₁ *b₂ *…*b_m , a₁ *a₂ *…*a_k ) = 1, которое доказывает, что произведения a₁ *a₂ *…*a_k и b₁ *b₂ *…*b_m являются взаимно простыми.

Определение попарно простых чисел

Через взаимно простые числа можно дадим определение попарно простых чисел.

Попарно простые числа — это последовательность целых чисел a ₁ , a ₂ , …, a _k , где каждое число будет взаимно простым по отношению к остальным.

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

• 14, 9, 17, и −25 — попарно простые, так как пары чисел 14 и 9, 14 и 17, 14 и −25, 9 и 17, 9 и −25, 17 и −25 представляют из себя взаимно простые числа.

При этом, взаимно простые числа далеко не всегда могут быть попарно простыми. Подтвердим на примере. 8, 16, 5 и 15 не являются попарно простыми, так как числа 8 и 16 не взаимно простые. Однако, 8, 16, 5 и 15 — взаимно простые. Таким образом, 8, 16, 5 и 15 — взаимно простые, но не попарно простые.

Остановимся на понятии совокупности некоторого количества простых чисел. Эти числа всегда являются и взаимно простыми и попарно простыми. Например, 71, 443, 857, 991 — и попарно простые, и взаимно простые.

Когда речь идет о двух целых числах, то для них понятия «попарно простые» и «взаимно простые» совпадают.

Взаимно простые числа — определение, свойства и примеры

Чтобы доказать, что числа взаимно простые (ВПЧ), учитываются их свойства. Запись считается правдивой, если выполняется одно из следующих условий: значение НОД равно 1, в задачах используются попарно ВПЧ. Чтобы понять слово «делитель», рассматривается конкретный пример: у 24 и 54 этот показатель равен 6. НОД может являться то число, на которое делятся без остатка m и n.

Показатель существует, и он определён, если значение m или n отлично от нуля. Понятие записывается различным набором символов. Рекомендуется следовать следующими записями:

• (m, n);
• gcd (m, n).

НОД (m, n) делится на все общие делители m и n. Если соблюдается условие для а: НОД (a, b)(a, b) и для b: НОД (a, b)(a, b), значит a и b — ВПЧ. С помощью такого свойства легко определяются подходящие пары.

Составные цифры

Два числа относительно друг друга будут взаимно простыми всегда. Аналогичные отношения формируются между составными цифрами. Возможно, что из пары m или n одно — составное, а другое — простое, либо две цифры составные (натуральные числа, у которых есть больше двух делителей). Чтобы подтвердить каноническое утверждение, рассматривается пара из 9 и 88. Её простота доказывается путём вычисления НОД.

Разложение 88: ±1, ±2, ±4, ±8±1, ±2, ±4, ±8. НОД (9): ±1, ±3, ±9±1, ±3, ±9. Из двух вариантов выбираются общие цифры, а из списка определяется самая большая. Из полного перечня подходит единица.

На практике часто определяется ВПЧ двух целых цифр. Алгоритм решения задач заключается в поиске НОД, его сравнении с единицей. Чтобы быстро и правильно найти пару, используется таблица, в которой есть числа, кратные одному и сами себе.

Описание нескольких групп признаков делимости (ПД) неизвестной а:

1. ПД для 2, 4 вычисляется по последней цифре (самый маленький делитель равен двум).
2. ПД на 3, 37 зависит от суммы цифр, из которых состоит число.
3. Признак для 7 определяется после нахождения множителя, попарной суммы либо выполнения иных действий над цифрами а.
4. ПД для 6, 12, 14. Основывается на иных признаках.

Задачи и доказательства

Числа a1, a2, …, akу, у которых есть положительный НОД, больший 11, не являются между собой взаимно обратными. Пример с последующей проверкой: 99, 17−99, 17 и −27−27 — простые. Любое количество цифр будет ВПЧ по отношению к другим членам совокупности. Но 12, −9, 90012, −9, 900 и −72−72 к этой категории не относятся.

Первое задание

Нужно найти число из 4 цифр, кратное 15. Это не дробь, знаменателя нет, но произведение составляющих равняется 60. Решение: чтобы результат делился на 15 без остатка, он должен делиться на 3 и 5. Из предполагаемого списка вычёркивается нуль, так как произведение бы равнялось 0, что невозможно. Можно прийти к выводу, что последняя цифра результата — 5.

Известно, что в ответе должно быть четыре цифры, из которых одна уже известна. Нужно найти оставшиеся три, которые находятся в ряду перед пятёркой, а при их умножении получается 12. Проверка предположения: 60:5=12. Полученный результат легко представить в виде нескольких вариантов со следующими тремя множителями:

• 1, 3 и 4;
• 1, 2 и 6;
• 2, 2 и 3.

По условию задачи, результат должен делиться на 15. Поэтому ответ будет состоять из трёх вариантов: 3225, 2325 и 2235.

Второй пример

Из 181615121 нужно зачеркнуть 3 цифры так, чтобы результат был кратным 12. Множители делителя: 3 и 4. Если их вычеркнуть, заданное число разделится на три и четыре, что объясняется их ПД:

1. M кратно 4, если последние две цифры равны нулю либо их сумма делится на четыре без остатка.
2. Если сумма составляющих цифр делится на три, тогда и само число кратно трём.

Учитывая ПД на 4, можно прийти к выводу, что последние две цифры из заданного числа не делятся на четыре. Поэтому из 181615121 вычёркивается единица.

Чтобы разделить 181615121 на три, необходимо просуммировать все составляющие, разделив на 3. Результат суммы равен 25 (3х8). Так как условие выполняется, вычеркивается последняя единица.

Воспользовавшись признаками делимости на 3 и 4, можно составить следующие уравнения:

1. 25 = 3×8 + 1. Если вычеркнуть один, условия задачи не будут соблюдены, так как нужно удалить ещё две цифры.
2. 25 = 3×7 + 4. Не подходит, так как при сложении не получается 4.
3. 25 = 3×6 + 7. Если вычеркнуть шестую цифру либо единицу, кроме последней, сумма двух удалённых из списка будет равна семи.

Ответ: 181512, 811512 либо 181152.

Третье и четвёртое задания

Пример 3: необходимо определить шестизначное число, для записи которого используются 0 и 6, а также оно делится на 90. Решение: составляется уравнение 90 = 10х9. Результат делится на 9 и 10. В конце находится нуль, а сумма составных цифр делится на девять. Для записи используются три шестёрки, так как 3 х 6=18, а 18 кратно 9. Ответы: 666000, 660600, 606060, 600660.

Пример 4: нужно определить четырёхзначное число, которое делится на 45 без остатка. Все составные цифры разные и нечётные. Решение: следует составить уравнение с учётом условия задачи. Так как 45 = 9х5, то результат делится на пять и на девять. Одновременно он должен оканчиваться на 5, так как нуль считается чётным. Первые три цифры: 1, 3, 7, 9. Из списка выбираются те три числа, которые в сумме с пятёркой делятся на 9. К ним относятся: 1, 3, 9 и 5. Ответы: 9135, 3915,1935, 1395, 3195.

В условиях некоторых задач говорится о попарно простых числах (ППЧ). Понятие распространяется на последовательность целых цифр a1, a2, …, aka1, a2, …, ak, где каждая взаимно простая относительно других. Пример последовательности: 14, 9, 1714, 9, 17, и −25−25. Любая пара из списка будет взаимно простой. Последнее условие считается обязательным для ППЧ, но взаимно простые попарны не в каждом случае.

Другое понятие, которое встречается в задачах на рассматриваемую тему — совокупность ПЧ. Такие цифры всегда попарно и взаимно простые. Пример последовательности: 1, 443, 857, 99171, 443, 857, 991. У любой такой последовательности понятия попарности и взаимности совпадают.

Как находить в 6 классе взаимно простые числа и что это такое

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

Общие сведения

В системе счисления и мер используется специальная система знаков, называемая цифрами. Слово «цифра» происходит от латинского cifra. Интересно, что на арабском термин пишется как صفر‎, что в дословном переводе на русский язык обозначает «пустой». С этих символов формируются числа. Чтобы разобраться в отличиях одних от других, нужно запомнить 3 утверждения:

1. Всего существует 10 цифр — 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
2. Из десяти символов формируют числа.
3. Цифры — это знаки, а числа — абстракции, обозначающие количество.

Нужно знать, что существует несколько систем счисления. В России принято использовать арабскую. В церковнославянском и древнегреческом применяли запись буквами. Её до сих пор используют в иврите. В программировании применяется смешанная запись. Так как она шестнадцатеричная, используют комбинации знаков: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Итак, «число» и «цифра» разные понятия по происхождению. Первое используют как единицу счёта. Им выражают количество. Второй же параметр применяют для обозначений значений. Для записи в международном формате принята арабская последовательность от 0 до 9, но в некоторых случаях ставят и римские символы — I, II, III, IV, V, V I, V II, V III, IX, X и так далее.

По своему виду числа бывают:

• натуральными — простыми целыми, использующимися при счёте,
• рациональными — конечными дробными отношениями,
• иррациональными — бесконечными непериодическими дробями,
• действительными — образующими множество, включающее рациональные и иррациональные значения.

Свойства и определение

Существует правило, объясняющее, какие числа называются взаимно простыми. Согласно ему, это 2 целых натуральных значения, у которых самый большой общий делитель не превышает единицу. Из этого правила следует, что 2 таких выражения будут иметь только лишь один общий делитель, при этом равняться он будет единице. Например, можно рассмотреть 5 и 11. Разделить их без остатка можно или самих на себя или единицу.

Понятие взаимности простых чисел справедливо как для пары выражений, так и большего их числа. Два натуральных числа, стоящие один за одним, всегда будут взаимными. Например, 13 и 14 — простая пара, такая же как 23 и 24.

Это легко можно доказать, используя то, что 2 натуральных значения a и b делятся на одно и то же натуральное число, превышающее единицу, если их разница будет делиться на это выражение. Так как a и b — 2 соседних значения, для удобства можно принять что a &lt,b, то b — a = 1. Исходя из того, что один делится только на себя, a и b не будут иметь других общих делителей, кроме единицы.

Из определения о взаимных значениях следует, что любые простые величины всегда окажутся взаимными. Ведь делителями любого простого выражения являются лишь оно само и 1. Кстати, такие значения обозначают так: (a, b) = 1.

Из признаков и свойств можно выделить:

1. Меньшее из возможных общих кратных пары взаимно простых выражений равняется их результату перемножения. Например, (3, = 1. То есть они взаимные. Их наименьшее кратное равно 24. Действительно, если попробовать методом перебора подобрать меньшее значение, найти его будет невозможно.
2. Если числа a и b простые, и существует число c, которое кратно им двоим, оно будет делиться без остатка на результат умножения a * b. Например, (3, 10) = 1, число 60 кратно как трём, так и десяти, а также кратно 30 (3 x 10).
3. Когда числа a и b простые, и имеется такая величина, как b (c b), выражение a * c также будет: b (ac b). Например, (2, 17) = 1, а * c = 34. 34 кратно b, то есть 17. Тогда: a * c = 2 * 34 = 68. Проверить результат легко. Нужно его просто разделить на кратную величину: 68 ÷ 17 = 4. Так как в ответе целое, 68 кратно 17.

Здесь важно понять, что натуральные значения будут взаимными, если их общий делитель равняется единице. Вот пример пары таких чисел: 2 и 5, 13 и 16, 35 и 88 или 7, 9, 16.

Таблица и примеры

Часто попадаются задачи, в которых требуется доказать, что целые числа будут взаимно простыми. Доказательство сводится к нахождению наибольшего общего делителя для заданных условием данных. Затем результат проверяют на равенство единице.

Нужно доказать, что делитель не совпадает с членами выражения. Если это не так, произведение k1* k2 *… * kn можно поделить на kn+1. Но на него делится и число k, определяемое суммой k1 * k2 *…* kn+1. Следовательно на kn+1 должно разделиться и второе слагаемое, которое равно одному, а это невыполнимо. То есть всегда может быть новое простое число, не стоящее среди любого количества наперёд заданных простых чисел. Проверка предположения выполнена.

Перед выполнением действий полезно проверить заданные выражения по таблице взаимно простых чисел. Эта таблица строится на том, что если исходные целые значения являются простыми, значит, их НОД равен единице. Обычно в книгах таблица заканчивается 1000. Но такую таблицу можно составить не только до тысячи, но и до сколь угодно большего значения, поэтому она является бесконечно большой. Проверить, что ряд простых значений может быть бесконечным, довольно просто.

Доказательство строится на обратном. Пусть количество простых величин ограничено n штуками. Если имеется значение k, равное k1 * k2 *… * kn+1, оно отлично от каждого из входящих в многочлен. Когда k — простое число, утверждение будет доказано. Должен существовать простой делитель этого числа kn+1.

Как пример, можно привести 3 значения: −99, 17 и −27. Они взаимные, так как любая совокупность простых величин составляет набор взаимности. Например, 2, 3, 11, 19, 151, 293 и 677. А вот такие значения как 12, −72 не являются взаимными, так как у них есть общее делимое 3, и оно отлично от единицы.

Таким образом, чтобы определить взаимность, необходимо попробовать разложить значения на простые множители. Например, пара состоящая из 8 и 15 будет взаимной, хотя сами числа не являются простыми. То же самое, можно сказать, о 8, 15 и 49. В то же время 6, 8 и 9 хоть и взаимные, но они не будут парно простыми.

Зная, какие выражения попарно взаимные, а какие нет, можно определить возможность сокращения дроби. Интересно, что количество зубцов на звёздочках в цепи передачи стремятся делать взаимно простыми. Это помогает обеспечить равномерность износа: каждый зубец будет входить в звенья цепи по очереди.