Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
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}$$

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
Can you divide both the left hand side and the right hand side? – Penny Loren Oct 27 '12 at 22:45

Your Answer


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.