Harmonic Number (Starting from an AMC problem) (1)

January 2025
M	T	W	T	F	S	S
	1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

The $n$ -th Harmonic number, denoted $H_n$ is defined by the sum of the reciprocals of the first $n$ natural numbers:

$H_n = \sum_{k=1}^n \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$

This number has quite interesting properties. On thing we could consider when $n$ is finite is the quotient of the sum. If we write it as

$H_n = \sum_{k=1}^n \frac{1}{k} = \frac{u_n}{v_n}, \quad (u_n, v_n)=1, \quad v_n>0$

Then many problems raise. Here, we have a problem concerning when is the denominator the lcm of $1,2,\dots n$ .

2022 AMC 12A Problem 23

Let $h_n$ and $k_n$ be the unique relatively prime positive integers such that

$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\frac{h_n}{k_n}.$

Let $L_n$ denote the least common multiple of the numbers $1, 2, 3, \ldots, n$ . For how many integers with $1\le{n}\le{22}$ is $k_n<L_n$ ?
$\textbf{(A) }0 \qquad\textbf{(B) }3 \qquad\textbf{(C) }7 \qquad\textbf{(D) }8\qquad\textbf{(E) }10$

The solution would be straightforward. For $p_i$ in the prime factorization of $L_n$ , consider quotients of the form $\dfrac{1}{kp_i^l}$ , where $l=\lfloor\log_{p_i} n\rfloor$ , $k\in\{1,2,\dots \lfloor\dfrac{n}{p_i^l}\rfloor\}$ . Sum then up and find when does the denominator of the sum is divisible by $p_i^{l}$ .

This interesting problem prompts us to relate a prime $p$ with this fraction. Now let’s introduce a result of it.

Theorem 1 If $p>3$ , then

$1+\frac{1}{2}+\dots + \frac{1}{p-1}\equiv 0 \pmod p^2$

That is, the numerator is always divisible by $p^2$ .

Proof. For $1\leq i\leq p-1$ ,

$\frac{1}{i}+\frac{1}{p-i}=\frac{p}{i(p-i)}\equiv 0\pmod p$

Thus, we must have

$1+\frac{1}{2}+\dots + \frac{1}{p-1}\equiv 0 \pmod p$

Consider the product

$(p-1)!\left(1+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{p-1}\right)$

It has the same equivalence relation with respect to the original one since $p\nmid (p-1)!$ . It remains to prove that

$(p-1)!\left(1+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{p-1}\right)\equiv 0 \pmod {p^2}$

Consider the identity

$(p-1)! = p^{p-1}-A_1p^{p-2}+\dots -A_{p-2}p+A_{p-1}$

where $A_{k}=\sum_{1 \leq i_1 < i_2 < \dots < i_k \leq p-1} i_1i_2 \dots i_m$ .

We have $A_{p-1}=(p-1!)$ and $A_{p-2}=(p-1)!\left(1+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{p-1}\right)$

From the identity, we can also deduce that

$kA_k=\binom{p}{k+1}+\binom{p-1}{k}A_1+\dots +\binom{p-k+1}{2}A_{k-1}$

Hence $p\mid A_k$ for $1\leq k\leq p-3$ . It follows that $p^2\mid A_{p-2}$ .

$J(p)$ and $I(p)$

Eswarathasan, Arulappah, and Eugene Levine. “p-Integral Harmonic Sums.” Discrete Mathematics, vol. 91, no. 3, Sept. 1991, pp. 249–57. https://doi.org/10.1016/0012-365x(90)90234-9.

Harmonic Number (Starting from an AMC problem) (1)

Leave a Reply Cancel reply