When I took number theory in the fall we used Number Theory: A Lively Introduction, by Pommersheim, Marks, and Flapan. It's good in that its explanations are clear and simple and if you haven't written proofs before it provides a good introduction, but I suspect it is too simplistic for your purposes. It's a fun book and the math content is serious, but it's not the most rigorous book you could get. I'm also familiar with Tattersall's Elementary Number Theory in Nine Chapters, which is for more sophisticated students. My professor says it's a good introduction, but I found it to be riddled with typos. It does have some rather subtle proofs in the exercises, so it's interesting in that respect.
The disadvantage of both these books is that neither has answers in the back. I haven't looked for a solution manual, so I don't know about that.