#1 Продвинутые задачи на НОД

Пусть \(d=\gcd(n+4,n^2+2n+10)\). По модулю \(n+4\) имеем \(n\equiv-4\), поэтому \(n^2+2n+10\equiv16-8+10=18\). Следовательно, \(d=\gcd(n+4,18)\), значит возможны только делители \(18\): \(1,2,3,6,9,18\). Каждый из них достигается: для делителя \(r\mid18\) возьмём \(n+4=r+18\). Тогда \( \gcd(n+4,18)=r \).

Если \(d\mid n+1\), то \(n\equiv-1\pmod d\). Тогда \(n^2+n+1\equiv1-1+1=1\pmod d\). Общий делитель должен делить \(1\), значит он равен \(1\).

Любой общий делитель \(d\) чисел \(3n+2\) и \(5n+3\) делит комбинацию \(5(3n+2)-3(5n+3)=1\). Поэтому \(d=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\).

Заметим, что \((2n+1)^2=4n^2+4n+1\). Если \(d\) делит \(2n+1\) и \(4n^2+4n+3\), то \(d\) делит разность \(2\). Но \(2n+1\) нечётно, значит его общий делитель со вторым числом не может быть равен \(2\). Поэтому \(d=1\).

Имеем \(n^3-1=(n-1)(n^2+n+1)\) и \(n^2-1=(n-1)(n+1)\). Поэтому НОД равен \((n-1)\gcd(n^2+n+1,n+1)\). Последний НОД равен \(1\), так как при \(n\equiv-1\) выражение \(n^2+n+1\) даёт остаток \(1\). Следовательно, весь НОД равен \(n-1\).

Пусть \(d\) - общий делитель. Так как \(d\mid2n+1\), имеем \((2n+1)^2\equiv0\pmod d\). Но \(4(n^2+n+1)=(2n+1)^2+3\), значит \(d\mid3\). Поэтому НОД больше \(1\) только если \(3\mid2n+1\), то есть \(n\equiv1\pmod3\). При этом условии \(3\) действительно делит оба числа. Ответ: \(n\equiv1\pmod3\).

Пусть нечётный простой \(p\) делит оба числа. Из \(a+b\equiv0\pmod p\) следует \(b\equiv-a\). Тогда \(a^2+b^2\equiv2a^2\pmod p\). Так как \(p\ne2\), получаем \(p\mid a\), а значит \(p\mid b\), что противоречит \( \gcd(a,b)=1 \). Значит, возможен только делитель \(2\). Он появляется тогда и только тогда, когда \(a+b\) и \(a^2+b^2\) чётны, то есть когда \(a,b\) оба нечётны. В этом случае \(a^2+b^2\equiv2\pmod4\), поэтому НОД ровно \(2\).

Пусть \(m=n+2\). Тогда \(n^2+3n+3=m^2-m+1\), а \(n^2+5n+7=m^2+m+1\). Их общий делитель делит разность \(2m\). Но \(m^2-m+1\) взаимно просто с \(m\), потому что по модулю \(m\) оно даёт остаток \(1\). Следовательно, общий делитель может делить только \(2\). При этом \(m^2-m+1\) всегда нечётно, поэтому общий делитель не равен \(2\). Значит, НОД равен \(1\).

Так как \( \gcd(m,n)=1 \), общий факт для степеней даёт \( \gcd(a^m-1,a^n-1)=a^1-1=a-1 \). Если доказывать напрямую, общий делитель сохраняется при замене пары показателей \((m,n)\) на \((m-n,n)\), пока алгоритм Евклида не приведёт к показателю \(1\).

Общий делитель делит разность \((3^n+2)-(3^n-1)=3\). Значит, возможен только общий простой делитель \(3\). Но \(3^n-1\equiv -1\pmod3\), поэтому \(3\) не делит первое число. Следовательно, общий делитель равен \(1\).

Пусть \(d\) - общий делитель. Тогда \(d\mid n(n^2+2)-(n^3+3)=2n-3\). Значит \(2n\equiv3\pmod d\). Умножим \(n^2+2\) на \(4\): получаем \(4n^2+8\equiv9+8=17\pmod d\). Поэтому \(d\mid17\). Общий делитель больше \(1\) возможен только при \(17\mid d\), то есть при \(2n\equiv3\pmod{17}\). Так как \(2^{-1}\equiv9\pmod{17}\), получаем \(n\equiv27\equiv10\pmod{17}\). Проверка подстановкой показывает, что при таких \(n\) оба выражения делятся на \(17\).

Пусть \(d\) делит оба числа. Тогда \(d\mid (n+1)!+1-(n+1)(n!+1)=-n\). Значит \(d\mid n\), а тогда \(d\mid n!\). Но \(d\mid n!+1\), поэтому \(d\mid1\). Следовательно, \(d=1\).

Пусть \(d\) - общий делитель. Тогда \(d\mid p^3+1-p(p^2+1)=1-p\). Значит, \(d\mid p-1\). По модулю \(p-1\) имеем \(p\equiv1\), поэтому \(p^2+1\equiv2\). Следовательно, общий делитель может делить только \(2\). Если \(p=2\), то получаем \(\gcd(5,9)=1\). Если \(p\) нечётно, то \(p^2+1\) и \(p^3+1\) чётны, значит НОД равен \(2\). Ответ: все нечётные простые \(p\).

Пусть \(g=\gcd(m,n)\). Число \(a^g-b^g\) делит оба выражения. Обратно, пусть \(d\) делит оба. Так как \( \gcd(b,d)=1 \), существует обратный элемент \(b^{-1}\pmod d\). Из \(a^m\equiv b^m\) и \(a^n\equiv b^n\) получаем \((ab^{-1})^m\equiv1\) и \((ab^{-1})^n\equiv1\pmod d\). По алгоритму Евклида для показателей \((ab^{-1})^g\equiv1\pmod d\). Значит, \(a^g\equiv b^g\pmod d\), то есть \(d\mid a^g-b^g\).

Так как \(4^m-1=2^{2m}-1\), применяем формулу для степеней: \( \gcd(2^{2m}-1,2^n-1)=2^{\gcd(2m,n)}-1 \). Это и есть ответ.

Пусть \(d\) - НОД. По модулю \(x+y\) имеем \(x\equiv-y\), поэтому \(x^{2k}+y^{2k}\equiv2y^{2k}\pmod d\). Так как \( \gcd(y,x+y)=1 \), общий делитель \(d\) делит \(2\). Следовательно, возможны только \(1\) и \(2\). Если \(x,y\) оба нечётны, то \(x+y\) чётно и \(x^{2k}+y^{2k}\) чётно, значит НОД равен \(2\). Если один из них чётен, другой нечётен, то \(x+y\) нечётно, значит НОД равен \(1\).

Пусть нечётный простой \(p\) делит оба выражения. Так как \(p\nmid b\), положим \(t\equiv ab^{-1}\pmod p\). Тогда из \(a^2+b^2\equiv0\) получаем \(t^2\equiv-1\), а из \(a^3+b^3\equiv0\) получаем \(t^3\equiv-1\). Деление второго сравнения на первое даёт \(t\equiv1\), но тогда \(1\equiv-1\pmod p\), противоречие. Значит, нечётных простых общих делителей нет. Если один из \(a,b\) чётен, оба выражения нечётны, и НОД равен \(1\). Если оба нечётны, оба выражения чётны, а \(a^2+b^2\equiv2\pmod4\), поэтому НОД равен \(2\).

Имеем \(u_{n+1}=u_n(u_n-1)+1\), поэтому \(u_{n+1}\equiv1\pmod{u_n}\). Если \(u_k\equiv1\pmod{u_n}\), то \(u_{k+1}=u_k^2-u_k+1\equiv1-1+1=1\pmod{u_n}\). Следовательно, для любого \(m>n\) выполнено \(u_m\equiv1\pmod{u_n}\). Поэтому общий делитель \(u_m\) и \(u_n\) делит \(1\), и НОД равен \(1\).

Обозначим \(Q=a^2+ab+b^2\). Если \(3\mid n\), то \(a^3-b^3=(a-b)Q\), значит \(a^3\equiv b^3\pmod Q\), и потому \(Q\mid a^n-b^n\). В этом случае НОД равен \(Q\). Пусть теперь \(3\nmid n\). Рассмотрим простой \(p\ne3\), делящий \(Q\) и \(a^n-b^n\). Так как \(p\nmid b\), положим \(t\equiv ab^{-1}\pmod p\). Из \(Q\equiv0\) следует \(t^2+t+1\equiv0\), то есть \(t^3\equiv1\) и \(t\not\equiv1\). Значит, порядок \(t\) равен \(3\). Но из \(a^n\equiv b^n\) следует \(t^n\equiv1\), поэтому \(3\mid n\), противоречие. Следовательно, при \(3\nmid n\) возможен только общий простой делитель \(3\). Число \(3\) делит \(Q\) тогда и только тогда, когда \(a\equiv b\pmod3\); из взаимной простоты тогда \(a,b\) не делятся на \(3\), и \(Q\) делится на \(3\), но не на \(9\). При том же условии \(a^n-b^n\) делится на \(3\). Ответ: если \(3\mid n\), НОД равен \(Q\); если \(3\nmid n\) и \(a\equiv b\pmod3\), НОД равен \(3\); в остальных случаях НОД равен \(1\).