Задача
NT-B1-M02-P016 НОД двух чисел Мерсенна
#16
★★★☆☆ Уровень 3 из 5
Найдите \(\gcd(2^{18}-1,2^{30}-1)\).
Используйте \(\gcd(18,30)=6\).
Для чисел вида \(a^m-1\) верно \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). Поэтому искомый НОД равен \(2^6-1=63\).
Можно дать после доказательства формулы в примерах или перед общей задачей.