Finding a number given its remainder when divided by other numbers

Question

I have this GRE question that I'd like to know how to solve. I want to solve it in as simple a way as possible, since it is GRE material. In particular, I don't want to use "congruences" or modulo arithmetic that I came across in other posts.

Here it is:

When the positive integer $n$ is divided by $3$ the remainder is $2$. When it is divided by $5$, the remainder is $1$. What is the least possible value of $n$?

Here's my effort: $$n=3q_1+2\tag1$$ $$n=5q_2+1\tag1$$

Great! I now have 2 equations and 3 unknowns. Can someone help me out please? Thanks. (I can imagine going through all positive integers and plugging them in to find the appropriate integer, but that seems rather trivial and inelegant. Is there another way?)

Answer 1

The Chinese remainder theorem is the key tool to solve this sort of problem, though given that this question is being asked in a timed test situation, and the numbers involved are quite small, I would highly recommend the "inelegant" approach, as it will be faster.

Answer 2

List the numbers that give remainder $1$ on division by $5$, looking for remainder $2$ on division by $3$. Start listing: $1$, $6$, $11$. Bingo!

Remark: This is probably the quickest way to solve the GRE problem. An alternative is to list the numbers that leave remainder $2$ on division by $3$, and look for remainder $1$ on division by $5$. That is a little slower: things increase faster if we count by $5$'s than if we count by $3$'s.

As to elegance, that requires thinking, and the GRE is not about that. On to the next question.

Answer 3

$n+4$ is divisible by $3$ and $5$. So $15-4 = 11$.

Answer 4

This is solved by the Chinese Remainder Theorem. But you are on the right track: Equate both: $$ 3 q_1 + 2 = 5 q_2 + 1 $$ So you know $3 q_1 + 1 = 5 q_2$. Look for a pair satisfying this, like $q_1 = 3$ and $q_2 = 2$. This gives the pair $3 \cdot 3 + 2 = 11$ and $2 \cdot 5 + 1 = 11$. Other solutions are $11 + 3 \cdot 5 \cdot k = 11 + 15 k$.

Answer 5

It's quite simple: test which of $\rm\:n = 5q\!+\!1 = 1,6,11\:$ has the desired remainder when divided by $3$. Since the remainders mod $\,3\,$ are $\rm\,1\to 1,\ 6\to 0,\ 11\to 2,\,$ it is $11$ with sought remainder $=2.$

The same quick test works if we replace $\,5\,$ by any $\rm\:m\:$ not divisible by $3.\,$ To find $\rm\:n\:$ such that $\rm\:3q+r = n = m\,j+k,\:$ test which of $\rm\: k,\, k\!+\!m,\, k\!+\!2m\:$ has remainder $\rm\:r\:$ when divided by $3$.

More generally, the same will work for any two coprime divisors (moduli), but you will need to generate a test sequence of $\rm\:d\:$ values, where $\rm\:d\:$ is the least divisor (modulus). The theory behind this is explained by the Chinese Remainder Theorem.