Results 1 to 2 of 2

Math Help - Numbers in array and its exponents ( congruence operation )

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    1

    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,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    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 .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime numbers and congruence equations.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 21st 2010, 11:54 PM
  2. Create whole numbers within array
    Posted in the Math Topics Forum
    Replies: 6
    Last Post: October 13th 2010, 01:38 PM
  3. Congruence with rational numbers
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 10th 2008, 10:23 AM
  4. Prime Numbers Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2007, 04:43 AM
  5. Array of Numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 24th 2006, 07:33 PM

Search Tags


/mathhelpforum @mathhelpforum