[Math] Finding a number given its remainder when divided by other numbers

arithmeticgre-exam

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?)

Best Answer

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.

Related Question