0
$\begingroup$

Trying to find $x \equiv_{17} -4$, $x \equiv_{23} 3$.

OK, so $x = -4 + 17k$ for some $k$.

$-4 + 17k \equiv_{23} 3$. Since $19$ is the inverse of $17 \pmod {23}$, $k \equiv_{23} (3+4)19 \equiv 133$.

Plugging those in: $x = 13 + 17(133) = 2274$.

Now, $2274 \equiv_{17} -4$, but for $\bmod 23$, I have to make it negative $-2274 \equiv_{23} 3$, otherwise it's $20$.

What did I do wrong?

  • 1
    Why did you all of a sudden change the $-4$ (third line) to $13$ (fourth line)?2011-10-06

2 Answers 2

5

You have defined $k$ by $x=-4+17k$, but later you find $x$ using $x=13+17k$. So of course your $x$ is $17$ bigger than it should be.

You could also have made things simpler for yourself: you have $k\equiv_{23} 133$, and so $k \equiv_{23} 18$. This gives the smaller solution $x=-4+17\cdot18=302$, which is the smallest positive solution.

  • 0
    Didn't notice I changed. Thanks. Ugh, you won't believe how much time I wasted trying to find where I had a typo.2011-10-06
2

HINT $\ $ Your inference $\rm\:mod\ 23:\ x\: \equiv\: -4 + 17\ k\: \equiv\: 3\ \Rightarrow\ k\: \equiv\: 133\ $ is correct, but your next inference is not; viz. $\rm\ y = x+17 = 13 + 17\ k\: \equiv\: x\pmod{17}\:,\:$ but $\rm\:y = x+17\:\not\equiv\: x\pmod{23}\:.\:$

NOTE $\ $ The solution can be more quickly calculated by mental arithmetic as follows

$\rm\displaystyle\ mod\ 23\!:\ -4 + 17\ k\ \equiv\ 3\ \ \Rightarrow\ \ k\ \equiv\ \frac{7}{17}\ \equiv\: -\frac{7}6\ \equiv\: -1-\frac{1}6\ \equiv\: -1-\frac{24}6\ \equiv\: -5\:$

Therefore $\rm\ \ x\ \equiv\: -4 +17\ (-5)\: \equiv\: -89\ \equiv\ 302\ \pmod{17\cdot 23}$