Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
When you change $-4$ in $13$, this also changes the values of $k$ (so the $k$ you computed for $-4$ will not work for $13$). If you take $x = -4 + 17 \times 133$ (or $-4+17 \times 18$), it works. –  Joel Cohen Oct 6 '11 at 22:09
1  
Why did you all of a sudden change the $-4$ (third line) to $13$ (fourth line)? –  André Nicolas Oct 6 '11 at 22:11
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
Didn't notice I changed. Thanks. Ugh, you won't believe how much time I wasted trying to find where I had a typo. –  iDontKnowBetter Oct 6 '11 at 22:21
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.