Докажите что числа 432 и 385 взаимно простые

Информация о числах

Свойства и характеристики одного числа
Все делители числа, сумма и произведение цифр, двоичный вид, разложение на простые множители.

Свойства пары чисел
Наименьшее общее кратное, наибольший общий делитель, сумма, разность и произведение чисел.

Сейчас изучают числа:

Числа 432 и 385

Четыреста тридцать два и триста восемьдесят пять

Описание

Числа 432 и 385 в сумме – 817 и имеют разницу 47.
Частное от деления 432 на 385

1.122078. При делении 432 на 385 образуется остаток 47. Произведение чисел – 166320.

Источник

Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел

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

Вообще чтобы найти наибольший общий делитель данных чисел:

1) представляют каждое данное число в каноническом виде;

2) образуют произведение общих для всех данных чисел простых множителей, каждый с наименьшим показателем, каким он входит во все разложения данных чисел;

3) находят значение этого произведения – оно и будет наибольшим общим делителем данных чисел.

Найдем наименьшее общее кратное чисел 3600 и 288. В его разложение должны войти все простые множители, которые содержатся хотя бы в одном из разложений чисел 3600 и 288, причем каждый из них нужно взять с наибольшим показателем, с каким он входит в оба разложения. Следовательно, К(3600, 288) = 2 5 ×3 2 ×5= 7200.

Вообще чтобы найти наименьшее общее кратное данных чисел.

1) представляют каждое данное число в каноническом виде;

2) образуют произведение всех простых множителей, находящихся в разложениях данных чисел, каждый с наибольшим показателе с каким он входит во все разложения данных чисел;

3) находят значения этого произведения, оно и будет наименьшим общим кратным данных чисел.

Задача 1. Найти наибольший общий делитель и наименьшее общее кратное чисел 60, 252 и 264.

Решение. Представим каждое число в каноническом виде: 60 = 2 2 ×3×5, 252 = 2 2 ×3 2 ×7, 264 = 2 3 ×3×11.

Чтобы найти наибольший общий делитель данных чисел, образуем произведение общих для всех данных разложений простых множителей каждый с наименьшим показателем, с каким он входит во все решения данных чисел: D (60, 252, 264) = 2 2 × 3 = 12.

Наименьшее общее кратное чисел можно найти, образовав произведение всех простых множителей, находящихся в данных разложениях, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел, т.е. К(60, 252, 264) = 2 3 ×3 2 ×5×7×11 = 27720.

Задача 2. Найти наибольший общий делитель и наименьшее общее кратное чисел 48 и 245.

Так как разложения данных чисел не содержат общих простых множителей, то D (48, 245) = 1, а K(48, 245) = 48×245 = 10760.

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

1. Если а делится на b, то D (а, b) = b.

2. Если а = bq + r и r b.

Если а делится на b, то D (а, b) = b.

Если при делении а на b, получается остаток r, то а = bq + r и D(а, b) = D(b, r) и задача свелась к отысканию наибольшего общего делителя чисел b и r.

Если b делится на r, то D(b, r)=r и тогда D(а, b) = r.

Продолжая описанный процесс, получаем все меньшие и меньшие остатки. В конце концов получим остаток, на который будет делиться предыдущий остаток. Этот наименьший, отличный от нуля, остаток и будет наибольшим общим делителем чисел а и b.

Найдем при помощи алгоритма Евклида наибольший общий делитель чисел 2585 и 7975. Процесс последовательного деления будем записывать так:

В последнем случае остаток равен нулю. Значит, D(7975, 2585) = 55.

Упражнения

1. Найдите наибольший общий делитель и наименьшее общее кратное данных чисел, представив их в каноническом виде:

2. Используя алгоритм Евклида, найдите наибольший общий делитель чисел.

а) 846 и 246; б) 585 и 1960; в) 15283 и 10013.

3. Верно ли, что: а) D(448, 656) = 16; б) K(578, 8670) = 8670?

4. Докажите, что числа 432 и 385 взаимно простые.

5. Найдите наибольший общий делитель всех пятизначных чисел, записанных при помощи цифр 1, 2, 3, 4, 5 (цифры в записи чисел не повторяются).

Не нашли, что искали? Воспользуйтесь поиском:

Источник

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

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

Сначала определимся, что значит простое число.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 1

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

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

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

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

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

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

Любая совокупность простых чисел составляет набор взаимно простых чисел, например, 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 взаимно простые. Тогда по определению взаимно простых чисел НОД (a, b) = 1. А из свойств НОД мы знаем, что для целых чисел a и b верно соотношение Безу au₀ + bv₀ = НОД (a, b). Следовательно, au₀ + bv₀ = 1.

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

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

Свойство 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

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

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

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

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

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

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

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

Источник

Презентация по математике «Способы нахождения НОД и НОК»

Описание разработки

Нахождение НОД.

1. Представить каждое число в каноническом виде.

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

3. Находят значение этого произведения – оно и будет наибольшим общим делителем данных чисел.

Нахождение НОК.

1. Представить каждое число в каноническом виде.

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

3. Найти значение этого произведения – оно и будет наименьшим общим кратным данных чисел.

1. Найдите НОД и НОК чисел, представив их в каноническом виде:

2. Используя алгоритм Евклида, найдите НОД чисел:

4. Докажите, что числа432 и 385 взаимно простые.

5. Найдите НОД всех пятизначных чисел, записанных при помощи цифр 1,2,3,4,5 (цифры в записи чисел не повторяются).

Содержимое разработки

Способы нахождения НОК и НОД

Алгоритм Евклида НОД (7975,2585)= 55

1. Найдите НОД и НОК чисел, представив их в каноническом виде: а) 948 и 624; б) 120,540,418. 2. Используя алгоритм Евклида, найдите НОД чисел: а)846, 246; б)585, 1960; в)15283, 10013. 3. Верно ли, что: а) НОД(448, 656)=16; б) НОК(578, 8670)=8670? 4. Докажите, что числа432 и 385 взаимно простые. 5. Найдите НОД всех пятизначных чисел, записанных при помощи цифр 1,2,3,4,5 (цифры в записи чисел не повторяются).

Ответ: 547 Указание. Тарелок 10n+7 или 12m+7. Значит, убирая 7 тарелок получаем число, делящееся на НОК (10, 12) = 60. т.е. число тарелок записывается как 60k+7.

2. Найдите все пары натуральных чисел, наименьшее общее кратное которых равно 78, а наибольший общий делитель равен 13.

3. Найти наименьшее натуральное число, большее 1 и дающее при делении на 2, 3, 4, 5, 6 остаток, равный 1.

Ответ: 61. Указание. Вычтем из искомого числа 1, тогда оно делится на 2, 3, 4. 5, 6, т.е.делится на НОД(2,3,4,5,6)=60.

4. Найти натуральные числа a и b, если НОД(a, b)=6, а НОК(a, b) = 90.

Ответ: (6; 90) или (18; 30) Указание. Очевидно, что a=6m, b=6n, где НОД(m, n) = 1. Поэтому НОК(a, b) = 6mn= 90, откуда mn = 15. Значит, возможны варианты (m,n)=(1,15), (3, 5) и наоборот.

Решить в натуральных числах уравнения:

2. Подготовиться к проверочной работе (практической).

Источник

Презентация по математике «Способы нахождения НОД и НОК»

Описание разработки

Нахождение НОД.

1. Представить каждое число в каноническом виде.

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

3. Находят значение этого произведения – оно и будет наибольшим общим делителем данных чисел.

Нахождение НОК.

1. Представить каждое число в каноническом виде.

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

3. Найти значение этого произведения – оно и будет наименьшим общим кратным данных чисел.

1. Найдите НОД и НОК чисел, представив их в каноническом виде:

2. Используя алгоритм Евклида, найдите НОД чисел:

4. Докажите, что числа432 и 385 взаимно простые.

5. Найдите НОД всех пятизначных чисел, записанных при помощи цифр 1,2,3,4,5 (цифры в записи чисел не повторяются).

Содержимое разработки

Способы нахождения НОК и НОД

Алгоритм Евклида НОД (7975,2585)= 55

1. Найдите НОД и НОК чисел, представив их в каноническом виде: а) 948 и 624; б) 120,540,418. 2. Используя алгоритм Евклида, найдите НОД чисел: а)846, 246; б)585, 1960; в)15283, 10013. 3. Верно ли, что: а) НОД(448, 656)=16; б) НОК(578, 8670)=8670? 4. Докажите, что числа432 и 385 взаимно простые. 5. Найдите НОД всех пятизначных чисел, записанных при помощи цифр 1,2,3,4,5 (цифры в записи чисел не повторяются).

Ответ: 547 Указание. Тарелок 10n+7 или 12m+7. Значит, убирая 7 тарелок получаем число, делящееся на НОК (10, 12) = 60. т.е. число тарелок записывается как 60k+7.

2. Найдите все пары натуральных чисел, наименьшее общее кратное которых равно 78, а наибольший общий делитель равен 13.

3. Найти наименьшее натуральное число, большее 1 и дающее при делении на 2, 3, 4, 5, 6 остаток, равный 1.

Ответ: 61. Указание. Вычтем из искомого числа 1, тогда оно делится на 2, 3, 4. 5, 6, т.е.делится на НОД(2,3,4,5,6)=60.

4. Найти натуральные числа a и b, если НОД(a, b)=6, а НОК(a, b) = 90.

Ответ: (6; 90) или (18; 30) Указание. Очевидно, что a=6m, b=6n, где НОД(m, n) = 1. Поэтому НОК(a, b) = 6mn= 90, откуда mn = 15. Значит, возможны варианты (m,n)=(1,15), (3, 5) и наоборот.

Решить в натуральных числах уравнения:

2. Подготовиться к проверочной работе (практической).

Источник