Как быстро найти общий делитель двух чисел - AvtoShod.ru

Как найти НОД

Нахождение путём разложения на множители
Алгоритм Евклида

Рассмотрим два способа нахождения наибольшего общего делителя.

Нахождение путём разложения на множители

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

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

Пример 1. Найти НОД (84, 90).

Решение: Раскладываем числа 84 и 90 на простые множители:

Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой:

2 · 3 = 6.

Таким образом, НОД (84, 90) = 6.

Пример 2. Найти НОД (15, 28).

Решение: Раскладываем 15 и 28 на простые множители:

Числа 15 и 28 являются взаимно простыми, так как их наибольший общий делитель — единица.

НОД (15, 28) = 1.

Алгоритм Евклида

Второй способ (иначе его называют способом Евклида) заключается в нахождении НОД путём последовательного деления.

Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.

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

Пример 1. Возьмём два числа 27 и 9. Так как 27 делится на 9 и 9 делится на 9, значит, 9 является общим делителем чисел 27 и 9. Этот делитель является в тоже время и наибольшим, потому что 9 не может делиться ни на какое число, большее 9. Следовательно:

НОД (27, 9) = 9.

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

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

Пример 2. Найдём наибольший общий делитель чисел 140 и 96:

1) 140 : 96 = 1 (остаток 44)

2) 96 : 44 = 2 (остаток

3) 44 : 8 = 5 (остаток 4)

4) 8 : 4 = 2

Последний делитель равен 4 — это значит:

НОД (140, 96) = 4.

Последовательное деление так же можно записывать столбиком:

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

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

Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа — 48:

48 : 4 = 12

48 делится на 4 без остатка. Таким образом:

НОД (140, 96, 48) = 4.

Источник

Загрузить 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).

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

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

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

Источник

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!

References

About This Article

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

Did this article help you?

Get all the best how-tos!

You’re all set!

Источник

Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 12 и 8, наибольшим общим делителем будет 4.

Как найти НОД?

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

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

Примеры нахождения наибольшего общего делителя

Рассмотрим приведенный алгоритм на конкретных примерах:

Пример 1: найти НОД 12 и 8

1. Раскладываем 12 и 8 на простые множители:

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 2 и 2

3. Перемножаем эти множители и получаем: 2 · 2 = 4

Ответ: НОД (8; 12) = 2 · 2 = 4.

Пример 2: найти НОД 75 и 150

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

1. Раскладываем 75 и 150 на простые множители:

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 3, 5 и 5

3. Перемножаем эти множители и получаем: 3 · 5 · 5 = 75

Ответ: НОД (75; 150) = 3 · 5 · 5 = 75.

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

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

Пример 3: найти НОД 9 и 5

1. Раскладываем 5 и 9 на простые множители:

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

Источник

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

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

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

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

Если натуральное число 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).

Источник

Как найти НОД

Нахождение путём разложения на множители

Алгоритм Евклида

Советы

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

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

References

About This Article

Did this article help you?

Как найти НОД?

Примеры нахождения наибольшего общего делителя

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

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

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

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

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

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

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

Не пропустите также: