Consider divisibility, GCD, LCM, and related theorems which are usually covered early in elementary number theory books. I've seen a few different styles for dealing with these things.
1. One style involves introducing a ton of variables. If you've got A divides B somewhere, introduce C=B/A. If you've got an A that does not divide B, introduce q = floor(B/A), r = B%A. You start with some theorem you want to prove about A and B, and soon you've got a dozen or two variables floating around and end with something like "we see that z = t and thus the theorem is proved" and the poor student has no idea what the heck just happened.
It's like A and B got smashed together in a Large Integer Collider and you are supposed to figure out things from the shower of divisors.
2. Another style is to do unique factorization as soon as possible. GCD and LCM can then be dealt with in terms of factorizations.
3. I believe I've even seen a textbook that took what in the other approaches is a theorem that the GCD of A and B is the minimum positive linear combination of A and B and defined that as the GCD.
I think that for a given student there is a good chance that one of these approaches (or others that I'm sure I've forgotten about) will work a lot better than the others and one will work a lot worse than the others. Finding an approach that works for everyone in a class could be difficult.
It focuses on factoring and primality testing, but it also covers a lot of introductory number theory. IIRC it also covers continued fractions as used for factoring and the quadratic sieve and MPQS. The pseudo-code given in the book is very easy to translate into python, which supports large integers and efficient exponentiation mod P.