НОД будет 36. Внизу прикрепил скриншот с алгоритмом Евклида. Если нужно, могу написать код программы или сразу готовую программу могу сбросить)