Нахождение наибольшего общего делителя: основные термины


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


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


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


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


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


Большинство натуральных чисел могут делиться не только на единицу, самих себя, но и на другие числа. Так, например, число 15 можно поделить еще на 3 и 5. Все их называют делителями числа 15.


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


У числа 30 можно выделить такие делители, как 1, 3, 5, 6, 15, 30.


Можно заметить, что 15 и 30 имеют одинаковые делители 1, 3, 5, 15. Наибольший общий делитель этих двух чисел - 15.


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


Для решения задач используется такая сокращенная надпись:


НОД (А; Б).


Например, НОД (15; 30) = 30.


Чтобы записать все делители натурального числа, применяется запись:


Д (15) = {1, 3, 5, 15}


Д (9) = {1, 9}


НОД (9; 15) = 1


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


Как найти наибольший общий делитель чисел


Чтобы найти НОД нескольких чисел, нужно:


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


- выделить все одинаковые множители у данных чисел;


- перемножить их между собой.


Например, чтобы вычислить наибольший общий делитель чисел 30 и 56, нужно записать следующее:


30 = 2 * 3 * 5


70 = 2 * 5 * 7


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


Так, в правом столбце окажутся все нужные для решения множители.


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


70|2   30|2


35|5   15|5


7         3


НОД (30; 56) = 2 * 5 = 10


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