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

Математика

Наибольший общий делитель (НОД) двух натуральных чисел — самое большое число, на которое оба числа делятся без остатка. Например, у чисел 1818 и 3030 общие делители 11, 22, 33 и 66. Самый большой из них — 66, поэтому НОД(18,30)=6\text{НОД}(18,30)=6.

Как найти НОД разложением на простые множители

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

  1. Разложим оба числа. Получим 84=22⋅3⋅784=2^2\cdot3\cdot7 и 126=2⋅32⋅7126=2\cdot3^2\cdot7.
  2. Возьмём простые множители, которые есть в обоих разложениях. В первом числе две двойки, во втором одна, поэтому берём одну двойку. Для троек тоже берём одну, для семёрок — одну.
  3. Перемножим выбранные множители. НОД(84,126)=2⋅3⋅7=42\text{НОД}(84,126)=2\cdot3\cdot7=42.

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

Где пригодится НОД

Чтобы сократить дробь 84126\dfrac{84}{126} за один шаг, разделим числитель и знаменатель на их НОД, то есть на 4242. Получим несократимую дробь 23\dfrac{2}{3}. Если бы мы разделили только на 77, получили бы 1218\dfrac{12}{18}, которую можно сократить ещё раз.

НОД в особых случаях

  • Если одно число делится на другое, НОД равен меньшему. Например, НОД(14,70)=14\text{НОД}(14,70)=14.
  • Если общий делитель только один и это единица, числа называют взаимно простыми. Например, 88 и 1515 — взаимно простые, хотя оба числа составные. У любых двух различных простых чисел НОД тоже равен единице.
  • Для трёх чисел подходят только множители, которые есть во всех трёх разложениях. Например, 72=23⋅3272=2^3\cdot3^2, 90=2⋅32⋅590=2\cdot3^2\cdot5 и 150=2⋅3⋅52150=2\cdot3\cdot5^2. Общие множители здесь 22 и 33, поэтому НОД(72,90,150)=6\text{НОД}(72,90,150)=6.
Top.Mail.Ru