0
$\begingroup$

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?

4 Answers 4

2

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.

  • 0
    but is that an integer solution?2012-10-27
  • 0
    Don't you mean, when you divide through by 3, that we need to solve for $x\equiv 1\pmod{19}$?2012-10-27
  • 0
    Ok so basically we take the first expression and then add the value of x(mod y)?2012-10-27
  • 0
    @amWhy: I certainly do; I’m making more than my share of careless typos today. Thanks.2012-10-27
  • 0
    @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$.2012-10-27
  • 0
    So, in this case 1+19n? I thought it would be 3n+3. I am totally confused.2012-10-27
  • 0
    @Penny: Yep, as in my corrected answer above.2012-10-27
  • 0
    3x = 3(1+19) ahhh2012-10-27
1

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

0

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

0

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

  • 0
    Can you divide both the left hand side and the right hand side?2012-10-27