27 topics
Number theory help, from divisibility to congruences
Number theory is where obvious facts about whole numbers suddenly have to be proved, and where dividing stops producing a decimal and starts producing a remainder you are expected to work with. Most of a first course lives inside modular arithmetic, and most of the marks lost there come from assuming mod obeys every rule ordinary arithmetic does.
Where students get stuck
Dividing in modular arithmetic keeps giving me wrong answers
There is no division mod n. What stands in for it is multiplying by an inverse, and a has an inverse mod n only when gcd(a, n) = 1. So 2x ≡ 4 (mod 6) cannot be handled by cancelling the 2: it has two solutions, x ≡ 2 and x ≡ 5. When the gcd is d and d divides the right-hand side, divide the modulus by d as well and solve the smaller congruence. When d does not divide it, there is no solution at all. Cancelling without first checking that gcd is the single most common lost mark in the course.
The extended Euclidean algorithm — I get the gcd but not the coefficients
Run it in two passes and it stops being fiddly. Going forward, do the ordinary algorithm and keep every line written as dividend = quotient × divisor + remainder. Going backward, start from the line whose remainder is the gcd, rearrange so the gcd stands alone, then substitute the previous line’s remainder in and collect terms. Repeat until only your two original numbers are left. Never multiply the numbers out along the way — keep them symbolic, or you lose track of which coefficient belongs to which and cannot read off x and y at the end.
Fermat’s little theorem and Euler’s theorem look like the same theorem
Euler’s is the general statement and Fermat’s is the special case where the modulus is prime. Euler says that a raised to phi(n) is congruent to 1 mod n whenever gcd(a, n) = 1, and when n is prime phi(n) is n − 1, which is exactly Fermat. Use either one to shrink an exponent before you compute anything. To find 3 to the 100 mod 7, notice that 3 to the 6 is 1, divide 100 by 6 to get remainder 4, and the answer is 3 to the 4 mod 7. The theorem is not there to be quoted, it is there to reduce the exponent.
I can state the Chinese Remainder Theorem, I cannot use it
Build a number that is correct in one modulus and invisible in the others, then add the pieces. For x ≡ 2 (mod 3) and x ≡ 3 (mod 5), the product is 15. For the first congruence take 15 divided by 3, which is 5, find the inverse of 5 mod 3, and multiply through by the required residue 2. Do the same for the second congruence, add both pieces, reduce mod 15. Each piece is deliberately a multiple of the other modulus so it contributes nothing there. The answer is unique modulo the product, as long as the moduli are pairwise coprime.
What's covered
Number Theory topics you can work through with a tutor, generate practice on, or turn into flashcards and a study plan.
Divisibility and primes
- The division algorithm
- Greatest common divisor and least common multiple
- The Euclidean and extended Euclidean algorithms
- Bézout’s identity
- The sieve of Eratosthenes and prime distribution
- The fundamental theorem of arithmetic
Congruences
- Modular arithmetic and residue classes
- Linear congruences
- Modular inverses
- The Chinese Remainder Theorem
- Systems of congruences
Classical theorems
- Fermat’s little theorem
- Euler’s theorem and the totient function
- Wilson’s theorem
- Order of an element and primitive roots
- Quadratic residues and the Legendre symbol
Proof techniques for the integers
- Proving irrationality by contradiction
- Induction and strong induction on integers
- The well-ordering principle
- Infinite descent
- Testing a conjecture and finding counterexamples
Applications
- Modular exponentiation by repeated squaring
- RSA key generation and encryption
- Check digits and hashing
- Diophantine equations
- Pythagorean triples
- Continued fractions
Number Theory questions
I am taking this for cryptography. Does it cover the RSA side properly?
Yes. The applications group above is built around it: why the modulus is a product of two primes, why the exponents are inverses mod phi(n), why decryption returns the original message, and how repeated squaring keeps the numbers manageable. Bring the parameters your course uses and it will work through a key with you.
Do I have to memorise all these theorems, or can I look them up?
Check your course rules, because they vary. The more useful skill is recognising the situation each theorem is for — a huge exponent points at Euler, several moduli at once points at the Chinese Remainder Theorem. Flashcards handle the statements; recognising when to reach for one is what the sessions work on.
My assignment is due tonight and I am out of time. Will it just solve it?
No. It will take one question and work through it with you, then leave the rest of the set to you. Submitting work you did not do is academic misconduct at every school we deal with, and number theory assignments in particular are almost always followed by a test on the same material.
Can it handle the very large numbers in these questions?
It works them the way you have to on paper — reducing early, squaring repeatedly, keeping every intermediate value small — on the whiteboard where you can follow each step. It is a tutor rather than a calculator, so check arithmetic you are going to hand in.
Stuck on number theory right now?
Talk it through out loud, share your screen, and watch it worked out step by step on a whiteboard.
Start free — no card