1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Lord_Farin May 30 '13 at 11:00
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I understand why the x has to be integer, but why does it need to be in the interval $[0,336]$ ? $\endgroup$ – user76508 May 8 '13 at 13:43
  • 1
    $\begingroup$ Because that is the most commonly used complete residue system. $\endgroup$ – vadim123 May 8 '13 at 13:45
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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