One of the biggest myths in number theory is that work on Fermat's last theorem played a large role in the development of ideal theory and algebraic number theory. In fact it was much loftier goals such as the quest for higher reciprocity laws that were the true sources of inspiration. For references see e.g. Lemmermeyer's book "Reciprocity Laws" p. 15 (notes on Lagrange).
Speaking of FLT, recall the "legend" legend that Kummer submitted a false proof based on the erroneous assumption that cyclotomic number rings were UFDs. Edwards argued that this may be a myth and put forth an argument that, instead, Kummer's mistake was based on a simple error not related to any UFD assumption. However R. Bolling recently discovered new evidence that seems to lend strong support to the veracity of to the original legend.
Above there is discussion of Cantor diagonalization. In claim that Kummer did in fact diagonalization was actually discovered first by du Bois-Reymond mistakenly assume facts equivalent to unique factorization in his pioneering work on "orders various rings of infinity" where he diagonalized on growth rates cylotomic integers in one of functionshis early papers (which was not an attempted proof of FLT). So its attribution only part of this legend is actually true.
The above two paragraphs don't really do justice to Cantor the complex history. For a more faithful rendition I highly recommend that the interested reader also consult Franz Lemmermeyer's recent paper  which, imho, is another legendone of the most interesting historical works on number theory in quite some time.
By the way, far less known than the constructivity of Euclid's proof that there are infinitely many primes (cf. M. Hardy abovebelow) is the striking fact that Euclid's constructive proof generalizes quite widely - namely to any infinite ring having fewer units than elements. For this little-known proof see my post here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1209616#p1209616 http://google.com/groups?selm=y8zk5f3rn4e.fsf%40nestle.csail.mit.edu
 Franz Lemmermeyer. Jacobi and Kummer's ideal numbers.
Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg v. 79, 2, 2009, 165-187. http://dx.doi.org/10.1007/s12188-009-0020-5