# Finding coprime integers near a lattice point

I have a list $L$ of ordered pairs $(n,m)$ where $n$ and $m$ are integers. I would like to know which elements $(n,m)$ in $L$ satisfy the property that $\gcd(n+i,m+j) \neq 1$ for $i =-1,0,1$ and $j =-1,0,1.$ For example the point $(55,21)$ has this property since $[(55+i,21+j) ] = [(54,20),(54,21),(54,22),(55,20),(55,21),(55,22),(56,20),(56,21),(56,22)].$ I have tried the following : for (n,m) in L: for i in range(-1,2): for j in range(-1,2): if gcd(n+i,m+j)!=1: print(n,m) which returns any point with $gcd =1$ which is not what I want. Thanks very much for your help!

edit retag close merge delete

I suppose you test only for (i,j) different from (0,0), otherwise (55,21) wouldn't be a solution.

I am not quite sure what you mean, since $\gcd(1275,1309)=17$.

I mean that (1275,1309) is a solution for the same problem (with same notations as in my answer) with R=[(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]

Sort by » oldest newest most voted That seems to work:

R=[(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)];

N=100;

L=[(n,m) for n in xsrange(2,N) for m in xsrange(n,N)];

v=[(n,m) for (n,m) in L if len([(i,j) for (i,j) in R if gcd(n+i,m+j)==1])==0];

print v

more