Period finding: Why x^r (mod N) is a periodic function?

645 Views Asked by At

If I take an example, I can observe that it is the case, but I am not able to understand why an exponentially rising function x^r would hit say x^r (mod N) periodically.

r is a variable here, and x and N are given inputs.

Example: N = 21, x = 2, then period is 6.

2^6(mod21) = 1, 2^12(mod21) = 1.