For an introductory undergrad course I'd say the book to use by a long-shot is Kenneth Rosen's Elementary Number Theory and its Applications

The theory is all there, but it's placed nicely in a context appropriate for a mixed bag of undergrad students by a large number of interesting-but-doable exercises and informative historical notes. Modern applications to computer science, cryptography, etc are all there and can be emphasized (or not) as you see fit.

This is what I'd read if I were you. Last time I checked, the book was annoyingly expensive - but this is the only criticism of it I have. Most students give this book very favorable reviews, too.