Reddit mentions of Elementary Number Theory and Its Application, 6th Edition

I think an introductory book on number theory would be useful, probably more immediately useful than a book on abstract algebra. Algebra is something you'd want to look into eventually, but you don't need all of the associated machinery to learn about Z/nZ, and algebra may be more abstract that you want, as an introduction.

I had Rosen, which was okay, but not great. Definitely not worth the price. Still, it may be useful to see the typical ToC of an intro number theory book so you can try to find a better one.

Last term, on a whim I took an elective math course called "Introduction to Number Theory and Cryptography". The crypto didn't come til the end, but by then, with such an extensive background in number theory, it was easy, intuitive, and I understood.
We used Elementary Number Theory which I just realized is written by Kenneth Rosen (Discrete Math and it's applications). The book was great, and by the later chapters, Crypto wasn't just a list of algorithms, and oh good, they work- I actually understood it, I grokked it.

This term, I have a mandatory course in Crypto run by the CS department. It's just "here is the algorithm" over and over, with only a bit of background math proving things. We're using Cryptography: Theory and Practice, which has a lot of algorithms, and descriptions, but doesn't necessarily provide the rigorous math proofs I prefer.