I discovered this interesting discussion on Fast Exponentiation.
Here I try to capture some main points for better intuition and understanding.
Khan Academy has an interesting exercise of visualizing modulus as a clock.
Question: What is -29 mod 4
Answer: 3
Divide -29 by 4 and pick the first positive value.
- 26≡11 (mod 5) => 26 mod 5 is equal to 11 mod 5