Re: Find the minimum of a set in modulo n

In article <1160742449.230164.224880@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Dani Camps" <danicamps81@xxxxxxxxx> wrote:

What I don't understand is the following:

If I assume that the N points, a*N=lcm(a,n), that we will get between 0
and n are equally distributed between 0 and n, meaning that the
difference between two consecutive points is always the same, then this
distance between two consecutive points in the set must be n/N what it
is equal to gcd(a,n).

If the distance between two points is gcd(a,n) then you can find the
minimum point in your set d_min, because d_min + k*gcd(a,n) = b ->
d_min = b - k*gcd(a,n) = mod(b,gcd(a,n))

But the point that is missing in my understanding, is why all the N
points that I will get between 0 and n, are equally distributed (the
distance between them is constant).

Try asking again, but this time don't top-post.

Regards

Dani

Gerry Myerson wrote:
In article <1160646497.819962.278900@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Dani Camps" <danicamps81@xxxxxxxxx> wrote:

Thanks !

Please don't top-post.

PS: Some hint to understand? ;)

Sure. What don't you understand? meaning of gcd? method of computation
of gcd? meaning of division-with-remainder? method of computation of
division-with-remainder? meaning of answer? something else?

Dani


Gerry Myerson wrote:
In article <1160604284.472066.73650@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Dani Camps" <danicamps81@xxxxxxxxx> wrote:

I have the following problem. Imagine that you generate a set in
modulo
n in the following way:

s_k = (a*k + b) mod n

where a >= n and 0 <= b <= n. And we can assume all of them, a,b,n
are
integers

Let's give an example, imagine that:

a=90, b=5, n=54

If we start increasing k we will obtain the following set of numbers:

{5, 41, 23, 5, 41, 23, 5, 41, 23, 5, 41, 23,...}

We will always obtain periodic sequences where if:

lcm(a,n)=N*a=M*n

The period of the sequences is N, in our previous case
lcm(90,54)=270=3*90=5*54.
The actual numbers that we have in our basic period depend on the
value
of b, thus if in our previous example b=13, then the basic sequence
that we obtain is {13, 49, 31}.

We can say that given (a*k + b) mod n we can generate a set of N
elements that will have values between 0 and n.

So my problem is, given (a*k + b) mod n, is it possible to compute
the
minimum of this set of N elements as a function of a,b and n ?

1. Compute d = gcd(a, n).
2. Compute the remainder on dividing b by d. That's your answer.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)


--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)


--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: Find the minimum of a set in modulo n
    ... and n are equally distributed between 0 and n, meaning that the ... If the distance between two points is gcdthen you can find the ... Gerry Myerson wrote: ... The period of the sequences is N, ...
    (sci.math)
  • Re: Tau of SR
    ... it means that an observer who sees the events occur ... >> The individual coordinates have little meaning, ... > the distance and time between events, does not mean we should throw ... > determined by what *reference frame* the distance is measured in. ...
    (sci.physics.relativity)
  • Re: Tau of SR
    ... > The individual coordinates have little meaning, ... the distance and time between events, does not mean we should throw ... > Compare a 4-space rotation with a 3-space rotation. ... determined by what *reference frame* the distance is measured in. ...
    (sci.physics.relativity)
  • Re: God as collective consciousness
    ... Distance relies on rulers. ... I don't follow your meaning in the above paragraph. ... Both are in our brain. ... around the earth. ...
    (talk.origins)
  • Re: DNA = Information
    ... You analogy between matchsticks and DNA is silly. ... on their own and combine to produce sentences which also convey meaning. ... This is quite different from the manner DNA produces usable sequences. ...
    (talk.origins)