# Numbers in array and its exponents ( congruence operation )

• Nov 20th 2009, 01:21 PM
jmarchetti
Numbers in array and its exponents ( congruence operation )
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,
• Nov 20th 2009, 11:46 PM
Shanks
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 $Z_5$ is 5, thus it exhaust all the element before reperting .