For courses in Elementary Number Theory for non-math majors, for mathematics education students, and for Computer Science students. This is an introductory undergraduate text designed to entice non-math majors into learning some mathematics, while teaching them to think mathematically at the same time. Starting with nothing more than basic high school algebra, the reader is gradually led from basic algebra to the point of actively performing mathematical research while getting a glimpse of current mathematical frontiers. The writing style is informal and includes many numerical examples, which are analyzed for patterns and used to make conjectures. The emphasis is on the methods used for proving theorems rather than on specific results.