Let $\frac{x}{y}=1+\frac12 +\frac13 +\cdots +\frac1{96}$ where $\text{gcd}(x,y)=1$. Show that $97\;|\;x$.

I try adding these together, but seems very long boring and don't think it is the right way to solving. Sorry for bad english.


4 Answers 4


If you group the fractions in pairs with the first pairing to last, second pairing to next-to-last, etc, you get $$1+\frac 1{96}=\frac {97}{96}, \frac 12+\frac 1{95}=\frac {97}{190}...$$ The sums of these pairs all have a numerator of $97$, and because $97$ is prime the common denominator will not have a factor of $97$, so in $\frac xy$, $x$ is a multiple of $97$.

  • 4
    $\begingroup$ Very interesting approach... $\endgroup$
    – imranfat
    Commented Sep 28, 2016 at 23:39
  • 3
    $\begingroup$ Nice approach, and one which lends itself to generalization. $\endgroup$ Commented Sep 28, 2016 at 23:42
  • $\begingroup$ thanks this turns out be surprise easy $\endgroup$
    – locke5
    Commented Sep 28, 2016 at 23:43
  • $\begingroup$ I found it interesting how both of our solutions ended up with $\frac{p(p-1)}2$, but the way we reordered the sum is completely different. $\endgroup$
    – DanielV
    Commented Sep 29, 2016 at 3:10

What we need to do is as follows: $$ \begin{equation}\begin{split} 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{96} & = \Big(1+\frac{1}{96}\Big) + \Big(\frac{1}{2}+\frac{1}{95}\Big) + \ldots + \Big(\frac{1}{48} + \frac{1}{49}\Big) \\ & = \frac{97}{96} + \frac{97}{2*95} + \frac{97}{3*94} + \ldots + \frac{97}{48*49} \\ & = 97 \Big( \frac{1}{96} + \frac{1}{2*95} + \frac{1}{3*94} + \ldots + \frac{1}{48*49}\Big) \end{split}\end{equation} $$

Hence, the numerator is a multiple of $97$. To see that the denominator is not a multiple of $97$, note that $97$ is a prime, and the denominator contains natural numbers less than $97$ (in fact, the reduced denominator is a factor of $96$!), hence cannot possibly be a multiple of $97$. Thus, in it's reduced form, the numerator of the expression is a multiple of $97$.

In fact, Wolstenhomme's theorem says that the numerator is a multiple of $97^2 = 9409$!

  • 1
    $\begingroup$ I like that you mentioned Wolstenholme's theorem. $\endgroup$ Commented Sep 28, 2016 at 23:43
  • 1
    $\begingroup$ Thank you, @SangchulLee. It was natural in the context, and is a highly non-trivial fact. $\endgroup$ Commented Sep 28, 2016 at 23:44

This is along the lines of DanielV's proposed solution.

We know $97$ is prime. Multiplying both sides by $96!$, it's enough to show that $\sum_{n=1}^{96} \frac{96!}{n}$ (which is a sum of integers) is divisible by $97$, because $96!$ and $97$ are coprime. Let $a_n = \frac{96!}{n}$ for $n\in\{1,\ldots,96\}$. Then we have $n a_n = 96!$, so $a_n \equiv 96! n^{-1} \pmod {97}$, where $n^{-1}$ is the inverse of $n$ in the integers mod $97$. Then $\sum_{n=1}^{96} a_n$ is divisible by $97$ because $$ \sum_{n=1}^{96} a_n \equiv 96! \sum_{n=1}^{96} n^{-1} \color{red}{=} 96! \sum_{n=1}^{96} n = 96! \frac{96 \cdot 97}{2} \equiv 0 \pmod{97}.$$ The red $\color{red}{=}$ holds because the inverse $n \mapsto n^{-1}$ is a permutation of $\{1,\ldots,96\}$.


If you know that 97 is prime, and that every nonzero value has a multiplicative inverse mod a prime value, and that modular inverse is a bijection due to it being an involution, then you get:

$$\sum_{k = 1}^{96} k^{-1} \equiv \sum_{j = 1}^{96} j \pmod {97}$$

And the result follows from arithmetic sum.

More explicitly, letting $p = 97$,

$p \not | y$ because $y | (p - 1)!$ and $p$ is prime and $(x,y)$ are in reduced terms. Therefore:

$xy^{-1} \equiv 0 \pmod p$ iff $x \equiv 0 \pmod p$ implies the numerator of $\frac{x}{y}$ is divisible by $p$.

Since $\frac{x}{y} = \sum_{k=1}^p k^{-1}$, follows that

$$p | x \text{ iff } \sum_{k = 1}^{p-1} k^{-1} \equiv 0 \pmod p$$

Let $S_n \equiv n^{-1} \pmod p$ with $n$ ranging from $1$ to $p-1$. Then $S$ is a bijection, so

$$\sum_{n = 1}^{p-1} S_n \equiv \sum_{n = 1}^{p-1} n \pmod {p}$$

And the result follows from

$$p(p-1)/2 \equiv 0 \pmod p$$

  • 1
    $\begingroup$ You seem to be interpreting $n^{-1}$ as the modular inverse. That's not a reasonable interpretation of the question, since the questioner explicitly indicates that the sum should be a rational number not an integer. $\endgroup$ Commented Sep 29, 2016 at 0:04
  • 1
    $\begingroup$ @DanielV The idea is right of course, but in order to formalize the proof you need to link the sum of inverses $\pmod p$ with the sum of inverses in $\mathbb{Q}$. That would require at least knowing/proving that the inverses $\pmod p$ are all distinct and that $(p-1)! \equiv -1 \pmod p$, then working out $96! \frac{x}{y}$. $\endgroup$
    – dxiv
    Commented Sep 29, 2016 at 0:05
  • 1
    $\begingroup$ Sure, but I don't see how that extends to a sum of fractions. It seems to me that to apply that you'd need to put everything over a common denominator. $\endgroup$
    – arkeet
    Commented Sep 29, 2016 at 0:13
  • 1
    $\begingroup$ @DanielV Paraphrasing your argument for one single value $2^{-1} \equiv 49 \pmod{97}$ so the numerator of $\frac{1}{2}$ should be divisible by $49$ which is obviously not true. You can prove that your answer does in fact translate to rational numbers, but it doesn't just follow without elaborating. $\endgroup$
    – dxiv
    Commented Sep 29, 2016 at 0:18
  • 2
    $\begingroup$ @DanielV I am not at all disagreeing with that fact. It's just not obvious that a fact about the sum $\sum_n a_n^{-1}$ in the field $\mathbb{F}_{97}$ translates to a similar fact in $\mathbb{Q}$. $\endgroup$
    – arkeet
    Commented Sep 29, 2016 at 0:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .