Common modulus attack on RSA when the 2 public exponents differ by a single bit
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$.