Discrete Math › Section G · Additional topics › Topic G.3
GCD, congruences, and modular arithmetic
The greatest common divisor and arithmetic with remainders are the working tools of number theory. One fast, very old algorithm computes the gcd, and the same calculation, run backwards, solves equations in which only remainders matter.
In this topic
- Arithmetic that wraps around
- Greatest common divisor
- The Euclidean algorithm
- Worked example: gcd and Bezout coefficients
- Bezout's identity and Euclid's lemma
- Congruences
- Calculating with congruences
- Worked example: solving a linear congruence
- Linear Diophantine equations
- Fermat's little theorem
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…