# Without Chinese Remainder Theorem

I was helping a young lady study for the (general) GRE. She was using some study guide she had bought. The math sections are divided into "Arithmetic", "Algebra", "Geometry", "Data Analysis." The Arithmetic sections is pre-high school stuff: Simplify exponents, calculate percents, and such.

At the end of the arithmetic section, was a problem: When a positive integer $n$ is divided by $3$ the remainder is $2.$ When it is divided by $5$, the remainder is $1$. Find the smallest possible value of $n$.

I couldn't come up with a good way for her to work the problem. At this level, she wouldn't put division in the shape of the Division Algorithm, so it took some explaining just to get to "Well, $n =3k+2$ for some $k$."

With the two facts $n=3k+2$ and $n=5m+1$, the best I could do was have her write down some terms of both progressions and discover that $11$ was common to both.

So my question is: Is there some technique from pre-algebra (why is that a thing?) that students typically learn which would help them with this problem? Or is it typical of the GRE to ask a question where the student would have to reason as we did (that is, just listing a few terms)? Or is the study guide just whacked?

• Trial and error on the sequence $6,11,16,21,\ldots$ is probably just as fast as any theoretical approach. – Arthur May 6 '18 at 11:18
• Did you mean that the remainder on division by $3$ was $1$? $11$ is not a possible remainder on division by $3$. – lulu May 6 '18 at 11:19
• Assuming you meant $1$, just use trial and error. just try the integers $\{6,11,16,\cdots\}$ until you find one of the form $3n+1$. – lulu May 6 '18 at 11:20
• @lulu Edited. Thanks. – B. Goddard May 6 '18 at 11:21
• No problem. Trial and error is still the best method, by far. If you want an alternative, to solve $5n+1\equiv 2\pmod 3$ note that $5\equiv -1\pmod 3$ so it is the same as $n\equiv -1\equiv 2 \pmod 3$. – lulu May 6 '18 at 11:25

Another way (not sure if simpler than listing) is to express it as a fraction: $$k=\frac{n-2}{3}; m=\frac{n-1}{5} \Rightarrow k-m=\frac{2n-7}{15}=\frac{2n+8-15}{15}=\frac{2(n+4)}{15}-1.$$ The smallest positive $n=11$.

• Thanks for reading the question. I had thought of something like this, but I'm surprised it worked without more acrobatics. – B. Goddard May 7 '18 at 0:02
• You are welcome. I assume the question was designed that way. Acrobatics will be when it requires to solve diophantine equation. – farruhota May 7 '18 at 4:51

Calculate backwards:

Dividing by $3$ means subtracting $3$ from $n$ as much as you can until you can subtract it any more, i.e. when you obtain a number less than $3$. So the next to last step, you obtained $2+3$, the step before, $2+3+3$, and so on.

Therefore the smallest $n$ which satisfies these conditions is the first number in the sequence $\;(2, \,2+3,\,2+3+3,\,…)$ which $1$ more than a multiple of $2$.

Alternatively, you write simultaneously the sequences \begin{align} &2, \,2+3=5,\,2+3+3=8,\,…\\ &1,\,1+5=6,\,1+5+5=11,\,… \end{align} until you find a common term.

The answer must work for 3n+2 and 5m+1, not 3n+1 as inferred in two of the comments.

3*1+2=5, 5*1+1=6;

3*2+2=8, 5*2+1=11;

3*3+2=11

So, 11 is the smallest answer. The multiplier for 3 and 5 does not have to be the same.