Калькулятор НОД и НОК

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

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

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

Если числа имеют только один общий делитель – единицу, то такие числа называют взаимно простыми.

Наибольший общий делитель НОД обозначают: НОД(a, b), (a, b), gcd(a, b), hcf(a, b).

Свойства НОД

1. Наибольший общий делитель чисел a и b делится на любой общий делитель этих чисел.
   Данное свойство означает, что если найти все общие делители чисел a и b, то НОД(a, b) будет делится на любой из этих делителей.
   Например, возьмём два числа 15 и 30 и найдем все общие делители этих чисел: 1, 3, 5, 15. Наибольший из этих делителей – число 15. Тогда число 15 делится на 1, 3, 5, 15.
2. Если число a делится на b, то НОД(a, b) = b.
   Например, число 20 делится на число 10, тогда НОД(20, 10) = 10.
3. При помощи наибольшего общего делителя можно привести дроби к несократимому виду.
   Например, дробь 5/30 можно привести к несократимому виду, если найти НОД(30, 5). НОД(30, 5) = 5, следовательно число 5 – самое больше число из возможных делителей числа 30 и 5 на которое можно разделить эти числа, тогда 30:5 = 6, 5:5 = 1. Получаем дробь 5/30 = 1/6.

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

Чтобы найти наибольший общий делитель НОД двух, трех и более чисел, необходимо:

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

---

Приведем пример, найдем наибольший общий делитель двух чисел 24 и 58.

Способ №1

1. Разложим числа на простые множители. Для этого проверим, является ли каждое из чисел простым (если число простое, то его нельзя разложить на простые множители, и оно само является своим разложением).
   
   58 - составное число
   
   Разложим число 24 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
   
   24 : 2 = 12 - делится на простое число 2
   12 : 2 = 6 - делится на простое число 2
   6 : 2 = 3 - делится на простое число 2.
   Завершаем деление, так как 3 простое число
   
   Разложим число 58 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
   
   58 : 2 = 29 - делится на простое число 2.
   Завершаем деление, так как 29 простое число
2. Выделим синим цветом и выпишем общие множители.
   
   24 = 2 ⋅ 2 ⋅ 2 ⋅ 3
   58 = 2 ⋅ 29
   
   У чисел (24, 58) только один общий множитель - 2 и он и будет наибольшим общим делителем этих чисел
   
   Ответ: НОД (24, 58) = 2

Способ №2

1. Найдем все возможные делители чисел (24, 58). Для этого поочередно разделим число 24 на делители от 1 до 24, число 58 на делители от 1 до 58. Если число делится без остатка, то делитель запишем в список делителей.
   
   Для числа 24 выпишем все случаи, когда оно делится без остатка:
   24 : 1 = 24;
   24 : 2 = 12;
   24 : 3 = 8;
   24 : 4 = 6;
   24 : 6 = 4;
   24 : 8 = 3;
   24 : 12 = 2;
   24 : 24 = 1;
   
   Для числа 58 выпишем все случаи, когда оно делится без остатка:
   58 : 1 = 58;
   58 : 2 = 29;
   58 : 29 = 2;
   58 : 58 = 1;
2. Выпишем все общие делители чисел (24, 58) и выделим зеленым цветом самый большой, это и будет наибольший общий делитель НОД чисел (24, 58)
   
   Общие делители чисел (24, 58): 1, 2
   
   Ответ: НОД (24, 58) = 2

---

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

Наименьшее общее кратное НОК(a, b) – это наименьшее число, которое можно разделить на числа a и b без остатка.

Наименьшее общее кратное НОК обозначается: НОК(a, b), [a, b], LCM(a, b), lcm(a, b).

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

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

1. Разложить эти числа на простые множители.
2. Выписать множители одного из чисел и добавить к ним множители из разложения остальных чисел, которых нет в разложении.
3. Умножить получившиеся множители.

---

Приведем пример, найдем наименьшее общее кратное НОК для чисел 30 и 225.

Способ №1

1. Разложим числа на простые множители. Для этого проверим, является ли каждое из чисел простым (если число простое, то его нельзя разложить на простые множители, и оно само является своим разложением).
   225 - составное число
   30 - составное число
   
   Разложим число 225 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
   
   225 : 3 = 75 - делится на простое число 3
   75 : 3 = 25 - делится на простое число 3
   25 : 5 = 5 - делится на простое число 5.
   Завершаем деление, так как 5 простое число
   
   Разложим число 30 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
   
   30 : 2 = 15 - делится на простое число 2
   15 : 3 = 5 - делится на простое число 3.
   Завершаем деление, так как 5 простое число
2. Прежде всего запишем множители самого большого числа, а затем меньшего числа. Найдем недостающие множители, выделим синим цветом в разложении меньшего числа множители, которые не вошли в разложение большего числа.
   225 = 3 ∙ 3 ∙ 5 ∙ 5
   30 = 2 ∙ 3 ∙ 5
   
   3) Теперь, чтобы найти НОК нужно перемножить множители большего числа с недостающими множителями, которые выделены синим цветом
   
   НОК (225 ; 30) = 3 ∙ 3 ∙ 5 ∙ 5 ∙ 2 = 450

Способ №2

1. Найдем все возможные кратные чисел (225 ; 30). Для этого поочередно умножим число 225 на числа от 1 до 30, число 30 на числа от 1 до 225.
   
   Выделим все кратные числа 225 зеленым цветом: зеленым цветом:
   
   225 ∙ 1 = 225;   225 ∙ 2 = 450;   225 ∙ 3 = 675;   225 ∙ 4 = 900;
   225 ∙ 5 = 1125;   225 ∙ 6 = 1350;   225 ∙ 7 = 1575;   225 ∙ 8 = 1800;
   225 ∙ 9 = 2025;   225 ∙ 10 = 2250;   225 ∙ 11 = 2475;   225 ∙ 12 = 2700;
   225 ∙ 13 = 2925;   225 ∙ 14 = 3150;   225 ∙ 15 = 3375;   225 ∙ 16 = 3600;
   225 ∙ 17 = 3825;   225 ∙ 18 = 4050;   225 ∙ 19 = 4275;   225 ∙ 20 = 4500;
   225 ∙ 21 = 4725;   225 ∙ 22 = 4950;   225 ∙ 23 = 5175;   225 ∙ 24 = 5400;
   225 ∙ 25 = 5625;   225 ∙ 26 = 5850;   225 ∙ 27 = 6075;   225 ∙ 28 = 6300;
   225 ∙ 29 = 6525;   225 ∙ 30 = 6750;   
   
   Выделим все кратные числа 30 зеленым цветом:
   
   30 ∙ 1 = 30;   30 ∙ 2 = 60;   30 ∙ 3 = 90;   30 ∙ 4 = 120;
   30 ∙ 5 = 150;   30 ∙ 6 = 180;   30 ∙ 7 = 210;   30 ∙ 8 = 240;
   30 ∙ 9 = 270;   30 ∙ 10 = 300;   30 ∙ 11 = 330;   30 ∙ 12 = 360;
   30 ∙ 13 = 390;   30 ∙ 14 = 420;   30 ∙ 15 = 450;   30 ∙ 16 = 480;
   30 ∙ 17 = 510;   30 ∙ 18 = 540;   30 ∙ 19 = 570;   30 ∙ 20 = 600;
   30 ∙ 21 = 630;   30 ∙ 22 = 660;   30 ∙ 23 = 690;   30 ∙ 24 = 720;
   30 ∙ 25 = 750;   30 ∙ 26 = 780;   30 ∙ 27 = 810;   30 ∙ 28 = 840;
   30 ∙ 29 = 870;   30 ∙ 30 = 900;   30 ∙ 31 = 930;   30 ∙ 32 = 960;
   30 ∙ 33 = 990;   30 ∙ 34 = 1020;   30 ∙ 35 = 1050;   30 ∙ 36 = 1080;
   30 ∙ 37 = 1110;   30 ∙ 38 = 1140;   30 ∙ 39 = 1170;   30 ∙ 40 = 1200;
   30 ∙ 41 = 1230;   30 ∙ 42 = 1260;   30 ∙ 43 = 1290;   30 ∙ 44 = 1320;
   30 ∙ 45 = 1350;   30 ∙ 46 = 1380;   30 ∙ 47 = 1410;   30 ∙ 48 = 1440;
   30 ∙ 49 = 1470;   30 ∙ 50 = 1500;   30 ∙ 51 = 1530;   30 ∙ 52 = 1560;
   30 ∙ 53 = 1590;   30 ∙ 54 = 1620;   30 ∙ 55 = 1650;   30 ∙ 56 = 1680;
   30 ∙ 57 = 1710;   30 ∙ 58 = 1740;   30 ∙ 59 = 1770;   30 ∙ 60 = 1800;
   30 ∙ 61 = 1830;   30 ∙ 62 = 1860;   30 ∙ 63 = 1890;   30 ∙ 64 = 1920;
   30 ∙ 65 = 1950;   30 ∙ 66 = 1980;   30 ∙ 67 = 2010;   30 ∙ 68 = 2040;
   30 ∙ 69 = 2070;   30 ∙ 70 = 2100;   30 ∙ 71 = 2130;   30 ∙ 72 = 2160;
   30 ∙ 73 = 2190;   30 ∙ 74 = 2220;   30 ∙ 75 = 2250;   30 ∙ 76 = 2280;
   30 ∙ 77 = 2310;   30 ∙ 78 = 2340;   30 ∙ 79 = 2370;   30 ∙ 80 = 2400;
   30 ∙ 81 = 2430;   30 ∙ 82 = 2460;   30 ∙ 83 = 2490;   30 ∙ 84 = 2520;
   30 ∙ 85 = 2550;   30 ∙ 86 = 2580;   30 ∙ 87 = 2610;   30 ∙ 88 = 2640;
   30 ∙ 89 = 2670;   30 ∙ 90 = 2700;   30 ∙ 91 = 2730;   30 ∙ 92 = 2760;
   30 ∙ 93 = 2790;   30 ∙ 94 = 2820;   30 ∙ 95 = 2850;   30 ∙ 96 = 2880;
   30 ∙ 97 = 2910;   30 ∙ 98 = 2940;   30 ∙ 99 = 2970;   30 ∙ 100 = 3000;
   30 ∙ 101 = 3030;   30 ∙ 102 = 3060;   30 ∙ 103 = 3090;   30 ∙ 104 = 3120;
   30 ∙ 105 = 3150;   30 ∙ 106 = 3180;   30 ∙ 107 = 3210;   30 ∙ 108 = 3240;
   30 ∙ 109 = 3270;   30 ∙ 110 = 3300;   30 ∙ 111 = 3330;   30 ∙ 112 = 3360;
   30 ∙ 113 = 3390;   30 ∙ 114 = 3420;   30 ∙ 115 = 3450;   30 ∙ 116 = 3480;
   30 ∙ 117 = 3510;   30 ∙ 118 = 3540;   30 ∙ 119 = 3570;   30 ∙ 120 = 3600;
   30 ∙ 121 = 3630;   30 ∙ 122 = 3660;   30 ∙ 123 = 3690;   30 ∙ 124 = 3720;
   30 ∙ 125 = 3750;   30 ∙ 126 = 3780;   30 ∙ 127 = 3810;   30 ∙ 128 = 3840;
   30 ∙ 129 = 3870;   30 ∙ 130 = 3900;   30 ∙ 131 = 3930;   30 ∙ 132 = 3960;
   30 ∙ 133 = 3990;   30 ∙ 134 = 4020;   30 ∙ 135 = 4050;   30 ∙ 136 = 4080;
   30 ∙ 137 = 4110;   30 ∙ 138 = 4140;   30 ∙ 139 = 4170;   30 ∙ 140 = 4200;
   30 ∙ 141 = 4230;   30 ∙ 142 = 4260;   30 ∙ 143 = 4290;   30 ∙ 144 = 4320;
   30 ∙ 145 = 4350;   30 ∙ 146 = 4380;   30 ∙ 147 = 4410;   30 ∙ 148 = 4440;
   30 ∙ 149 = 4470;   30 ∙ 150 = 4500;   30 ∙ 151 = 4530;   30 ∙ 152 = 4560;
   30 ∙ 153 = 4590;   30 ∙ 154 = 4620;   30 ∙ 155 = 4650;   30 ∙ 156 = 4680;
   30 ∙ 157 = 4710;   30 ∙ 158 = 4740;   30 ∙ 159 = 4770;   30 ∙ 160 = 4800;
   30 ∙ 161 = 4830;   30 ∙ 162 = 4860;   30 ∙ 163 = 4890;   30 ∙ 164 = 4920;
   30 ∙ 165 = 4950;   30 ∙ 166 = 4980;   30 ∙ 167 = 5010;   30 ∙ 168 = 5040;
   30 ∙ 169 = 5070;   30 ∙ 170 = 5100;   30 ∙ 171 = 5130;   30 ∙ 172 = 5160;
   30 ∙ 173 = 5190;   30 ∙ 174 = 5220;   30 ∙ 175 = 5250;   30 ∙ 176 = 5280;
   30 ∙ 177 = 5310;   30 ∙ 178 = 5340;   30 ∙ 179 = 5370;   30 ∙ 180 = 5400;
   30 ∙ 181 = 5430;   30 ∙ 182 = 5460;   30 ∙ 183 = 5490;   30 ∙ 184 = 5520;
   30 ∙ 185 = 5550;   30 ∙ 186 = 5580;   30 ∙ 187 = 5610;   30 ∙ 188 = 5640;
   30 ∙ 189 = 5670;   30 ∙ 190 = 5700;   30 ∙ 191 = 5730;   30 ∙ 192 = 5760;
   30 ∙ 193 = 5790;   30 ∙ 194 = 5820;   30 ∙ 195 = 5850;   30 ∙ 196 = 5880;
   30 ∙ 197 = 5910;   30 ∙ 198 = 5940;   30 ∙ 199 = 5970;   30 ∙ 200 = 6000;
   30 ∙ 201 = 6030;   30 ∙ 202 = 6060;   30 ∙ 203 = 6090;   30 ∙ 204 = 6120;
   30 ∙ 205 = 6150;   30 ∙ 206 = 6180;   30 ∙ 207 = 6210;   30 ∙ 208 = 6240;
   30 ∙ 209 = 6270;   30 ∙ 210 = 6300;   30 ∙ 211 = 6330;   30 ∙ 212 = 6360;
   30 ∙ 213 = 6390;   30 ∙ 214 = 6420;   30 ∙ 215 = 6450;   30 ∙ 216 = 6480;
   30 ∙ 217 = 6510;   30 ∙ 218 = 6540;   30 ∙ 219 = 6570;   30 ∙ 220 = 6600;
   30 ∙ 221 = 6630;   30 ∙ 222 = 6660;   30 ∙ 223 = 6690;   30 ∙ 224 = 6720;
   30 ∙ 225 = 6750;
2. Выпишем все общие кратные чисел (225 ; 30) и выделим зеленым цветом самое маленькое, это и будет наименьшим общим кратным чисел (225 ; 30).
   
   Общие кратные чисел (225 ; 30): 450, 900, 1350, 1800, 2250, 2700, 3150, 3600, 4050, 4500, 4950, 5400, 5850, 6300, 6750
   
   Ответ: НОК (225 ; 30) = 450