НОД, НОК и алгоритм Евклида

\(\gcd(252,198)=\gcd(198,54)=\gcd(54,36)=\gcd(36,18)=18\). Ответ: \(18\).

\(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\). Поэтому \(\gcd=2\cdot3\cdot7=42\), \(\operatorname{lcm}=2^2\cdot3^2\cdot7=252\).

\(96=2^5\cdot3\), \(180=2^2\cdot3^2\cdot5\). Тогда \(\gcd=2^2\cdot3=12\), \(\operatorname{lcm}=2^5\cdot3^2\cdot5=1440\). Получаем \(96\cdot180=17280\) и \(12\cdot1440=17280\).

Если \(d\mid n\) и \(d\mid n+1\), то \(d\mid(n+1)-n=1\). Значит, \(d=1\). Поэтому \(\gcd(n,n+1)=1\).

Любой общий делитель \(d\) чисел \(n\) и \(2n+1\) делит \(2n\), а значит, делит \((2n+1)-2n=1\). Поэтому \(d=1\), и НОД равен \(1\).

\(\gcd(48,180)=12\), \(\operatorname{lcm}(48,180)=720\). Так как оба числа умножены на \(n\), получаем \(\gcd(48n,180n)=12n\) и \(\operatorname{lcm}(48n,180n)=720n\).

Имеем \(90n=18\cdot630\), откуда \(n=126\). Проверка: \(\gcd(126,90)=18\), \(\operatorname{lcm}(126,90)=630\), значит, ответ верен.

Пусть \(d=\gcd(n,n+2)\). Тогда \(d\mid(n+2)-n=2\), значит, \(d\in\{1,2\}\). Если \(n\) четно, то оба числа четны и НОД равен \(2\). Если \(n\) нечетно, оба числа нечетны, общего делителя \(2\) нет, значит, НОД равен \(1\).

Если \(d\mid n\) и \(d\mid n^2+n+1\), то \(d\mid n(n+1)\). Тогда \(d\) делит разность \((n^2+n+1)-n(n+1)=1\). Значит, \(d=1\).

Пусть \(d\mid a+b\) и \(d\mid a-b\). Тогда \(d\mid (a+b)+(a-b)=2a\) и \(d\mid(a+b)-(a-b)=2b\). Так как \(\gcd(a,b)=1\), общий делитель не может содержать нечетный простой множитель. Поэтому \(d\mid2\).

По модулю \(n+2\) имеем \(n\equiv -2\). Тогда \(n^2+3n+5\equiv4-6+5=3\). Следовательно, \(\gcd(n+2,n^2+3n+5)=\gcd(n+2,3)\). Он больше \(1\) тогда и только тогда, когда \(3\mid n+2\), то есть \(n\equiv1\pmod3\).

\(36n=12\cdot180\), значит, \(n=60\). Проверяем: \(\gcd(60,36)=12\), \(\operatorname{lcm}(60,36)=180\). Ответ: \(60\).

Предположим, что простой \(p\) делит и \(a+b\), и \(ab\). Из \(p\mid ab\) следует \(p\mid a\) или \(p\mid b\). Если \(p\mid a\), то из \(p\mid a+b\) получаем \(p\mid b\), противоречие с \(\gcd(a,b)=1\). Случай \(p\mid b\) аналогичен. Значит, общих простых делителей нет, и НОД равен \(1\).

По модулю \(n+3\) имеем \(n\equiv -3\), поэтому \(n^2+1\equiv10\). Значит, \(\gcd(n^2+1,n+3)=\gcd(10,n+3)\). Этот НОД больше \(1\), если \(n+3\) делится на \(2\) или \(5\). То есть \(n\) нечетно или \(n\equiv2\pmod5\).

По модулю \(n-1\) имеем \(n\equiv1\). Тогда \(n^2+n+1\equiv1+1+1=3\). Следовательно, НОД равен \(\gcd(n-1,3)\), значит, он делит \(3\). Он равен \(3\) тогда и только тогда, когда \(3\mid n-1\), то есть \(n\equiv1\pmod3\).

Для чисел вида \(a^m-1\) верно \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). Поэтому искомый НОД равен \(2^6-1=63\).

Если простой \(p\) делит \(a^m\), то \(p\mid a\). Если бы тот же \(p\) делил \(b^n\), то \(p\mid b\), что противоречит \(\gcd(a,b)=1\). Значит, общих простых делителей у \(a^m\) и \(b^n\) нет, и их НОД равен \(1\).

Пусть \(d=\gcd(a^2+b^2,a+b)\). Тогда \(a\equiv -b\pmod d\), поэтому \(a^2+b^2\equiv2b^2\pmod d\). Значит, \(d\mid2b^2\). Но \(\gcd(a+b,b)=\gcd(a,b)=1\), следовательно, \(\gcd(d,b)=1\). Поэтому из \(d\mid2b^2\) получаем \(d\mid2\).

По модулю \(n+6\) имеем \(n\equiv -6\), поэтому \(n^2+4\equiv36+4=40\). Значит, НОД равен \(\gcd(n+6,40)\). Он больше \(1\), если \(n+6\) делится на \(2\) или \(5\). Поэтому \(n\) четно или \(n\equiv4\pmod5\).

Пусть \(d=\gcd(n^2+n+1,n^2+2n+3)\). Тогда \(d\mid(n^2+2n+3)-(n^2+n+1)=n+2\). По модулю \(d\) имеем \(n\equiv-2\), поэтому из \(d\mid n^2+n+1\) получаем \(d\mid4-2+1=3\). Значит, \(d\) равен \(1\) или \(3\). Оба выражения делятся на \(3\) тогда и только тогда, когда \(n\equiv1\pmod3\). Следовательно, НОД равен \(3\) при \(n\equiv1\pmod3\), и \(1\) иначе.

Пусть \(m\ge n\) и \(m=qn+r\). Так как \(a^n\equiv1\pmod{a^n-1}\), имеем \(a^m=a^{qn+r}\equiv a^r\pmod{a^n-1}\). Поэтому \(\gcd(a^m-1,a^n-1)=\gcd(a^r-1,a^n-1)\). Это ровно шаг алгоритма Евклида для пары показателей \((m,n)\). Повторяя, приходим к \(d=\gcd(m,n)\). Тогда НОД равен \(a^d-1\).

Пусть \(a=12x\), \(b=12y\), \(\gcd(x,y)=1\). Тогда \(\operatorname{lcm}(a,b)=12xy=720\), значит, \(xy=60\). Так как \(x\) и \(y\) взаимно просты, каждая простая степень из \(60=2^2\cdot3\cdot5\) целиком идет либо в \(x\), либо в \(y\). Неупорядоченные пары \((x,y)\): \((1,60)\), \((3,20)\), \((4,15)\), \((5,12)\). Поэтому пары \((a,b)\): \((12,720)\), \((36,240)\), \((48,180)\), \((60,144)\).

В полном кубе все показатели простых кратны \(3\). Чтобы куб делился на \(18=2\cdot3^2\), показатель двойки должен быть хотя бы \(3\), и показатель тройки тоже хотя бы \(3\). Значит, каждый такой куб делится на \(2^3\cdot3^3=216\). Это значение достижимо: можно взять все три куба равными \(216=6^3\). Поэтому наименьший возможный НОД равен \(216\).

Пусть \(d=\gcd(a,b)\), \(a=dx\), \(b=dy\), где \(\gcd(x,y)=1\). Тогда \(\operatorname{lcm}(a,b)=dxy\), а \(a+b=d(x+y)\). Так как \(\gcd(x+y,xy)=1\), получаем \(\gcd(a+b,\operatorname{lcm}(a,b))=d\). Значит, \(d=\gcd(154,840)=14\).

Тогда \(a=14x\), \(b=14y\), \(x+y=11\), а \(\operatorname{lcm}(a,b)=14xy=840\), то есть \(xy=60\). Числа \(x,y\) - корни уравнения \(t^2-11t+60=0\), откуда \(\{x,y\}=\{5,6\}\). Следовательно, \(\{a,b\}=\{70,84\}\).