Numbers in array and its exponents ( congruence operation )
joseluismarchetti
The question is in the end.
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,
Ask me about System Design
wrote:
Try 2 and 7. (Hint: it won't hit all columns. Why?)
Then look up "primitive roots" to learn more of the
state of affairs regarding your question.
Gerhard "Ask Me About System Design" Paseman, 2009.11.20
William Elliot
>
> 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)
= 3 (mod 5)
> 2^4 = 16 ( column 1)
= 1 (mod 5)
> 2^5 = 32 ( column 2)
= 2 (mod 5)
> 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.
>
False. For integers modulus n, and a coprime to n,
{ a^i | i in N } may not be { 1, 2,.. n-1 }
For one thing you have to rule out a = 1, which is coprime to n.
Now 3 is coprime o 8 and the powers of three
for integers modulus 8, are 3, 1, 3, 1, ....
> How can this be proved ?
>
It can't be proved.
joseluismarchetti
my question. I was staring to the answers for a while until I realized
the operation is multiplication and not exponent!
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
So again:
2*1 = 2 ( column 2)
2*2 = 4 ( column 4)
2*3 = 6 ( column 1)
2*4 = 8 ( column 3)
2*5 = 10 ( column 5)
2*6 = 12 ( back to column 2)
The question should be:
If the number I chose is coprime with n ( 2 and 5 are coprime in my
example ) the multiplication results would land in all possible
columns
before repeating a column.
How can we prove that ?
Thanks again.
cbr...@cbrownsystems.com
wrote:
If k is coprime to n, and some column does not appear in the set of
products (k*1, k*2, ..., k*n), then by the pigeonhole principle, there
must be some a, b such that k*a and k*b yield the same column. Without
loss of generality, assume that a is greater than b.
But if k*a and k*b are in the same column, then they have the same
remainder r when divided by n; i.e. if r is that column, then
k*a = x*n + r
k*b = y*n + r
for some (distinct!) x and y. Now subtract the above two equations and
we get
k*a - k*b = x*n - y *n
and then
k*(a - b) = (x - y)*n
which describes a common multiple of k and n.
Since by assumption a and b are different, (a-b) is not 0; and since
both a and b are less than n, (a-b) must be less than n.
But since k is coprime to n, the /least/ common multiple of k and n is
k*n; contradiction. So there can be no such a and b.
Cheers - Chas