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.

How would I solve for the following in general:

$(px + q)\equiv 0 \pmod r$

For example,

$ (2x + 1)=0 \pmod 7 $

$x = 3, 10, 17, 24, \ldots $

$(9y + 5)= 0 \pmod 3 $

$y$ has no solution.

I came up with the answers through intuition, but is there an actual proof or formula that can solve for the above?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

Your title is misleading: the % symbol is the modulus: it $(px + q) \mathbin{\%} r$ means the remainder after dividing $(px + q)$ by $r$. This can be expressed as equivalence modulo $r$.

E.g., your first equivalence reads:

$$2x + 1 \equiv 0 \pmod 7 \iff 2x \equiv -1 \pmod 7 $$ $$\iff 2x \equiv 6 \pmod 7 \iff x \equiv 3 \pmod 7$$

So indeed, $x \in \{..., -4, 3, 10, 17, 24, ...\}$


For your second question: $(9y + 5) \mathbin{\%} 3 = 0$, we are interested in the remainder of $9y + 5$ when divided by $3$, and testing whether this remainder can be equal to $0$: Note that $3$ divides $9y$ for all values of $y$, but $3$ does not divide $5$: so $3$ cannot divide $9y + 5$ evenly, so it cannot hold. That is,

$$9y + 5 \equiv 0 \pmod 3 \iff 9y \equiv -5 \pmod 3 $$ $$\iff 9y \equiv 1 \pmod 3$$ which, as you note, cannot hold because $9y\equiv 0 \pmod 3$, that is, $9y$ is divisible by 3, whatever the value of $y$, and so there cannot be a remainder of $1$.


Resources:

share|improve this answer
    
Thanks! Seems so obvious once you see the answer.. –  oliver Jan 25 '13 at 14:04
    
Edited the title to more accurately reflect the nature of the question. –  oliver Jan 25 '13 at 14:08
    
Your welcome! Thanks for the edit. –  amWhy Jan 25 '13 at 14:09
    
Thanks @Willie, for the edit: I totally missed the % problem! –  amWhy Jan 25 '13 at 14:11
    
+1 Nice and I agree with oliver at the first comment. –  B. S. Jan 25 '13 at 14:28
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.