Re: Find the minimum of a set in modulo n

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)
.

Relevant Pages

  • 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)
  • 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: Consciousness "Hard Problem"
    ... > Sequences of words have meaning. ...
    (sci.logic)
  • Re: Non-beneficial Gaps
    ... ratio of potentially meaningful vs. meaningless 2-character sequences ... english language, we have 26 letters to create words ... sequences of letters that can contain "meaning", that is, convey ...
    (talk.origins)
  • 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)