Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a linear function without modulo like $y=ax+b$, if we know two points of $(x,y)$, the parameters $a$ and $b$ can be easily derived.

But in the case of modulo linear function: $y=ax+b \pmod n$, assuming $n$ is a known integer and $\gcd(a,n)=1$, how many integer points of $(x,y)$ do we need to know in order to determine the integers $a$ and $b$? Here $x,y$ are integers in the range $0$ to $n-1$.

share|improve this question
    
By the way, unless $n$ is prime, the structure $\lbrace0,\dots,n-1\rbrace$ isn't a field. –  Gerry Myerson Oct 12 '11 at 6:22
    
You can only determine $a$ and $b$ modulo $n$; and you should not call it a "field", since "field" is a term of art with a specific meaning. Do you get to "choose" the values of $x$ (or $y$) that you will be given, or are you just given two values and you have no control over them? –  Arturo Magidin Oct 12 '11 at 6:30
    
indeed, i misused the term "field". corrected. –  jscoot Oct 12 '11 at 6:36
add comment

3 Answers 3

up vote 3 down vote accepted

You can only determine $a$ and $b$ modulo $n$; that is, if $b\equiv b'\pmod{n}$ and $a\equiv a'\pmod{n}$, then for every $x$ you will have $ax+b\bmod n = a'x+b'\bmod n$.

If you have some control over which points you are given (e.g., you get to specify their $x$-coordinates, or you get to specify the $x$-coordinate of the second point after being given the first point), then you only need two points.

If you know two values, $(x_1,y_1)$ and $(x_2,y_2)$, then $x_1\equiv x_2\pmod{n}$ if and only if $y_1\equiv y_2\pmod{n}$, so we may assume that they are not the same point modulo $n$. This gives you: $$\begin{align*} y_1 &\equiv ax_1 + b\pmod{n}\\ y_2 &\equiv ax_2 + b \pmod{n}. \end{align*}$$ and hence $$y_1 - y_2 \equiv a(x_1-x_2)\pmod{n}.$$ Now notice that $\gcd(n,y_1-y_2) = \gcd(n,a(x_1-x_2)) = \gcd(n,x_1-x_2)$, since $\gcd(n,a)=1$ by assumption. Therefore, if we let $d$ be that gcd and write $n=dm$, $y_1-y_2 = dy'$, $x_1-x_2 = dx'$, then we have $$\begin{align*} y_1-y_2 &\equiv a(x_1-x_2)\pmod{n}\\ dy' &\equiv adx' \pmod{dn'}\\ y' &\equiv ax'\pmod{n'} \end{align*}$$ and now $\gcd(n',x') = 1$. Hence, we can solve for $a$ in that congruence (modulo $n'$). So if you have enough control over the points you are given that you can ensure that $\gcd(n,x_1-x_2)=1$, this will solve the problem, since once you have $a\bmod n$, you can find $b\bmod n$.

If you don't have control and you are unlucky enough that $\gcd(n,x_1-x_2)=d\gt 1$, then this gives you $d$ possible values of $a$ modulo $n$, some of which may or may not be relatively prime to $n$ (for example if $n=12$ and $d=3$, and the result as $a\equiv 1 \pmod{4}$, then this gives you the possibilities $a=1\bmod 12$, $a=5\bmod 12$, and $a=9\bmod 12$, of which the latter is not relatively prime to $n$). So the two points may not suffice.

For example, say $n=12$, and the points are $(4,7)$ and $(1,10)$. Then you get $-3 \equiv 3a\pmod{12}$, hence $-1\equiv a\pmod{4}$. That gives $a\equiv 3,7,11\pmod{12}$. Of these, only $a\equiv 7\pmod{12}$ and $a\equiv 11\pmod{12}$ are prime to $12$. One possibility is $y\equiv 7x + 3$ (when $a=7$), and another is $y=11x-1$ (when $a=11$); both are compatible with the two given points.

If you are given another point, it may, again, suffice or not. For instance, if you get another point $(x_3,y_3)$ with $\gcd(12,x_3-x_2) = \gcd(12,x_3-x_1)=3$, say $(7,4)$, this point is likewise compatible with both of the possibilities above. And also $(10,1)$; but one more point beyond this will suffice to uniquely determine $a$ (since there will be no other point with $x$ coordinate that can drop you into the "bad" case). So if your first two points have $\gcd(n,x_1-x_2)=d\gt 1$, then you may need as many as $\frac{n}{d}-1$ additional points.

In particular, if $n$ is not a prime and $p$ is the smallest prime that divides $n$, it's possible to be given $\frac{n}{p}$ distinct points and not have them uniquely determine the values of $a$ and $b$.

share|improve this answer
add comment

Two. If $y_1\equiv ax_1+b\pmod n$ and $y_2\equiv ax_2+b\pmod n$ then $y_1-y_2\equiv a(x_1-x_2)\pmod n$, which you can solve for $a$, provided $\gcd(x_1-x_2,n)=1$. And once you have $a$, you have $b$.

share|improve this answer
add comment

You would be needing 2 pairs of (x,y) satisfying the given equation

when u know both y,n u will know the remainder obviously

now, the remainder is ax+b out of which we even have x which essentially leaves us with a equation in 2 unknowns a,b

so another (x,y) will solve the problem here of finding a,b

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.