Theorems in number theory whose first proofs were long and difficult What are the examples of important theorems of number theory that has been shown to have surprisingly simple proofs though their first demonstration wasn't at all simple enough. Now simple proof is an ambiguous term but in this case it may be defined as a proof which is both short and elementary. As an example, the Kelly's proof of Sylvester-Gallai Theorem may be consdered.  

This example may be stretching the number theory context of your question, but it does at least involve the set $\mathbb N$ of natural numbers, and a significant part of elementary number theory is equivalent to finite set theory. (*see comments for this answer.)
It is a well known result that $\mathbb Q$ is countable - i.e., there is a bijection between $\mathbb N$ and $\mathbb Q$.
However, for over one-hundred years, no one was able to explicitly state such a bijection.  Rather, the proof relied on arranging $\mathbb Q$ in an infinite array including may redundant entries - e.g. $\frac11, \frac22, \frac33, \dots$
This method of proof is not difficult, but it is unnecessarily long and involves skipping over redundant entries.
Then, in $1989$, Yoram Sagher noticed a rather simple explicit bijection between $\mathbb N$ and $\mathbb Q^{+}$.
Let $\frac{m}{n} \in \mathbb Q^{+}$ with $gcd(n,m)=1$, and let $q_1, q_2, \dots, q_k$ be the prime factors of $n$.  Then
$$f(\frac{m}{n}) = m^2n^2/(q_1q_2\cdots q_k)$$
is the desired bijection.  Given the simplicity of $f$, it is surprising that no one had noticed it before.
Note that the inverse is (easily) computable, so you say what the $n$'th rational number listed is for any $n$.
You can read details here : Counting the rationals quickly
