##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Why modulo works
Here is the observation: . Why does this work? If divides both and , then also divides , and , and so on. The remainder is just minus some multiple of .
So any common divisor of and is also a common divisor of and . This means you can replace the larger number with a remainder, making the problem smaller each time. The numbers shrink fast.
