A118119 Smallest integer m for which gcd(m^n + 1, (m+1)^n + 1) > 1.

2, 5, 8, 6, 2, 4, 5, 2, 2, 10, 8, 6, 2, 3, 6, 14, 2, 37, 6, 2, 2, 10, 2, 6, 2, 2, 6, 10, 2, 52, 22, 2, 2, 4, 8, 26, 2, 3, 5, 5, 2, 24, 6, 2, 2, 32, 6, 4, 2, 2, 8, 5, 2, 6, 5, 4, 2, 230, 2, 44, 2, 2, 17, 4, 2, 55, 5, 2, 2, 34, 2, 9, 2, 3, 8, 4, 2, 6, 6, 2, 2, 2, 3

Offset: 2

Author

Adam Kertesz, May 12 2006; May 13 2006

Keywords

• nonn

Comments

Let f(x) := x^n + c and g(x) := (x+1)^n + c. It can be shown that there exists an integer polynomial s(x) and t(x) such that s(x) f(x) + t(x) g(x) = resultant(f, g) for all x. Let p be a prime number such that f(x_0) == 0 (mod p) and g(x_0) == 0 (mod p) for some x_0 in Z/pZ. Then, s(x_0) f(x_0) + t(x_0) g(x_0) == 0 == resultant(f,g) (mod p). So, p|resultant(f,g). If gcd(f(x_0), g(x_0)) > 1 for some integer x_0, there exists a prime number p which divides gcd(f(x_0), g(x_0)). We can assume that p is a prime factor of resultant(f,g). Let S be a set of x (in Z/pZ) such that x^n == -c (mod p). If we are able to find consecutive terms y, y+1 in S, then y is one of the solutions such that gcd(f(y),g(y)) > 1. - Hiroaki Yamanouchi, Mar 11 2015

Examples

			a(3)=5 because gcd(2 = 1^3 + 1, 9 = 2^3 + 1) = gcd(9, 28) = gcd(28, 65) = gcd(65, 126) = 1 and gcd(126 = 5^3 + 1, 217 = 6^3 + 1) = 7 > 1.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 2..10000

Crossrefs

Sequences of smallest m with gcd(m^n + c, (m+1)^n + c) > 1: A255852 (c=2), A255853 (c=3), A255854 (c=4), A255855 (c=5), A255856 (c=6), A255857 (c=7), A255858 (c=8), A255859 (c=9), A255860 (c=10), A255861 (c=11), A255862 (c=12), A255863 (c=13), A255864 (c=14), A255865 (c=15), A255866 (c=16), A255867 (c=17), A255868 (c=18), A255869 (c=19)

Programs

Maple

A118119 := proc(n) local k ,g; for k from 1 do g := igcd(k^n+1,(k+1)^n+1) ; if g>1 then return k ; end if; end do: end proc: # R. J. Mathar, Mar 07 2011

Mathematica

A118119[n_] := Module[{m = 1}, While[GCD[m^n + 1, (m + 1)^n + 1] <= 1, m++]; m]; Table[A118119[n], {n, 2, 50}] (* Robert Price, Oct 15 2018 *)

PARI

{ a(n,c=1) = my(f,g); g=gcdext(x^n+c,(x+1)^n+c); f = factor(lcm(denominator(content(g[1])),denominator(content(g[2]))))[,1]; g=[]; for(i=1,#f, g=concat(g, apply(lift, polrootsmod( gcd([x^n+c,(x+1)^n+c]*Mod(1,f[i])), f[i] ) )); );vecmin(g); }  \\ Max Alekseyev, Aug 06 2015

PARI

\\ This naive form is typically faster than the polynomial gcd method above. Perhaps a combined algorithm which tries this first before calling the other would be fastest.
a(n)=for(m=2,oo, if(gcd(m^n + 1, (m+1)^n + 1)>1, return(m))) \\ Charles R Greathouse IV, May 08 2024

Python

from itertools import count
from math import gcd
def A118119(n): return next(filter(lambda m:gcd(m**n+1,(m+1)**n+1)>1,count(1))) # Chai Wah Wu, May 08 2024

Extensions

Edited by Max Alekseyev, Aug 06 2015