Common modulus attack on RSA when the 2 public exponents differ by a single bit This is an exam question an i have no idea how to recover the message m. 

John wants to send an encrypted message to mary who has a pair of RSA keys, However, John does not know Mary's public key and so John sends an email to Mary to ask for the key. mary's email reply is intercepted by Peter who replaces Mary's public key $\{e,n\}$ with $\{e_2, n\}$ where $e_2$ is obtained by changing one bit in $e$ from $0$ to $1$. Now john encrypts a message $m$ to Mary by using $\{e_2, n\}$. As Mary cannot decrypt the message, she resends her public key to John and asks John to send the encrypted message to her again. Peter does not interrupt this time. However, Peter eavesdrops the whole communication and obtains both encrypted message (one encrypted by $\{e_2,n\}$ and one by $\{e,n\}$. Explain how Peter can recover the message $m$.

How can encryption with both $\{e_2,n\}$ and $\{e,n\}$ be used to recover the message $m$?

I did think that it is related to common module attack, but i have no idea how to prove that $\gcd(e,e_2)=1$.

Does anyone have some idea on how to recover the message?
Proving $\gcd(e, e_2) = 1$ is easy; all you need to do is rely on the property 

$\gcd(e, e_2) = \gcd(e, e-e_2)$

Now $e$ and $e_2$ differs in a single bit (because Peter flipped one bit in $e$ to form $e_2$), and hence $|e - e_2|$ is a power of two (the sign of which depends if Peter flipped a zero bit or a one bit), and hence has $2$ as its only prime factor.  On the other hand, we know $e$ is odd (because it is an RSA exponent), and so $e$ and $e-e_2$ do not have any prime factors in common (and hence, $e$ and $e_2$ do not either).

This result implies that the method you already have (which is effectively using the Euclidean method on the values $e$ and $e_2$ to compute $M^{gcd(e, e_2)}$) will give you $M$.