15
$\begingroup$

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.

$\endgroup$
35
+50
$\begingroup$

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$.

$\endgroup$
  • 3
    $\begingroup$ Very interesting approach... $\endgroup$ – imranfat Sep 28 '16 at 23:39
  • 3
    $\begingroup$ Nice approach, and one which lends itself to generalization. $\endgroup$ – Semiclassical Sep 28 '16 at 23:42
  • $\begingroup$ thanks this turns out be surprise easy $\endgroup$ – locke5 Sep 28 '16 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 Sep 29 '16 at 3:10
10
$\begingroup$

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$!

$\endgroup$
5
$\begingroup$

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\}$.

$\endgroup$
5
$\begingroup$

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$$

$\endgroup$
  • 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$ – Semiclassical Sep 29 '16 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 Sep 29 '16 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 Sep 29 '16 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 Sep 29 '16 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 Sep 29 '16 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.