Consider
$$\sum_{k=1}^{1992}\frac{1}{k}=\frac{a}{b}.$$
If $a$ and $b$ are natural numbers that are relatively prime, what is the remainder when dividing $a$ by $5$?
$\text{(A) } 0 \space\space\space\space\space \text{(B) } 1 \space\space\space\space\space \text{(C) } 2 \space\space\space\space\space \text{(D) } 3 \space\space\space\space\space \text{(E) } 4$
My Attempt:
Consider
$$S_n=\sum_{k=1}^{n}\frac{1}{k}=\frac{a}{b}$$
When $n=2$, $S_2=\frac{1}{1}+\frac{1}{2}=\frac{3}{2} \implies 3 \equiv 3 (\bmod 5)$
When $n=3$, $S_3=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}=\frac{11}{6} \implies 11 \equiv 1 (\bmod 5)$
When $n=4$, $S_4=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{25}{12} \implies 25 \equiv 0 (\bmod 5)$
When $n=5$, $S_5=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}=\frac{137}{60} \implies 137 \equiv 2 (\bmod 5)$
When $n=6$, $S_6=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}=\frac{49}{20} \implies 49 \equiv 4 (\bmod 5)$
When $n=7$, $S_7=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}=\frac{363}{140} \implies 363 \equiv 3 (\bmod 5)$
From the last calculation, for $S_7$, I thought, with doubt, assume that if $n$ is of the form $5k+2$,$5k+3$,$5k+4$,$5k+5$, or $5k+6$, then it will give remainder $3,1,0,2,4$, respectively, when divided by $5$.
The value of $n$ we have is $1992$, which can be expressed as $5 \times 398+2$. Hence the numerator is congruent to $3$ when divided by $5$, that is option $\text{D}$.
With the help of WA, it showed that the last digit of the numerator is $9$, therefore the answer should be $\text{E}$. However, calculators are not allowed in the test.
The calculations in my approach are tedious, especially when $n=5$ and higher. In the end resulted a wrong answer. So either I had a mistake in the calculations, or the method itself is wrong.
How can we answer this question as fast as possible, since this problem appears in a timed exam?
Your help would be appreciated. THANKS!
Let $S=S_{1992}=\frac ab$ be the given rational number, written as an irreducible fraction. The only way to proceed is to find $b$ exactly first. (I could not see any Wolstenholme-type theorems that can be applied.) So let us exhibit $b$.
A common denominator of all involved fractions, maybe not the minimal one, is: $$ B = 2^{10}\cdot 3^7\cdot 5^4\cdot 7^3\cdot 11^3\cdot 13^2\cdot 17^2\cdot 19^2\cdot 23^2\cdot 29^2\cdot 31^2\cdot 37^2\cdot 41^2\cdot 43^2 \cdot \Pi \ , $$ where $\Pi$ is the product of all primes from $47$ to $1987$. Then we maximally simplify the fraction $A/B$ to get $a/b$.
(Not having the right $b$ would introduce a factor between $1$ and $A/a$, and the answer may jump.)
For each prime below $1992$ we took its highest power still less than $1992$ in the product. So there is some $A$ with $$S=\frac AB\ . $$ Now the next question is if there are any simplifications with any prime $p$ from $2$ to $1987$ in $\frac AB$. Well, how can it be that some prime number is dividing $A$? It can be! OP has already computed some harmonic numbers, and note that in $S_6,S_7$ there is no factor $3$ in the denominator. Let us collect all primes $p$ that may divide both $A$ and $B$. Such a prime $p$ is among the prime number in the above factorization of $B$, so it is one of $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,\dots,1979, 1987$, just to have them clearly written down. Fix such a $p$, and let $\nu(p,B)$ be the power it has in the factorization of $B$. For example $\nu(2,B)=10$, $\nu(3,B)=6$, and so on. Then $$ \frac A{B/p^{\nu(p,B)}} =\sum_{1\le k\le 1992}\frac{p^{\nu(p,B)}}k \ . $$ The last relation makes also sense in the field with $p$ elements $\Bbb F_p=\Bbb Z/p$, if on the R.H.S. we first simplify with the maximal $p$-power in any fraction, so let us write this in the form $$ A\sim \sum_{1\le k\le 1992}\Bbb F_p\left(\frac{p^{\nu(p,B)}}k\right) \ . $$ and $A$ modulo $p$ vanishes iff the R.H.S. vanishes in $\Bbb F_p=\Bbb Z/p$. We have denoted by $\sim$ an equality up to some non-zero factor. Doing so, we have explicitly for the first few primes: $$ \begin{aligned} A&\sim \sum_{1\le k\le 1992}\Bbb F_2\left(\frac {2^{10}}k\right)\equiv\frac {1024}{1024}=1 &&\text{ in } \Bbb Z/2\ , \\ A&\sim \sum_{1\le k\le 1992}\Bbb F_3\left(\frac {3^6}k\right)\equiv \Bbb F_3\left(\frac {729}{729}+ \frac {729}{2\cdot 729}\right) \equiv 1+2\equiv 0 &&\text{ in } \Bbb Z/3\ , \\ A&\sim \sum_{1\le k\le 1992}\Bbb F_5\left(\frac {5^4}k\right)\equiv \Bbb F_5 \left(\frac {625}{625}+\frac {625}{2\cdot 625}+\frac {625}{3\cdot 625}\right) \equiv 1+3+2\equiv 1 &&\text{ in } \Bbb Z/5\ ,\\ A&\sim \sum_{1\le k\le 1992}\Bbb F_7\left(\frac {7^3}k\right)\equiv \Bbb F_7 \left(\frac {343}{343} +\frac {343}{2\cdot 343} +\frac {343}{3\cdot 343} +\frac {343}{4\cdot 343} +\frac {343}{5\cdot 343} \right) \\ & \equiv 1+4+5+2+3\equiv 1 &&\text{ in } \Bbb Z/7\ , \end{aligned} $$ and so on. In general: $$ A\sim \sum_{1\le k\le 1992}\Bbb F_p\left(\frac {p^{\nu(p,B)}}k\right) = \sum_{\substack{ 1\le n\le [1992/p^{\nu(p,B)}]\\ k=np^{\nu(p,B)}}} \Bbb F_p\left(\frac 1n\right) \qquad\text{ in }\Bbb Z/p\ . $$ As long as we have a higher power, there are not too many terms to be considered, and the computations can be done with only few terms, let us record them all to see that it is in worse a brute force computation to be liquidated in some minutes in an exam: $$ \begin{aligned} A&\sim \sum_{1\le n\le [1992/1331]}\frac 1n =\frac 11\equiv 1&&\text{ in } \Bbb Z/11\ , \\ A&\sim \sum_{1\le n\le [1992/169]}\frac 1n =\frac 11+\frac 12 +\dots+\frac 1{11}\equiv -\frac 1{12}\equiv1&&\text{ in } \Bbb Z/13\ , \\ A&\sim \sum_{1\le n\le [1992/289]}\frac 1n =\frac 11+\frac 12+\frac 13+\frac 14+\frac 15+\frac 16 \\ &\equiv 1+ 9 + 6+(-4)+(-7)+3 \equiv8&&\text{ in } \Bbb Z/17\ , \\ A&\sim \sum_{1\le n\le [1992/361]}\frac 1n =\frac 11+\frac 12+\frac 13+\frac 14+\frac 15 \\ &\equiv 1+ 10 + (-6)+ 5+4 \equiv-5&&\text{ in } \Bbb Z/19\ , \\ A&\sim \sum_{1\le n\le [1992/23^2]}\frac 1n =\frac 11+\frac 12+\frac 13 \equiv 1+ 12 + 8 \equiv-2&&\text{ in } \Bbb Z/23\ , \\ A&\sim \sum_{1\le n\le [1992/29^2]}\frac 1n =\frac 11+\frac 12 \equiv 1+ 15 \equiv16&&\text{ in } \Bbb Z/29\ , \\ A&\sim \sum_{1\le n\le [1992/31^2]}\frac 1n =\frac 11+\frac 12 \equiv 1+ 16 \equiv17&&\text{ in } \Bbb Z/31\ , \\ A&\sim \sum_{1\le n\le [1992/p^2]}\frac 1n =\frac 11 \equiv 1 &&\text{ in } \Bbb Z/p\ , \\ \end{aligned} $$ where in the last line $p$ is among $37, 41,43$.
There remain a lot of other primes $p$ from $47$ to $1987$, which appear to a first power in $B$. For each of them we compute $1+\frac 12+\dots+\frac 1m$ for some $m$ modulo $p$. We can make the for many of them by looking at the first few harmonic numbers, $$ 1\ ,\ \frac{3}{2}\ ,\ \frac{11}{6}\ ,\ \frac{25}{12}\ ,\ \frac{137}{60}\ ,\ \frac{49}{20}\ ,\ \frac{363}{140}\ ,\ \frac{761}{280}\ ,\ \frac{7129}{2520}\ ,\ \frac{7381}{2520}\ ,\ \frac{83711}{27720}\ , \\ \frac{86021}{27720}\ ,\ \frac{1145993}{360360}\ ,\ \frac{1171733}{360360} \ ,\ \frac{1195757}{360360}\ ,\ \frac{2436559}{720720} \ . $$ Only the following primes show up so far in the numerators, $$ \begin{aligned} 1 &= 1\ ,\\ 3 &= 3\ ,\\ 11 &= 11\ ,\\ 25 &= 5^{2}\ ,\\ 137 &= \color{red}{137}\ ,\\ 49 &= 7^{2}\ ,\\ 363 &= 3 \cdot 11^{2}\ ,\\ 761 &= \color{red}{761}\ ,\\ 7129 &= 7129\ ,\\ 7381 &= 11^{2} \cdot 61\ ,\\ 83711 &= 97 \cdot \color{red}{863}\ ,\\ 86021 &= 13^{2} \cdot \color{red}{509}\ ,\\ 1145993 &= 29 \cdot 43 \cdot \color{red}{919}\ ,\\ 1171733 &= \color{red}{1049} \cdot \color{red}{1117}\ ,\\ 1195757 &= 29 \cdot 41233\ ,\\ 2436559 &= 17^{2} \cdot 8431\ ,\\ \end{aligned} $$ so we can already eliminate all $p\ge 1992/16=124.5\dots$ not in the above from those with a potential simplification. Also, when considering a prime $p$, note that $1+\frac 12+\dots+\frac 1p$ is zero modulo $p$ (since we have $1+2+\dots+(p-1)$ in an other order of the summands), so we can also argue as follows, here for $47$ explicitly in $\Bbb F_{47}=\Bbb ZZ/47$: $$ \frac 11+\frac 12+\dots+\frac 1{42} \equiv -\frac 1{43} -\frac 1{44} -\frac 1{45} -\frac 1{46} \equiv -\frac 1{-4} -\frac 1{-3} -\frac 1{-2} -\frac 1{-1} \ , $$ so we again land in one of the above sums. However, for the red numbers above and the remained primes $53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113$ the check is annoying for a human. (But easy for a computer. Well, the whole story is easy with a computer, so this is no argument.)
For the red numbers, it is a check that the corresponding harmonic sum is not on the place with the red number in charge. For $137$ we have to compute the $14$.th harmonic number, not the fifths. For the other red numbers, all $>500$ we have at most the fourth harmonic number to consider, but we are further down in the list with them.
For $53,\dots,113$ i do not have any quick human simplification here. For the forthcoming argument, it turns out that we can still ignore those primes which are one modulo five, so the check list is still: $$ 53, 59, 67, 73, 79, 83, 89, 97, 103, 107, 109, 113\ . $$ I will postpone this check. It turns out that $A$ is not zero modulo any of these primes.
So $A/B$ simplifies only with $3$. Is this power of $3$ the biggest one? (Or we may simplify with $9$?) Same argument, with computations done in the ring $R=\Bbb Z/9$, not a field, but the algebra is the same. Recall: $$ \frac A{B/729}=\sum_{1\le k\le 1992}\frac{729}k\ . $$ The fractions $729/k$ are integers, consider them as such first, then pass modulo $9$ to $R$, so it makes sense to compute with these numbers, and we write $R(729/k)$ for the corresponding element. The number $B/729$ is a unit in $R$, so $$ \begin{aligned} A &\sim \frac A{B/729} = \sum_{1\le k\le 1992}R\left(\frac{729}k\right) \equiv \sum_{\substack{1\le k\le 1992\\243\text{ divides }k}}R\left(\frac{729}k\right) \\ &= R\left(\frac{729}{243}\right) + R\left(\frac{729}{2\cdot 243}\right) + R\left(\frac{729}{3\cdot 243}\right) + R\left(\frac{729}{4\cdot 243}\right) + R\left(\frac{729}{5\cdot 243}\right) + R\left(\frac{729}{6\cdot 243}\right) + R\left(\frac{729}{7\cdot 243}\right) + R\left(\frac{729}{8\cdot 243}\right) \\ &=3+\frac 32+1+\frac 34+\frac 35+\frac 12+\frac 37+\frac 38\\ &=3+3\cdot 5+1+3\cdot7+3\cdot 2+5+3\cdot 4+3\cdot(-1)\\ &=3(1+5+7+2+4-1)+6=6\qquad\text{ in }R=\Bbb Z/9\ . \end{aligned} $$ So the exact denominator is $b=B/3$: $$ b= 2^{10}\cdot 3^{\color{red}5}\cdot 5^4\cdot 7^3\cdot 11^3\cdot 13^2\cdot 17^2\cdot 19^2\cdot 23^2\cdot 29^2\cdot 31^2\cdot 37^2\cdot 41^2\cdot 43^2 \cdot \Pi \ . $$ Below it is convenient to write $b=2\cdot 3\cdot 5^4\cdot b'$.
What is $a$ modulo five? We write the given sum for a convenient $c$ in the form $$ \frac ab=\frac 1{625}+\frac 1{2\cdot 625}+\frac 1{3\cdot 625} + \frac c{2\cdot 3\cdot 125 b'} = \frac{6b'+3b'+2b'+5c}{2\cdot 3\cdot 625 b'} = \frac{b'+5(2b'+c)}{b}\ . \ . $$ So $a$ is $b'$ modulo five: $$ a\equiv 2^{9}\cdot 3^4\cdot 7^3\cdot 11^3\cdot 13^2\cdot 17^2\cdot 19^2\cdot 23^2\cdot 29^2\cdot 31^2\cdot 37^2\cdot 41^2\cdot 43^2 \cdot \Pi \ . $$ I cannot see a human way to proceed.
Later EDIT: I will still say some words from the "programmer perspective", to illustrate the kind of question we have. Suppose we have a "small" number $N=700$ instead of the given $1992$, build the harmonic number$$H(N)=H(700)=\frac 11+\frac 12+\dots+\frac 1{699}+\frac 1{700}=\frac cd\ ,$$ with $c/d$ an irreducible fraction of two positive integers $c,d$, and ask for $c$ modulo five. The multiple choice Q&A style is now in this century also advancing in number theory, so that the corrector does not need to know the right number among $0,1,2,3,4$ (and the reason for it) and possibly ponder an answer like $-1$ instead, he or she needs to distinguish only between A,B,C,D,E. I was too often in the situation of Hussain, and this is the reason for exposing this answer. Well, it turns out that the prime $p=137<N=700$ does not show in the factorization of the denominator $d$. It is a relevant prime, since it is not one modulo five. In order to have the right letter among A,B,C,D,E, one has to investigate the primes up to $700$ one by one.
A note on the effort needed to solve this problem using computers, sage code:
So please, dear authors of exam problems, if such computational problems really need to test the talent of a mathematician in an exam, we will soon miss many talented mathematicians. And also, please learn to program, to see the difference in real life.