#1 Advanced GCD Problems

Let \(d=\gcd(n+4,n^2+2n+10)\). Modulo \(n+4\), \(n\equiv-4\), so \(n^2+2n+10\equiv16-8+10=18\). Hence \(d=\gcd(n+4,18)\), so only the divisors of \(18\) are possible: \(1,2,3,6,9,18\). Each occurs: for a divisor \(r\mid18\), take \(n+4=r+18\). Then \( \gcd(n+4,18)=r \).

If \(d\mid n+1\), then \(n\equiv-1\pmod d\). Therefore \(n^2+n+1\equiv1-1+1=1\pmod d\). A common divisor must divide \(1\), so it is \(1\).

Any common divisor \(d\) of \(3n+2\) and \(5n+3\) divides \(5(3n+2)-3(5n+3)=1\). Hence \(d=1\), so the numbers are coprime.

Modulo \(n+3\), \(n\equiv-3\), hence \(n^2+1\equiv10\). Thus \( \gcd(n^2+1,n+3)=\gcd(10,n+3) \). This gcd is greater than \(1\) exactly when \(n+3\) is divisible by \(2\) or by \(5\). Therefore \(n\) is odd or \(n\equiv2\pmod5\).

We have \((2n+1)^2=4n^2+4n+1\). If \(d\) divides \(2n+1\) and \(4n^2+4n+3\), then \(d\) divides the difference \(2\). But \(2n+1\) is odd, so the common divisor cannot be \(2\). Hence \(d=1\).

We have \(n^3-1=(n-1)(n^2+n+1)\) and \(n^2-1=(n-1)(n+1)\). Hence the gcd equals \((n-1)\gcd(n^2+n+1,n+1)\). The last gcd is \(1\), because for \(n\equiv-1\), the expression \(n^2+n+1\) has remainder \(1\). Therefore the gcd is \(n-1\).

Let \(d\) be a common divisor. Since \(d\mid2n+1\), we have \((2n+1)^2\equiv0\pmod d\). But \(4(n^2+n+1)=(2n+1)^2+3\), so \(d\mid3\). Thus the gcd is greater than \(1\) only when \(3\mid2n+1\), that is, \(n\equiv1\pmod3\). In this case \(3\) really divides both numbers. Answer: \(n\equiv1\pmod3\).

Let an odd prime \(p\) divide both numbers. From \(a+b\equiv0\pmod p\), we get \(b\equiv-a\). Then \(a^2+b^2\equiv2a^2\pmod p\). Since \(p\ne2\), this gives \(p\mid a\), hence \(p\mid b\), contradicting \( \gcd(a,b)=1 \). Thus only the divisor \(2\) is possible. It occurs exactly when both \(a+b\) and \(a^2+b^2\) are even, that is, when \(a,b\) are both odd. Then \(a^2+b^2\equiv2\pmod4\), so the gcd is exactly \(2\).

Let \(m=n+2\). Then \(n^2+3n+3=m^2-m+1\), and \(n^2+5n+7=m^2+m+1\). A common divisor divides the difference \(2m\). But \(m^2-m+1\) is coprime to \(m\), because modulo \(m\) it has remainder \(1\). Hence the common divisor can only divide \(2\). Since \(m^2-m+1\) is always odd, the common divisor is not \(2\). Therefore the gcd is \(1\).

Since \( \gcd(m,n)=1 \), the general power identity gives \( \gcd(a^m-1,a^n-1)=a^1-1=a-1 \). Directly, the common divisor is preserved when the exponent pair \((m,n)\) is replaced by \((m-n,n)\), until the Euclidean algorithm reaches exponent \(1\).

A common divisor divides the difference \((3^n+2)-(3^n-1)=3\). Thus the only possible common prime divisor is \(3\). But \(3^n-1\equiv -1\pmod3\), so \(3\) does not divide the first number. Hence the gcd is \(1\).

Let \(d\) be a common divisor. Then \(d\mid n(n^2+2)-(n^3+3)=2n-3\). Hence \(2n\equiv3\pmod d\). Multiplying \(n^2+2\) by \(4\), we get \(4n^2+8\equiv9+8=17\pmod d\). Thus \(d\mid17\). A nontrivial common divisor can occur only when \(17\mid d\), that is, when \(2n\equiv3\pmod{17}\). Since \(2^{-1}\equiv9\pmod{17}\), we get \(n\equiv27\equiv10\pmod{17}\). Direct checking shows that for such \(n\), both expressions are divisible by \(17\).

Let \(d\) divide both numbers. Then \(d\mid (n+1)!+1-(n+1)(n!+1)=-n\). Hence \(d\mid n\), so \(d\mid n!\). But \(d\mid n!+1\), therefore \(d\mid1\). Thus \(d=1\).

Let \(d\) be a common divisor. Then \(d\mid p^3+1-p(p^2+1)=1-p\). Thus \(d\mid p-1\). Modulo \(p-1\), \(p\equiv1\), so \(p^2+1\equiv2\). Hence a common divisor can only divide \(2\). If \(p=2\), then \(\gcd(5,9)=1\). If \(p\) is odd, both \(p^2+1\) and \(p^3+1\) are even, so the gcd is \(2\). Answer: all odd primes \(p\).

Let \(g=\gcd(m,n)\). The number \(a^g-b^g\) divides both expressions. Conversely, let \(d\) divide both. Since \( \gcd(b,d)=1 \), the inverse \(b^{-1}\pmod d\) exists. From \(a^m\equiv b^m\) and \(a^n\equiv b^n\), we get \((ab^{-1})^m\equiv1\) and \((ab^{-1})^n\equiv1\pmod d\). The Euclidean algorithm on the exponents gives \((ab^{-1})^g\equiv1\pmod d\). Hence \(a^g\equiv b^g\pmod d\), so \(d\mid a^g-b^g\).

Since \(4^m-1=2^{2m}-1\), the power formula gives \( \gcd(2^{2m}-1,2^n-1)=2^{\gcd(2m,n)}-1 \). This is the answer.

Let \(d\) be the gcd. Modulo \(x+y\), \(x\equiv-y\), hence \(x^{2k}+y^{2k}\equiv2y^{2k}\pmod d\). Since \( \gcd(y,x+y)=1 \), the common divisor \(d\) divides \(2\). Therefore only \(1\) and \(2\) are possible. If \(x,y\) are both odd, then \(x+y\) and \(x^{2k}+y^{2k}\) are even, so the gcd is \(2\). If one is even and the other is odd, then \(x+y\) is odd, so the gcd is \(1\).

Let an odd prime \(p\) divide both expressions. Since \(p\nmid b\), put \(t\equiv ab^{-1}\pmod p\). From \(a^2+b^2\equiv0\), we get \(t^2\equiv-1\); from \(a^3+b^3\equiv0\), we get \(t^3\equiv-1\). Dividing the second congruence by the first gives \(t\equiv1\), but then \(1\equiv-1\pmod p\), a contradiction. Thus there are no odd common prime divisors. If one of \(a,b\) is even, both expressions are odd, so the gcd is \(1\). If both are odd, both expressions are even and \(a^2+b^2\equiv2\pmod4\), so the gcd is \(2\).

We have \(u_{n+1}=u_n(u_n-1)+1\), so \(u_{n+1}\equiv1\pmod{u_n}\). If \(u_k\equiv1\pmod{u_n}\), then \(u_{k+1}=u_k^2-u_k+1\equiv1-1+1=1\pmod{u_n}\). Hence for every \(m>n\), \(u_m\equiv1\pmod{u_n}\). Thus a common divisor of \(u_m\) and \(u_n\) divides \(1\), so the gcd is \(1\).

Let \(Q=a^2+ab+b^2\). If \(3\mid n\), then \(a^3-b^3=(a-b)Q\), so \(a^3\equiv b^3\pmod Q\), and therefore \(Q\mid a^n-b^n\). In this case the gcd is \(Q\). Now suppose \(3\nmid n\). Let a prime \(p\ne3\) divide both \(Q\) and \(a^n-b^n\). Since \(p\nmid b\), put \(t\equiv ab^{-1}\pmod p\). From \(Q\equiv0\), we get \(t^2+t+1\equiv0\), hence \(t^3\equiv1\) and \(t\not\equiv1\). Thus the order of \(t\) is \(3\). But \(a^n\equiv b^n\) gives \(t^n\equiv1\), so \(3\mid n\), a contradiction. Therefore, when \(3\nmid n\), the only possible common prime divisor is \(3\). The number \(3\) divides \(Q\) exactly when \(a\equiv b\pmod3\); by coprimality neither is divisible by \(3\), and then \(Q\) is divisible by \(3\) but not by \(9\). Under the same condition \(a^n-b^n\) is divisible by \(3\). Answer: if \(3\mid n\), the gcd is \(Q\); if \(3\nmid n\) and \(a\equiv b\pmod3\), the gcd is \(3\); otherwise the gcd is \(1\).