1

I have a general question about modular equations:

Let's say I have this simple equation:

$$ax\equiv b \pmod{337}$$

I need to solve the equation.

What does "solve the equation" mean? There are an infinite number of $x$'s that will be correct.

Does $x$ need to be integer?

Thanks very much in advance,

Yaron.

Lord_Farin
  • 17,743
user76508
  • 746
  • I observe that many of your questions have a very vague title. Please, try to make the title of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. – Lord_Farin May 30 '13 at 11:00

2 Answers2

1

Write $p = 337$. This is a prime number.

First of all, if $a \equiv 0 \pmod{p}$ then there is a solution if and only if $b \equiv 0 \pmod{p}$, and then all integers $x$ are a solution.

If $a \not\equiv 0 \pmod{p}$, then the (infinite number of integer) solutions will form a congruence class modulo $p$. These can be found using Euclid's algorithm to find an inverse of $a$ modulo $p$, very much as you would do over the real numbers, say.

That is, use Euclid to find $u, v \in \Bbb{Z}$ such that $a u + p v = 1$, and then note that $x_{0} = u b$ is a solution, as $a x_{0} = a u b = b - p v b \equiv b \pmod{p}$. (Here $u$ is the inverse of $a$ modulo $p$, as $a u \equiv 1 \pmod{p}$.)

Then note that if $x$ is any solution, then $a (x - x_{0}) \equiv 0 \pmod{p}$, which happens if and only if $p \mid x - x_{0}$, so that $x \equiv x_{0} \pmod{p}$. Thus the set of solutions is the congruence class of $x_{0}$.

Andreas Caranti
  • 68,873
1

Typically this question means to find all the integer $x$ in the interval $[0,336]$ satisfying the equation.

vadim123
  • 82,796