# Find all integer solution for 3x = 22 mod 19

Ok, just to make sure I understood this correctly.

$22 \mod 19 = 3$

\begin{align} 2\times19&=38+3 = 41 \\ 3\times19&=57+3 = 60 \\ 4\times19&=76+3 = 79 \\ 5\times19&=95+3 = 98 \end{align}

\begin{align} 41/3 &= \mbox{not an integer} \\ 60/3 &= 20 \\ 79/3 &= \mbox{not an integer} \\ 98/3 &= \mbox{not an integer} \end{align}

How can I find all of them?

-

As you say, $22\bmod 19=3$, so the problem is equivalent to solving $3x\equiv 3\pmod{19}$. $3$ is relatively prime to $19$, so you can divide through by it and simply solve $x\equiv 1\pmod{19}$. By definition $x\equiv 1\pmod{19}$ if and only if $19\mid x-1$, i.e., if and only if there is an integer $n$ such that $x-1=19n$. The solutions are therefore the numbers of the form $19n+1$, where $n$ is any integer.

-
but is that an integer solution? –  Penny Loren Oct 27 '12 at 22:21
Don't you mean, when you divide through by 3, that we need to solve for $x\equiv 1\pmod{19}$? –  amWhy Oct 27 '12 at 22:33
Ok so basically we take the first expression and then add the value of x(mod y)? –  Penny Loren Oct 27 '12 at 22:35
@amWhy: I certainly do; I’m making more than my share of careless typos today. Thanks. –  Brian M. Scott Oct 27 '12 at 22:35
@Penny: First let me correct my previous list: that should be $$\{\dots,-56,-37,-18,1,20,39,58,\dots\}$$ Once you know one integer solution to $x\equiv1\pmod{19}$, you can get all the rest by adding and subtracting multiples of $19$. –  Brian M. Scott Oct 27 '12 at 22:37

$$3x\equiv 22\pmod{19}\iff 3x\equiv 3\pmod{19}\Rightarrow x\equiv 1\pmod{19}$$

-

$$3x \equiv 22 \pmod {19} \equiv 3 \pmod{19} \implies x \equiv 1 \pmod{19}$$

-

I assume its about this congruence $3x\equiv 22 \pmod{19}$. then, it's already done by the observation that $22\equiv 3 \pmod{19}$ and that $19$ and $3$ are relatively primes.

So, we get $3x\equiv 3 \pmod{19}$ and the answer is $x\equiv 1\pmod{19}$.

-
Can you divide both the left hand side and the right hand side? –  Penny Loren Oct 27 '12 at 22:45