Books on Number Theory for Layman
Solution 1:
A Classical Introduction to Modern Number Theory by Ireland and Rosen hands down!
Solution 2:
I would still stick with Hardy and Wright, even if it is quite old.
Solution 3:
I like Niven and Zuckerman, Introduction to the Theory of Numbers.
Solution 4:
Serre's "A course in Arithmetic" is pretty phenomenal.
Solution 5:
I recommend Primes of the Form x2 + ny2, by David Cox. The question of which primes can be written as the sum of two squares was settled by Euler. The more general question turns out to be much harder, and leads you to more advanced techniques in number theory like class field theory and elliptic curves with complex multiplication.