2
$\begingroup$

I'm currently in a Discrete Mathematics class in college, and my professor is giving a quiz soon and told us what will be on it.

Problem is, I missed a day of class and I have no idea to figure out what he was saying when he gave us this problem:

Describe the sequence $X_{n+1} = (Ax_n + b) \mod p$

Is there a common name for this / what am I supposed to do here? I've done a couple of google searches but found nothing; I was hoping some of you might be able to clarify what this means.

Thank you in advance!

Edit: I think $p$ is meant to be interpreted as a prime number.

2 Answers 2

1

The person may have been discussing the Linear Congruential Generators. With suitable choice of parameters, these are a simple method to generate a pseudo-random sequence. Of course such a sequence is definitely not "random," since it is periodic. But if the period is extremely long, say of length $\approx 10^{100}$, the periodicity is not a practical drawback.

  • 0
    Okay, thank you! I'll go ahead and assume that's what he was asking for, then.2012-11-15
4

I really don’t know what he’s looking for. About all that you can say without further information is that the sequence is periodic. If $A$ is a multiple of $p$, the sequence is constant: $x_n=b\bmod p$ for every $n$ except perhaps the initial value. If $A$ is not a multiple of $p$, the sequence is periodic with period $p$ and runs through the values $0,1,\dots,p-1$ in some order. (Here I’m assuming that $p$ is intended to be a prime.)

  • 1
    @Benjamin: You’re welcome! I should have said that I was assuming in my response that $p$ was prime; I’ll add that now.2012-11-15