You can easily prove this result by using group theory,
for example, 2 and 5 are relatively prime, the order of 2(with respect to multiplication) in is 5, thus it exhaust all the element before reperting .
Introduction:
=============
Another way to see congruences is to put the numbers in an array of width n.
In the following example n is 5:
col 1 2 3 4 5
--------------------------
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30
31 32 33 34 35
36 37 38 39 40
Numbers in the same column are congruent module 5, for instance 13 and 18
are in the same column (3) so they are congruent mod 5,
both gives 3 as a remainder when divided by 5.
This way is very simple to see how some congruence operations work,
for instance, two numbers will go together to the same column if I add a number x to
them ( if x is 3, then 13+3=16 and 18+3 is 21, 16 and 21 now are on column 1 )
What I am interested in:
========================
Lets look at the exponent operation, get number 2 in the table above, it is
on column 2, now lets see in what columns 2^x result lands:
2^1 = 2 ( column 2)
2^2 = 4 ( column 4)
2^3 = 8 ( column 3)
2^4 = 16 ( column 1)
2^5 = 32 ( column 2)
The results landed in all possible columns, except 5, before it went back to
its initial column 2.
I read that if the number I chose is coprime with n ( 2 and 5 are coprime in
my example ) the exponent results would land in all possible columns (except n)
before repeating a column.
Question:
=========
How can this be proved ?
Thanks,