How did Euler disprove Mersenne's conjecture? In 1644, Mersenne made the following conjecture:

The Mersenne numbers, $M_n=2^n−1$, are prime for $n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257$, and no others.

Euler found that the Mersenne number $M_{61}$ is prime, refuting the conjecture.
For context, $M_{61} = 2 305 843 009 213 693 951$. I imagine that this would be incredibly large for most 18th-century number theorists.
Thus, a natural question is: Do we know how Euler proved this? From what I've read, he wasn't Ramanujan-like in his results. Indeed, he tended to have proofs for such things, even if he never published/mentioned them (unless to show colleagues that he had already derived their published results years before them). Yet, I also doubt that he checked primes up to $\sqrt{M_{61}}$.
(And if it was indeed a case of mathematical mysticism, how could one use non-Eulerian cleverness to offer an alternative disproof? )
Edit: As Daniel Fischer commented, it actually wasn't Euler! "$M_{61}$ was determined to be prime in 1883 by Ivan Mikheevich Pervushin, though Mersenne claimed it was composite, and for this reason it is sometimes called Pervushin's number," according to Wikipedia. It was disproven a century later, but I suppose it would still be useful to know how it was disproved.
 A: As others have pointed out, it wasn't Euler who first proved $M61$ to be prime, but the Russian mathematician-priest L.M. Pervushin (or as it appeared in contemporary printed literature, Pervouchine). 
He sent his "proof" to the Imperial Academy Of Sciences of Saint-Petersbourg in 1883, however this paper is unavailable to the general public at this time (it is housed in the Academy archives and no scan of the document has been made public). On the other hand, a short note in the 1887 edition of the Bulletin de l'Académie Impériale des Sciences de Saint-Pétersbourg, tome XXXI, columns 532-533, entitled "Sur un nouveau nombre premier, annoncé par le père Pervouchine" reveals the following interesting points (in original French and corresponding English translation):

En novembre de l'année 1883, dans la correspondance de notre Académie
  se trouve une communication qui contient l'assertion que le nombre
$$ 2^{61}-1 = 2305843009213693951 $$
est un nombre premier. Ce résultat nous a été annoncé par son auteur, L.M. Pervouchine, prêtre à Chadriusk (gouvernement de Perm),
  qui nous avait envoyé auparavant des communications intéressantes sur
  quelques propositions arithmétiques analogues.

In English:

In November of the year 1883, within the communications of our Academy
  there is a letter containing the assertion that the number
$$ 2 ^ {61} -1 = 2305843009213693951 $$
is a prime number. This result was announced to us by its author, L.M. Pervouchine, priest at Chadriusk (Perm state),
  who had previously sent us interesting papers on
  some similar arithmetic propositions.

Disappointingly, the Academy then goes on to state the following:

(...) laissant à la charge de l'auteur la responsabilité pour
  l'exactitude du résultat qu'il a obtenu au bout de ses longs et
  fatiguants calculs.

In English:

(...) leaving the responsibility of the result's accuracy to the
  author, which he obtained after a series of long and tiresome
  calculations.

Finally, a note on the letter itself:

Le manuscrit du père Pervouchine contenant sa communication de l'année
  1883 (...) est accompagné de de quelques tables, calculées par
  l'auteur, et destinées à faciliter la vérification du résultat qu'il a
  obtenu.

In English:

The manuscript of father Pervouchine, containing his 1883 letter
  (...) is accompanied by some tables, calculated by
  the author, and intended to facilitate the verification of the result he
  obtained.

So it would appear that the method of calculation was indeed a heavily manual task, parts of which were recorded in tables and sent in a letter to the Academy. It looks like there was no peer review of these calculations, at least not up to 1887.

The note "Sur un nouveau nombre premier, annoncé par le père Pervouchine", Bulletin de l'Académie Impériale des Sciences de Saint-Pétersbourg, tome XXXI, columns 532-533, can be found here.
Also noteworthy is this interesting 1987 paper by Guy Haworth that details the history of the discovery of Mersenne primes.
