Как найти общий делитель двух целых чисел - Сайт, где вы сможете решить свои вопросы

Загрузить PDF

Наибольший общий делитель (НОД) двух целых чисел – это наибольшее целое число, на которое делится каждое из этих чисел. Например, НОД для 20 и 16 равен 4 (как 16, так и 20 имеют большие делители, но они не являются общими – например, 8 делитель 16, но не делитель 20). Существует простой и системный метод для нахождения НОД, называемый “алгоритм Евклида”. Эта статья расскажет вам, как находить наибольший общий делитель двух целых чисел.

1

Опустите любые знаки минус.
2
Выучите терминологию: при делении 32 на 5,
- 32 – делимое
- 5 – делитель
- 6 – частное
- 2 – остаток
3

Определите большее из чисел. Оно будет делимым, а меньшее число – делителем.
4

Запишите такой алгоритм: (делимое) = (делитель) * (частное) + (остаток)
5

Поставьте большее число на место делимого, а меньшее – на место делителя.
6

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

Найдите остаток и впишите его в соответствующую позицию в алгоритме.
8

Запишите алгоритм снова, но (A) запишите предыдущий делитель как новое делимое, а (B) предыдущий остаток как новый делитель.
9

Повторяйте предыдущий шаг до тех пор, пока остаток не равен 0.
10

Последний делитель и будет наибольшим общим делителем (НОД).
11

Например, найдем НОД для 108 и 30:
12

Обратите внимание, как числа 30 и 18 из первой строки образуют вторую строку. Затем 18 и 12 образуют третью строку, а 12 и 6 образуют четвертую строку. Кратные 3, 1, 1 и 2 не используются. Они представляют собой число раз, которые делимое делится на делитель, и поэтому уникальны для каждой строки.

Реклама

1

Опустите любые знаки минус.
2
Найдите простые множители чисел. Представьте их так, как показано на рисунке.
- Например, для 24 и 18:
  - 24- 2 x 2 x 2 x 3
  - 18- 2 x 3 x 3
- Например, для 50 и 35:
  - 50- 2 x 5 x 5
  - 35- 5 x 7
3
Найдите общие простые множители.
- Например, для 24 и 18:
  - 24- 2 x 2 x 2 x 3
  - 18- 2 x 3 x 3
- Например, для 50 и 35:
  - 50- 2 x 5 x 5
  - 35- 5 x 7
4
Перемножьте общие простые множители.
- Для 24 и 18 перемножьте 2 и 3 и получите 6. 6 – наибольший общий делитель 24 и 18.
- Для 50 и 35 нечего перемножать. 5 – единственный общий простой множитель, он и является НОДом.
5

Сделано!

Реклама

Советы

Один из способов записать это: <делимое>mod<делитель> = остаток; НОД (a,b) = b, если mod b = 0, и НОД(a,b) = НОД (b, a mod b) в противном случае.
В качестве примера найдем НОД (-77,91). Во-первых, используйте 77 вместо -77: НОД (-77,91) преобразуется в НОД (77,91). 77 меньше 91, поэтому мы должны поменять их местами, но рассмотрим то, как действует алгоритм, если мы не сделаем этого. При вычислении 77 mod 91 мы получим 77 (77 = 91 х 0 + 77). Так как это не нуль, рассматриваем ситуацию (b, a mod b), то есть НОД (77,91) = НОД (91,77). 91 mod 77 = 14 (14 является остатком). Это не нуль, поэтому НОД (91,77) становится НОД (77,14). 77 mod 14 = 7. Это не нуль, поэтому НОД (77,14) становится НОД (14,7). 14 mod 7 = 0 (так как 14/7 = 2 без остатка). Ответ: НОД (-77,91) = 7.
Описанный метод очень полезен при упрощении дробей. В описанном выше примере: -77/91 = -11/13, так как 7 является наибольшим общим делителем -77 и 91.
Если а и b равны нулю, то любое отличное от нуля число является их делителем, поэтому в этом случае НОД не существует (математики просто считают, что наибольший общий делитель 0 и 0 равен 0).

Об этой статье

Эту страницу просматривали 11 993 раза.

Была ли эта статья полезной?

Источник

Для этого термина существует аббревиатура «НОД», которая имеет и другие значения, см. Нод.

Наибольшим общим делителем (НОД) для двух целых чисел и называется наибольший из их общих делителей^[1]. Пример: для чисел 54 и 24 наибольший общий делитель равен 6.

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

Возможные обозначения наибольшего общего делителя чисел и :

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.

Связанные определения[править | править код]

Наименьшее общее кратное[править | править код]

Наименьшее общее кратное (НОК) двух целых чисел и — это наименьшее натуральное число, которое делится на и (без остатка). Обозначается НОК(m,n) или [m,n] , а в английской литературе .

НОК для ненулевых чисел и всегда существует и связан с НОД следующим соотношением:

Это частный случай более общей теоремы: если $a_{1},a_{2},dots ,a_{n}$ — ненулевые числа, — какое-либо их общее кратное, то имеет место формула:

$D=[a_{1},a_{2},dots ,a_{n}]cdot left({frac {D}{a_{1}}},{frac {D}{a_{2}}},dots ,{frac {D}{a_{n}}}right)$

Взаимно простые числа[править | править код]

Числа и называются взаимно простыми, если у них нет общих делителей, кроме pm 1 . Для таких чисел НОД. Обратно, если НОД то числа взаимно просты.

Аналогично, целые числа $a_{1},a_{2},dots a_{k}$ , где kgeq 2 , называются взаимно простыми, если их наибольший общий делитель равен единице.

Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.

Способы вычисления[править | править код]

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.

Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел и на простые множители:

$n=p_{1}^{{d_{1}}}cdot dots cdot p_{k}^{{d_{k}}},$

$m=p_{1}^{{e_{1}}}cdot dots cdot p_{k}^{{e_{k}}},$

где $p_{1},dots ,p_{k}$ — различные простые числа, а $d_{1},dots ,d_{k}$ и $e_{1},dots ,e_{k}$ — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(n,m) и НОК[n,m] выражаются формулами:

$(n,m)=p_{1}^{{min(d_{1},e_{1})}}cdot dots cdot p_{k}^{{min(d_{k},e_{k})}},$

$[n,m]=p_{1}^{{max(d_{1},e_{1})}}cdot dots cdot p_{k}^{{max(d_{k},e_{k})}}.$

Если чисел более двух: $a_{1},a_{2},dots a_{n}$ , их НОД находится по следующему алгоритму:

$d_{2}=(a_{1},a_{2})$

$d_{3}=(d_{2},a_{3})$

………

$d_{n}=(d_{{n-1}},a_{n})$

— это и есть искомый НОД.

Свойства[править | править код]

Основное свойство: наибольший общий делитель и делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
Если делится на , то НОД(m, n) = n. В частности, НОД(n, n) = n.
. В общем случае, если , где – целые числа, то .
— общий множитель можно выносить за знак НОД.
Если , то после деления на числа становятся взаимно простыми, то есть, $left({{frac {m}{D}},{frac {n}{D}}}right)=1$ . Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
Мультипликативность: если $a_{1},a_{2}$ взаимно просты, то:

$(a_{1}cdot a_{2},b)=(a_{1},b)cdot (a_{2},b)$

left{acdot m+bcdot nmid a,bin mathbb{Z } right}

и поэтому

представим в виде линейной комбинации чисел

Это соотношение называется соотношением Безу, а коэффициенты

— коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы

, порождённая набором ${a_{1},a_{2},dots ,a_{n}}$

, — циклическая и порождается одним элементом: НОД(a₁, a₂, … , a_n).

Вариации и обобщения[править | править код]

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

Наибольшим общим делителем НОД(a, b) называется тот общий делитель, который делится на все остальные общие делители

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

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

a=4=2cdot 2=left(1+{sqrt {-3}}right)left(1-{sqrt {-3}}right),qquad b=left(1+{sqrt {-3}}right)cdot 2.

В евклидовых кольцах наибольший общий делитель всегда существует и определён с точностью до делителей единицы, то есть количество НОД равно числу делителей единицы в кольце.

См. также[править | править код]

Бинарный алгоритм вычисления НОД
Делимость
Алгоритм Евклида
Наименьшее общее кратное

Литература[править | править код]

Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Примечания[править | править код]

↑ Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3. страница 857

Источник

Download Article

The Greatest Common Divisor (GCD) of two whole numbers, also called the Greatest Common Factor (GCF) and the Highest Common Factor (HCF), is the largest whole number that’s a divisor (factor) of both of them. For instance, the largest number that divides into both 20 and 16 is 4. (Both 16 and 20 have larger factors, but no larger common factors — for instance, 8 is a factor of 16, but it’s not a factor of 20.) In grade school, most people are taught a “guess-and-check” method of finding the GCD. Instead, there is a simple and systematic way of doing this that always leads to the correct answer. The method is called “Euclid’s algorithm.” If you want to know how to truly find the Greatest Common Divisor of two integers, see Step 1 to get started.^[1]

1

Drop any negative signs.
2
Know your vocabulary: when you divide 32 by 5,^[2]
- - 32 is the dividend
  - 5 is the divisor
  - 6 is the quotient
  - 2 is the remainder (or modulo).
Advertisement
3

Identify the larger of the two numbers. That will be the dividend, and the smaller the divisor.^[3]
4

Write out this algorithm: (dividend) = (divisor) * (quotient) + (remainder)^[4]
5

Put the larger number in the spot for dividend, and the smaller number as the divisor.^[5]
6

Decide how many times the smaller number will divide into the larger number, and drop it into the algorithm as the quotient.
7

Calculate the remainder, and substitute it into the appropriate place in the algorithm.^[6]
8

Write out the algorithm again, but this time A) use the old divisor as the new dividend and B) use the remainder as the new divisor.
9

Repeat the previous step until the remainder is zero.
10

The last divisor is the greatest common divisor.
11

Here is an example, where we are trying to find the GCD of 108 and 30:
12

Notice how the 30 and the 18 in the first line shift positions to create the second line. Then, the 18 and 12 shift to create the third line, and the 12 and 6 shift to create the fourth line. The 3, 1, 1, and 2 that follow the multiplication symbol do not reappear. They represent how many times the divisor goes into the dividend, so they are unique to each line.

1

Drop any negative signs.^[7]
2
Find the prime factorization of the numbers, and list them out as shown.^[8]
- Using 24 and 18 as the example numbers:
  - 24- 2 x 2 x 2 x 3
  - 18- 2 x 3 x 3
- Using 50 and 35 as the example numbers:
  - 50- 2 x 5 x 5
  - 35- 5 x 7
3
Identify all common prime factors.
- Using 24 and 18 as the example numbers:
  - 24- 2 x 2 x 2 x 3
  - 18- 2 x 3 x 3
- Using 50 and 35 as the example numbers:
  - 50- 2 x 5 x 5
  - 35- 5 x 7
4
Multiply the common factors together.^[9]
- In the case of 24 and 18, multiply 2 and 3 together to get 6. Six is the greatest common factor of 24 and 18.
- In the case of 50 and 35, there is nothing to multiply. 5 is the only common factor, and therefore the greatest.
5

Finished.

Add New Question

Question

How do I find the gcd of three integers?

Find all of the divisors of each of the integers, and note the largest one that’s common to all three.
Question

How do I round off 93,678,563 to the nearest 10,000?

Look at the digit in the 1,000’s place: it’s 8, so you round up to 93,680,000.
Question

What is a multiplicative inverse?

A multiplicative inverse is the reciprocal of a number.

See more answers

Ask a Question

200 characters left

Include your email address to get a message when this question is answered.

Submit

One way to write this, using the notation <dividend> mod <divisor> = the remainder is that GCD(a,b) = b if a mod b = 0, and GCD(a,b) = GCD(b, a mod b) otherwise.
As an example, let’s find GCD(-77,91). First, use 77 instead of -77, so GCD(-77,91) becomes GCD(77,91). Now, 77 is less than 91, so we should swap them, but let’s see how the algorithm takes care of that if we don’t. When we calculate 77 mod 91, we get 77 (since 77 = 91 x 0 + 77). Since that’s not zero, we switch (a, b) for (b, a mod b) and that gives us: GCD(77,91) = GCD(91,77). 91 mod 77 gives 14 (remember, that means 14 is the remainder). Since that’s not zero, swap GCD(91,77) for GCD(77,14). 77 mod 14 gives 7 which is not zero, so swap GCD(77,14) for GCD(14,7). 14 mod 7 is zero, since 14 = 7 * 2 with no remainder, so we stop. And that means: GCD(-77,91) = 7.
This technique is very useful when reducing fractions. By the above example, the fraction -77/91 reduces to -11/13 because 7 is the greatest common divisor of -77 and 91.

Show More Tips

Thanks for submitting a tip for review!

About This Article

Thanks to all authors for creating a page that has been read 601,253 times.

Did this article help you?

Источник

Эта статья посвящена такому вопросу, как нахождение наибольшего общего делителя. Сначала мы объясним, что это такое, и приведем несколько примеров, введем определения наибольшего общего делителя 2, 3 и более чисел, после чего остановимся на общих свойствах данного понятия и докажем их.

Что такое общие делители

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

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

Определение 1

Общим делителем нескольких целых чисел будет такое число, которое может быть делителем каждого числа из указанного множества.

Пример 1

Вот примеры такого делителя: тройка будет общим делителем для чисел -12 и 9, поскольку верны равенства 9=3·3 и −12=3·(−4). У чисел 3 и -12 есть и другие общие делители, такие, как 1, −1 и −3. Возьмем другой пример. У четырех целых чисел 3, −11, −8 и 19 будет два общих делителя: 1 и -1.

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

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

Что такое наибольший общий делитель (НОД)

Согласно свойствам делимости, если b является делителем целого числа a, которое не равно 0, то модуль числа b не может быть больше, чем модуль a, следовательно, любое число, не равное 0, имеет конечное число делителей. Значит, число общих делителей нескольких целых чисел, хотя бы одно из которых отличается от нуля, также будет конечным, и из всего их множества мы всегда можем выделить самое большое число (ранее мы уже говорили о понятии наибольшего и наименьшего целого числа, советуем вам повторить данный материал).

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

Переходим к формулировке основного определения.

Определение 2

Наибольшим общим делителем нескольких чисел является самое большое целое число, которое делит все эти числа.

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

Пример 2

Какой можно привести пример НОД для двух целых чисел? Например, для 6 и -15 это будет 3. Обоснуем это. Сначала запишем все делители шести: ±6, ±3, ±1, а потом все делители пятнадцати: ±15, ±5, ±3 и ±1. После этого мы выбираем общие: это −3, −1, 1 и 3. Из них надо выбрать самое большое число. Это и будет 3.

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

Определение 3

Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.

Для чисел a1, a2, …, an делитель удобно обозначать как НОД (a1, a2, …, an). Само значение делителя записывается как НОД (a1, a2, …, an) =b.

Пример 3

Приведем примеры наибольшего общего делителя нескольких целых чисел: 12, -8, 52, 16. Он будет равен четырем, значит, мы можем записать, что НОД (12, -8, 52, 16) =4.

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

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

Пример 4

Так, наибольший общий делитель чисел 60, 15 и -45 равен 15, поскольку пятнадцать делится не только на 60 и -45, но и на само себя, и большего делителя для всех этих чисел не существует.

Особый случай составляют взаимно простые числа. Они представляют собой целые числа с наибольшим общим делителем, равным 1.

Основные свойства НОД и алгоритм Евклида

У наибольшего общего делителя есть некоторые характерные свойства. Сформулируем их в виде теорем и докажем каждое из них.

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

Определение 4

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

Данное свойство следует из самого определения НОД и не нуждается в доказательствах.

Определение 5

Если число a можно разделить на число b, то множество общих делителей этих двух чисел будет аналогично множеству делителей числа b, то есть НОД (a, b)=b.

Докажем это утверждение.

Доказательство 1

Если у чисел a и b есть общие делители, то на них можно разделить любое из них. В то же время если a будет кратным b, то любой делитель b будет делителем и для a, поскольку у делимости есть такое свойство, как транзитивность. Значит, любой делитель b будет общим для чисел a и b. Это доказывает, что если мы можем разделить a на b, то множество всех делителей обоих чисел совпадет с множеством делителей одного числа b. А поскольку наибольший делитель любого числа есть само это число, то наибольший общий делитель чисел a и b будет также равен b, т.е. НОД (a, b)=b. Если a=b, то НОД (a, b)=НОД (a, a)=НОД (b, b) =a=b, например, НОД (132, 132) =132.

Используя это свойство, мы можем найти наибольший общий делитель двух чисел, если одно из них можно разделить на другое. Такой делитель равен одному из этих двух чисел, на которое можно разделить второе число. К примеру, НОД (8, 24) =8, так как 24 есть число, кратное восьми.

Определение 6

Если верно равенство a=b·q+c (здесь все переменные являются целыми числами), то все общие делители двух чисел a и b будут такими же, как и у чисел b и c, то есть НОД (a, b)=НОД (b, c).

Доказательство 2

Попробуем доказать данное свойство. У нас изначально есть равенство a=b·q+c, и любой общий делитель a и b будет делить и c, что объясняется соответствующим свойством делимости. Поэтому любой общий делитель b и c будет делить a. Значит, множество общих делителей a и b совпадет с множеством делителей b и c, в том числе и наибольшие из них, значит, равенство НОД (a, b)=НОД (b, c) справедливо.

Определение 7

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

Перед тем, как сформулировать свойство, советуем вам повторить теорему, которую мы доказывали в статье о делении с остатком. Согласно ей, делимое число a можно представить в виде b·q+r, причем b здесь является делителем, q – некоторым целым числом (его также называют неполным частным), а r – остатком, который удовлетворяет условию 0≤r≤b.

Допустим, у нас есть два целых числа больше 0, для которых будут справедливы следующие равенства:

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

Эти равенства заканчиваются тогда, когда rk+1становится равен 0. Это случится обязательно, поскольку последовательность b> r1> r2> r3, … представляет собой ряд убывающих целых чисел, который может включать в себя только конечное их количество. Значит, rk является наибольшим общим делителем a и b, то есть, rk=НОД (a, b).

В первую очередь нам надо доказать, что rk– это общий делитель чисел a и b, а после этого – то, что rk является не просто делителем, а именно наибольшим общим делителем двух данных чисел.

Просмотрим список равенств, приведенный выше, снизу вверх. Согласно последнему равенству,
rk−1 можно разделить на rk. Исходя из этого факта, а также предыдущего доказанного свойства наибольшего общего делителя, можно утверждать, что rk−2 можно разделить на rk, так как
rk−1 делится на rk и rkделится на rk.

Третье снизу равенство позволяет нам сделать вывод, что rk−3 можно разделить на rk, и т.д. Второе снизу – что b делится на rk, а первое – что a делится на rk. Из всего этого заключаем, что rk– общий делитель a и b.

Теперь докажем, что rk=НОД (a, b). Что для этого нужно сделать? Показать, что любой общий делитель a и b будет делить rk. Обозначим его r0_.

Просмотрим тот же список равенств, но уже сверху вниз. Исходя из предыдущего свойства, можно заключить, что r1 делится на r0, значит, согласно второму равенству r2 делится на r0. Идем по всем равенствам вниз и из последнего делаем вывод, что rk делится на r0. Следовательно, rk=НОД (a, b).

Рассмотрев данное свойство, заключаем, что множество общих делителей a и b аналогично множеству делителей НОД этих чисел. Это утверждение, которое является следствием из алгоритма Евклида, позволит нам вычислить все общие делители двух заданных чисел.

Перейдем к другим свойствам.

Определение 8

Если a и b являются целыми числами, не равными 0, то должны существовать два других целых числа u0 и v0, при которых будет справедливым равенство НОД (a, b) =a·u0+b·v0.

Равенство, приведенное в формулировке свойства, является линейным представлением наибольшего общего делителя a и b. Оно носит название соотношения Безу, а числа u0 и v0 называются коэффициентами Безу.

Доказательство 3

Докажем данное свойство. Запишем последовательность равенств по алгоритму Евклида:

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

Первое равенство говорит нам о том, что r1=a−b·q1_. Обозначим 1=s1 и −q1=t1 и перепишем данное равенство в виде r1=s1·a+t1·b. Здесь числа s1 и t1 будут целыми. Второе равенство позволяет сделать вывод, что r2=b−r1·q2=b−(s1·a+t1·b) ·q2=−s1·q2·a+(1−t1·q2) ·b. Обозначим −s1·q2=s2 и 1−t1·q2=t2 и перепишем равенство как r2=s2·a+t2·b, где s2 и t2 также будут целыми. Это объясняется тем, что сумма целых чисел, их произведение и разность также представляют собой целые числа. Точно таким же образом получаем из третьего равенства r3=s3·a+t3·b, из следующего r4=s4·a+t4·b и т.д. В конце заключаем, что rk=sk·a+tk·b при целых sk и tk. Поскольку rk=НОД (a, b), обозначим sk=u0 и tk=v0, В итоге мы можем получить линейное представление НОД в требуемом виде: НОД (a, b) =a·u0+b·v0.

Определение 9

НОД (m·a, m·b) =m·НОД(a, b) при любом натуральном значении m.

Доказательство 4

Обосновать это свойство можно так. Умножим на число m обе стороны каждого равенства в алгоритме Евклида и получим, что НОД (m·a, m·b) =m·rk, а rk – это НОД (a, b). Значит, НОД (m·a, m·b) =m·НОД(a, b). Именно это свойство наибольшего общего делителя используется при нахождении НОД методом разложения на простые множители.

Определение 10

Если у чисел a и b есть общий делитель p, то НОД (a:p, b:p)=НОД(a, b):p. В случае, когда p=НОД (a, b) получим НОД (a:НОД(a, b), b:НОД (a, b)=1, следовательно, числа a:НОД(a, b) и b:НОД (a, b) являются взаимно простыми.

Поскольку a=p·(a:p) и b=p·(b:p), то, основываясь на предыдущем свойстве, можно создать равенства вида НОД(a, b)=НОД(p·(a:p), p·(b:p))=p·НОД(a:p, b:p), среди которых и будет доказательство данного свойства. Это утверждение мы используем, когда приводим обыкновенные дроби к несократимому виду.

Определение 11

Наибольшим общим делителем a1, a2, …, ak будет число dk, которое можно найти, последовательно вычисляя НОД (a1, a2)=d2, НОД (d2, a3) =d3, НОД (d3, a4) =d4, …, НОД (dk-1, ak) =dk.

Это свойство полезно при нахождении наибольшего общего делителя трех и более чисел. С помощью него можно свести это действие к операциям с двумя числами. Его основой является следствие из алгоритма Евклида: если множество общих делителей a1, a2 и a3 совпадает с множеством d2 и a3, то оно совпадет и с делителями d3. Делители чисел a1, a2, a3 и a4 совпадут с делителями d3, значит, они совпадут и с делителями d4, и т.д. В конце мы получим, что общие делители чисел a1, a2, …, akсовпадут с делителями dk, а поскольку наибольшим делителем числа dkбудет само это число, то НОД (a1, a2, …, ak) =dk.

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

Источник

Онлайн калькулятор НОД и НОК двух чисел

Наибольший общий делитель (НОД)

Определение НОД

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

Если натуральное число a делится на натуральное число bb, то bb называют делителем числа aa, а число aa называют кратным числа bb. aa и bb являются натуральными числами. Число gg называют общим делителем и для aa и для bb. Множество общих делителей чисел aa и bb конечно, так как ни один из этих делителей не может быть больше, чем aa. Значит, среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел aa и bb и для его обозначения используют записи: НОД (a;b)(a;b) или D(a;b)(a;b)

Пример
Наибольший общий делитель (НОД) чисел 1818 и 2424 — это 66.

Как найти наибольший общий делитель (НОД)

Существует несколько способов нахождения наибольшего общего делителя (НОД) двух или более целых чисел:

Алгоритм Евклида: НОД(a,b)=(a, b) = НОД (b,a(b, a mod b)b), где «mod» – это операция взятия остатка от деления большего числа на меньшее. Этот алгоритм можно продолжать до тех пор, пока одно из чисел не станет равно нулю. В этом случае НОД равен ненулевому числу.

Пример
НОД(18,24)=НОД(24,18)=НОД(18,6)=НОД(6,0)=6НОД(18, 24) = НОД(24, 18) = НОД(18, 6) = НОД(6, 0) = 6

Разложение на простые множители: Найти все простые множители каждого из чисел и их степени. НОД будет равен произведению всех общих простых множителей в минимальной степени.

Пример
НОД(60,84)=22⋅31=12(60, 84) = 2^{2} cdot 3^{1} = 12, так как общие простые множители −2- 2 и 33, их минимальные степени −2- 2 и 11 соответственно.

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

Наименьшее общее кратное (НОК)

Определение НОК

НОК двух или более целых чисел — это наименьшее число, которое делится на каждое из этих чисел без остатка.

Общими кратными чисел называются числа которые делятся на исходные без остатка. Например для чисел 2525 и 5050 общими кратными будут числа 50,100,150,20050,100,150,200 и т.д Наименьшее из общих кратных будет называться НОК и обозначается НОК(a;b)(a;b) или K(a;b).(a;b).

Пример
Наименьшее общее кратное чисел 88 и 1212 – это 2424. Т.е. НОК (8,12)=24(8, 12) = 24.

Как найти наименьшее общее кратное (НОК)

Чтобы найти НОК двух чисел, необходимо:

Разложить числа на простые множители;
Выписать множители, входящие в состав первого числа и добавить к ним множители, которые входят в состав второго и не ходят в состав первого;
Найти произведение чисел, найденных на шаге 2. Полученное число и будет искомым наименьшим общим кратным.

Пример
Рассмотрим два числа: 88 и 1212. Найдем их НОКНОК:

Разложим 88 и 1212 на простые множители: 8=23,12=22⋅38 = 2^3, 12 = 2^2 cdot 3.

Выпишем все простые множители: 23⋅32^3 cdot 3.

Для каждого простого множителя выберем наибольшую кратность: 232^3 и 33.

Умножим выбранные простые множители между собой: 23⋅3=242^3 cdot 3 = 24.

Таким образом, НОК чисел 88 и 1212 равен 2424.

Свойства НОД и НОК

Любое общее кратное чисел aa и bb делится на K(a;b)(a;b);

Если a⋮bavdots b , то К(a;b)=a(a;b)=a;

Если К(a;b)=k(a;b)=k и mm-натуральное число, то К(am;bm)=km(am;bm)=km. Если dd-общий делитель для aa и bb,то К(ad;bdfrac{a}{d};frac{b}{d})= kd frac{k}{d}

Если a⋮cavdots c и b⋮cbvdots c ,то abcfrac{ab}{c} – общее кратное чисел aa и bb;

Для любых натуральных чисел aa и bb выполняется равенство D(a;b)⋅К(a;b)=abD(a;b)cdot К(a;b)=ab;

Любой общий делитель чисел aa и bb является делителем числа D(a;b)D(a;b).

Источник

Советы

Об этой статье

Была ли эта статья полезной?

Связанные определения[править | править код]

Наименьшее общее кратное[править | править код]

Взаимно простые числа[править | править код]

Способы вычисления[править | править код]

Свойства[править | править код]

Вариации и обобщения[править | править код]

См. также[править | править код]

Литература[править | править код]

Примечания[править | править код]

About This Article

Did this article help you?

Что такое общие делители

Что такое наибольший общий делитель (НОД)

Основные свойства НОД и алгоритм Евклида

Онлайн калькулятор НОД и НОК двух чисел

Наибольший общий делитель (НОД)

Как найти наибольший общий делитель (НОД)

Наименьшее общее кратное (НОК)

Как найти наименьшее общее кратное (НОК)

Свойства НОД и НОК

Вам также может понравиться

Как найти лягушек в геншин импакт

Как составить график дежурства в эксель

Как найти человека в контакте без фамилии

Добавить комментарий Отменить ответ