Преди да продължим към следващата задача, е необходимо да се запознаем с определението за най-голям общ делител (НОД).
Определение за НОД: най-голям общ делител на две естествени числа a и b е най-голямото число, което дели едновременно и a, и b без остатък. Например:
| a | b | НОД |
|---|---|---|
| 24 | 16 | 8 |
| 67 | 18 | 1 |
| 12 | 24 | 12 |
| 15 | 9 | 3 |
| 10 | 10 | 10 |
| 100 | 88 | 4 |