Let $m=n+k$, for some $k \ge 1$. So, $1=gcd(n+i,m+i)$ for all $i=1,2,....,k$. Thus, $1=gcd(n+i,(m+i)-(n+i))=gcd(n+i,k)$. Let $k > 1$ . So, there is a prime divisor $p$ of $k$ and $p \le k$. Also, note that among the $k$ consecutive natural numbers $n+i$, there must be a multiple of $p$. Thus, $p\mid k$ and $p \mid n+r$ for some $r$ such that $1 \le r \le k$. Thus, by definition of gcd, $p \mid gcd(n+r,k) =1$, which is a contradiction as $p>1$. So, $k=1$ and the set of solutions $(m,n)$ is : $(m,m+1)$ for all naturals $m$.

correct!

See also http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=616994&p=3676261&hilit=gcd#p3676261, with a more challenging variant examined.

Is this Indian RMO this year? RMC 2007 District Round, 7th grade Problem 3 Let $a,b$ be integers such that $b>a\ge 2$. Prove that if the number $a+k$ is prime with the number $b+k$ for all $k=1,2,3,\cdots,b-a$, then $a$ and $b$ are consecutive.

Recycling is encouraged in these politically-correct and environmental-sensible ages, it seems

A bit hehe just a bit, but easy different solution.. Let $n=x, m=x+k,$ where $x,k\in\Bbb{N}$ Now observe that, both $m$ and $n$ will yeild the same remainder when divided by the distance between the two numbers. That is, $m\equiv c \pmod{k}$ and, $n\equiv c \pmod{k}$, for some $c\in\Bbb{N}$ and $0\leq{c}<k$ Therefore, as we take the $k$ gcd's, there will be exactly one gcd which will be divisible by $k$. And hence, in that gcd, the numbers will not be coprime.. $\therefore$ We can conclude that the only possible solution to this will be $(m,m+1)\forall m\in\Bbb{N}$ Q.E.D. $\square$