# Determine a linear modulo function's parameters

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

-
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

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

-

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

-

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

-