baab mod axxxxxxxx
- Let be a common divisor of and . Consider all of the copies of which add up to . Take away all the instances of that evenly cover . What’s left must evenly divide .
- Alternatively, if we consider to be a common divisor of and we can copy it to cover evenly and as many times as necessary to add up to . Therefore it evenly divides .
If the visual demonstration is unconvincing, the above can also be shown algebraically using the definition of divisibility.
Let be the common divisor of and . We can write and as , for . We can also write for .3 We must show divides .
We must also show that if is the common divisor of and , then it divides . Let , . Once again we know .
This concludes the proof.