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,