1
$\begingroup$

The question is:

Consider the following set of integers:

$$ S = \left\{x \left| 0 \le x < 280 ∧ x \equiv 3 \mod 7 ∧ x \equiv 4 \mod 8 \right. \right\}. $$

How many integers are there in S?

$0$? $1$? $2$? $5$? $10$? $280$?

  • It's a multiple choice answer with the correct answer of 5. I just can't seem to wrap around the idea.
$\endgroup$
  • $\begingroup$ On Math SE we prefer not having thanks sprinkled throughout a question, to keep questions tidy to save readers' time. Also, you should show what you have tried so that we can give appropriate guidance. $\endgroup$ – user21820 Aug 19 '15 at 14:53
1
$\begingroup$

$x \equiv 3 \pmod{7}$ is equivalent to $x+4 \equiv 0 \pmod{7}$.

$x \equiv 4 \pmod{8}$ is equivalent to $x+4 \equiv 0 \pmod{8}$.

Thus we want to know which numbers $x$ are such that $x+4$ is divisible by both $7$ and $8$. Since $7$ and $8$ are coprime, it would be exactly those numbers such that $x+4$ is divisible by $7 \times 8 = 56$. You can count easily now.

$\endgroup$
1
$\begingroup$

By the Chinese Remainder Theorem, the given system of congruences has a unique solution modulo $56$. (The solution happens to be $x\equiv -4\equiv 52\pmod{56}$, but we don't need to know that.)

Since $280=5\cdot 56$, the system of congruences has $5$ solutions modulo $280$. (They are $x\equiv 52+56k\pmod{280}$, where $k$ ranges from $0$ to $4$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.