I would recomend Number Theory by George E. Andrews. It's great for a general introduction. While there aren't *that* many examples, there are hints and solutions to selected exercises. Additionally, at around $20CDN, if you find the book doesn't suite your needs, at least you didn't break the bank. Elementary Number Theory and Its Applications by Kenneth H. Rosen is a very broad introduction to number theory. The book covers many topics and has alot of examples. Perhaps even more importantly, it's written in a clear and sophisticated manner, and is well suited for both beginners and enthusiasts.
Hope this helps!
Maybe start with online articles on number theory rather than books?
Most textbooks on number theory are a bit unsatisfactory, since most of the classic problems that have been solved were solved by creating or importing chunks of new maths [abstract algebra, galois theory, statistical tracking of prime frequency...] into number theory.
So number-theory books usually give me the feeling of being a hasty overview of big topics pulled together, bundled together with the still-unsolved classic problems which those big topics have to-date failed to unlock. A bit of a mish-mash of rather difficult maths and a clump of questions the maths hasn't sorted out yet. At least to me....
Perhaps more worthwhile to just dig straight into a single specific pure-maths topic, like algebra or analysis.