Euclid Alg
A unit about the idea that if $d$ divides $a$ and $b$, then $d$ divides any linear combination of $a$ and $b$. This intuition underlies Bezout's lemma, the Euclidean algorithm, and the division algorithm, as well as a technique which I privately call remainder bounding. One very good example of a problem of this feeling is SL 2016 N4 (sort of the crown example of remainder bounding).
EuclidAlg is one of the units that revolves around a particular instinct and has a certain philosophy. Eulidean algorithm, remainder bounding and adjacent ideas are the topic of this unit.
Philosophy
Suppose we are dealing with a divisibility $A \mid B$. Then, we can do the following things:
- Subtract a multiple of $A$ from $B$, and divisibility still holds
- Throw out factors of $B$ that are coprime with $A$, and divisibility still holds.
- If we end up with a situation where |RHS|<|LHS|, deduce that |RHS|=0.
In many number theory problems, this technique is useful. Evan calls it "remainder bounding", because we want to take the remainder of $B$ mod $A$ and compare it with $A$.
This unit is a collection of problems where this technique is useful.
What you can take from this unit
If you want to get comfortable with solving most of the easy-medium level number theory problems, you should master this instinct.
Notable problems
There are many FEs where this philosophy is useful. Here are some of them.
- Shortlist 2011 N3: A very interesting FEs from the IMO shortlist.
- Shortlist 2013 N1: An easier problem from which beginners can understand remainder bounding.
- Shortlist 2016 N6: This one is a nice ego booster.
- Shortlist 2004 N3: A typical FE where remainder bounding is a necessary technique.
Non-FE problems
- HMMT 2017 A4: A nice problem from HMMT that demonstrates this philosophy well.
- Shortlist 2016 N4: This is the crown example of remainder bounding.