Let $q = \frac{3p-5}{2}$ where $p$ is an odd prime, and let\[ S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q(q+1)(q+2)} \]Prove that if $\frac{1}{p}-2S_q = \frac{m}{n}$ for integers $m$ and $n$, then $m - n$ is divisible by $p$.
Problem
Source:
Tags: USA(J)MO, USAMO, partial fractions, 2010 USAMO, 2010 USAMO Problem 5, modular arithmetic, Hi
29.04.2010 16:56
29.04.2010 16:59
This is IMO 1979 Problem 1.
29.04.2010 16:59
29.04.2010 17:03
29.04.2010 20:07
30.04.2010 00:37
archimedes1 wrote: This is IMO 1979 Problem 1. No it's not. It's also not a generalization, and it also is not trivialized by IMO 1979 #1. Knowing the IMO 1979 #1 does make this USAMO problem substantially easier though.
30.04.2010 07:09
This is how I solved it: (may not be correct or worded properly though...) Suppose $S\sub{q}$ = $\frac{a}{b}$ where a and b are relatively prime. Then the expression $\frac{1}{p} - 2S\sub{q}$ becomes $\frac{1}{p} - \frac{2a}{b}$ = $\frac{b - 2ap}{pb}$. p divides $m - n$ only when p divides b. Therefore it suffices to show that p divides b. We know that $q = \frac{3p - 5}{2}$ so therefore $p = \frac{2q + 5}{3}$. The sum $\frac{1}{1*2*3} + \frac{1}{4*5*6} + ... + \frac {1}{(q)(q+1)(q+2)}$ can only contain p in the denominator once, since the ratio $\frac{q+2}{p}$ is less than two (it's easy to show using inequalities or limits, etc...). So when all the terms in $S\sub{q}$ are added, all the terms in the numerator, except the term originally divided by p, will be divisible by p. In other words, this is like saying we can write $S\sub{q}$ as $\frac{pm + k}{(q+2)!}$, where m and k are integers and p does not divide k. Therefore, in the simplification of $S\sub{q}$ will contain p in the denominator, which means that p divides b, and p divides m - n.
30.04.2010 18:27
To the above solution: You've basically proven that with what you have, p|m and p|n. But the point is you can now reduce by a factor of p (actually, two factors of p) to get a fraction in which this is no longer true. For example, in the fraction 3/6, p=3 divides 3-6, but if we were to write it as 1/2, 3 does not divide 1-2.
01.05.2010 03:46
ahh good point...I still know p must divide b but then the reduced version (i.e. $\frac{b}{p} - 2a - b$) would still have to divide p...crap...there goes a third of my usamo grade. :/
01.05.2010 09:15
hmm I got \[\displaystyle \frac{m-n}{n} = \sum_{i=\frac{p+1}{2}}^{p-1} \frac{1}{i} + \sum_{i=p+1}^{\frac{3p-1}{2}} \frac{1}{i} \] So multiply both sides by $\frac{(2p-1)!}{p}$, which has no factors of $p$ (and is 1 mod $p$) but makes the RHS an integer... so we can consider this stuff in $\mathbb{Z}/p\mathbb{Z}$ now, and can replace $\frac{1}{a}$ with $a^{-1} \pmod{p}$. Then we're done because the sum is the same as $\sum_{i=1}^{p-1} i^{-1} = \sum_{i=1}^{p-1} i$ by unique inverse, which is $0 \pmod{p}$.
01.05.2010 20:29
not_trig wrote: hmm I got \[\displaystyle \frac{m-n}{n} = \sum_{i=\frac{p+1}{2}}^{p-1} \frac{1}{i} + \sum_{i={p+1}^\frac{3p-1}{2} \frac{1}{i} }\] So multiply both sides by $\frac{(2p-1)!}{p}$, which has no factors of $p$ (and is 1 mod $p$) but makes the RHS an integer... so we can consider this stuff in $\mathbb{Z}/p\mathbb{Z}$ now, and can replace $\frac{1}{a}$ with $a^{-1} \pmod{p}$. Then we're done because the sum is the same as $\sum_{i=1}^{p-1} i^{-1} = \sum_{i=1}^{p-1} i$ by unique inverse, which is $0 \pmod{p}$. Note that $\sum_{i=\frac{p+1}{2}}^{p-1} \frac{1}{i} + \sum_{i={p+1}}^{\frac{3p-1}{2}} \frac{1}{i}=\sum_{i=1}^{(p-1)/2}\left(\frac{1}{p+i}+\frac{1}{p-i}\right)=\sum_{i=1}^{(p-1)/2}\frac{2p}{(p-i)(p+i)}$, which is how I avoided using inverses.
01.05.2010 20:40
That is also what I did in my solution above.
01.05.2010 22:52
math154 wrote: That is also what I did in my solution above. but that is not congruent to 0 mod p since you are maybe in the wrong field!
01.05.2010 23:02
Argh I got lazy when typing it up. In my actual write-up, I did what Yongyi did and took out the $p$ and said the denominators were relatively prime to $p$.
09.04.2014 00:06
05.04.2016 06:12
05.04.2016 07:14
13.04.2016 02:11
Wait darn, misread as $\frac{1}{2 \cdot 3 \cdot 4} + \frac{1}{3 \cdot 4 \cdot 5} + \cdots$ at first
14.04.2016 20:20
21.12.2016 05:54
Actually with Wolstenholme's theorem, we can prove a stronger result: for $p\ge 5$, $m-n$ is divisible by $p^2$. This is because $\dfrac{1}{1}+\dfrac{1}{2}+...+\dfrac{1}{p-1} \equiv 0 \bmod{p^2}$ for $p\ge 5$
09.04.2018 22:29
@above: What about the numerator? The first 2 terms of the sequence are 3,5 does 3,5 mean the first 2 odd primes or first 2 odd numbers? i.e. is the sequence 3,5,7,9,...,p or 3,5,7,11,...,p?
13.07.2019 00:41
17.03.2020 04:54
Let $H_n=\sum_{k=1}^n1/k$. It is not hard to see that \begin{align*} S_q&=\sum_{k=1}^{\frac12(p-1)}\frac1{3k(3k-1)(3k+1)}\\ &=\sum_{k=1}^{\frac12(p-1)}\left(\frac{1/2}{3k-1}-\frac1{3k}+\frac{1/2}{3k+1}\right)\\ &=\frac12\sum_{k=1}^{\frac12(p-1)}\left(\frac1{3k-1}+\frac1{3k}+\frac1{3k+1}\right)-\frac32\sum_{k=1}^{\frac12(p-1)}\frac1{3k}\\ &=\frac12\left(H_{\frac12(3p-1)}-H_{\frac12(p-1)}-1\right), \end{align*}whence \[\frac mn=\frac1p-2S_q=\frac1p-\left(H_{\frac12(3p-1)}-H_{\frac12(p-1)}-1\right)=1-\left(\sum_{k=\frac12(p+1)}^{\frac12(3p-1)}\frac1k\right)+\frac1p.\]Conveniently the $1/p$ cancels out, so taking everything modulo $p$, \[\frac mn\equiv 1-\sum_{k=1}^{p-1}\frac1k\equiv 1-\sum_{k=1}^{p-1}k\equiv 1\pmod p,\]i.e.\ $m-n\equiv 0\pmod p$, as desired.
30.06.2020 20:11
Observe the decomposition \[\frac{1}{n(n+1)(n+2)} = \frac{1}{2n}+\frac{1}{2(n+2)} - \frac{1}{n+1}.\]Hence, we have \[S_q = \frac{1}{2}\sum_{2\le n\le \frac{3p-1}{2},3\nmid n}\frac{1}{n} - \sum_{1\le n\le \frac{3p-3}{2},3\mid n}\frac{1}{n}.\]Rearranging yields \[2S_q - \frac1p + 1= \sum_{i=1,3\nmid i}^{p-1} \frac{1}{i}+\sum_{i=p+1,3\nmid i}^{q+2}\frac{1}{i} - 2\sum_{i=1}^{\frac{q+1}{3}}\frac{1}{3i}=\sum_{i=1}^{p-1} \frac{1}{i}+\sum_{i=p+1}^{q+2}\frac{1}{i} - 3\sum_{i=1}^{\frac{q+1}{3}}\frac{1}{3i}=\]\[\sum_{i=1}^{p-1} \frac{1}{i}+\sum_{i=p+1}^{q+2}\frac{1}{i} - \sum_{i=1}^{\frac{q+1}{3}}\frac{1}{i}.\]Now, take modulo $p$ to yield \[1-\frac{m}{n} \equiv \sum_{i=1}^{p-1} \frac{1}{i}+\sum_{i=p+1}^{q+2}\frac{1}{i} - \sum_{i=1}^{\frac{q+1}{3}}\frac{1}{i} \equiv \sum_{i=p+1}^{q+2}\frac{1}{i} - \sum_{i=1}^{\frac{q+1}{3}}\frac{1}{i} \equiv \sum_{i=p+1}^{\frac{q+1}{3}}\frac{1}{i} - \sum_{i=1}^{\frac{q+1}{3}}\frac{1}{i} \equiv 0\pmod{p},\]hence \[m\equiv n\pmod{p}\]and the conclusion follows.
17.07.2020 21:21
This should be right... Note that $$2S_q=\sum_{k=1}^{\frac{p-1}{2}}\frac{2}{(3k-1)(3k)(3k+1)}\implies 2S_q=\sum_{k=1}^{\frac{p-1}{2}}\frac{1}{3k-1}-\frac{2}{3k}+\frac{1}{3k+1}=\sum_{k=2}^{\frac{3p-1}{2}}\frac{1}{k}-\sum_{k=1}^{\frac{p-1}{2}}\frac{1}{k}=-1+\sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}}\frac{1}{k}$$Since there is only one fraction with denominator multiple of $p$ in the sum, after subtracting $\frac{1}{p}$ and expanding the denominator will not contain a factor of $p$. So it suffices to show that the unreduced fractional equivalent to $$-1+\frac{1}{\frac{p+1}{2}}+\frac{1}{\frac{p+1}{2}+1}+\dots +\frac{1}{p-1}+\frac{1}{p+1}+\dots+\frac{1}{\frac{3p-1}{2}}$$has sum of numerator and denominator divisible by $p$. But note that since there are exactly $\frac{3p-1}{2}-\frac{p+1}{2}+1-1=p-1$ values in the denominators, and these are consecutive (except for the exclusion of $p$), these must be the $p-1$ nonzero residues modulo $p$. So it's equivalent to compute the value $$-1+\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{p-1}$$By Wilson's Theorem, the denominator is $-1\pmod{p}$. The numerator of the sum $\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{p-1}$ will be $\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\dots$, but again Wilson's Theorem gives that the numerators are each $-1$. Since inverses are bijective, the sum $\frac{1}{1}+\dots +\frac{1}{p-1}$ is equivalent to $\frac{(p-1)(p)}{2}\equiv 0 \pmod p$. So the entire fraction (while keeping the denominator) is equivalent to $-1+\frac{0}{-1}$. Now, putting the $-1$ into the fraction gives the desired result.
25.07.2020 05:50
We have \begin{align*} 2S_q &= 2\sum_{x=1}^{\frac{q+1}{3}} \frac{1}{(3x-1)(3x)(3x+1)} = \sum_{x=1}^{\frac{p-1}{2}} \left[\frac{1}{3x(3x-1)}-\frac{1}{3x(3x+1)}\right]\\ &=\sum_{x=1}^{\frac{p-1}{2}} \left[ \frac{1}{3x-1} - \frac{2}{3x} +\frac{1}{3x+1}\right] = \sum_{x=1}^{\frac{p-1}{2}}\left[ \frac{1}{3x-1} + \frac{1}{3x} +\frac{1}{3x+1}\right] - \sum_{x=1}^{\frac{p-1}{2}} \frac{1}{x} \\ &= H_{\frac{3p-1}{2}}-1 - H_{\frac{p-1}{2}} \end{align*}Therefore, \begin{align*} 2S_q-\frac{1}{p} &= \left(-1-\frac{1}{p}\right) + \frac{2}{p+1} + \frac{2}{p+3}+\cdots+\frac{2}{3p-1}\\ &= -1-\frac{1}{p} + \left(\frac{2}{p+1} + \frac{2}{3p-1}\right) + \left(\frac{2}{p+3} + \frac{2}{3p-3}\right) +\cdots + \left(\frac{2}{2p-2} + \frac{2}{2p+2}\right) +\frac{2}{2p} \\ &\equiv -1 \pmod{p}, \end{align*}since each of the paired fractions sum to 0 mod $p$. Finally, this means $-m/n\equiv -1\pmod{p}$, i.e. $p\mid m-n$.
15.09.2020 07:55
Apply partial fractions on $\frac{2}{(3n - 1)3n(3n + 1)} = \frac{1}{3n - 1} - \frac{2}{3n} + \frac{1}{3n + 1}$, so we need to evaluate the sum $$\begin{aligned} -1 + \left(\frac{1}{1} + \frac{1}{2} - \frac{2}{3} + \frac{1}{4} \right) + \cdots + \left( \frac{1}{q} - \frac{2}{q + 1} + \frac{1}{q + 2} \right) &= \\ \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{p - 1} \right) + \left( \frac{1}{p + 1} + \frac{1}{p + 2} + \cdots + \frac{1}{q + 2} \right) - 3\left(\frac{1}{3} + \frac{1}{6} + \cdots + \frac{1}{q + 1} \right). \end{aligned}$$Ignore the left sum for now, and focus on the right two. Reducing the middle sum $\pmod p$, we get $$\left( \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{\frac{p - 1}{2}} \right),$$while the right sum becomes $$-\left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{\frac{p - 1}{2}} \right),$$meaning we get extreme cancellation. However, also notice that $\frac{1}{1} + \frac{1}{2} + \cdot + \frac{1}{p - 1}$ reduces to $0$, so we are done.
12.02.2021 09:45
Note that \begin{align*} 2S_q & = 2\sum_{k=1}^{\frac{p-1}{2}} \frac{1}{(3k-1)(3k)(3k+1)}\\ & = 2\sum_{k=1}^{\frac{p-1}{2}} \left(\frac{\tfrac{1}{2}}{3k-1} - \frac{1}{3k} + \frac{\tfrac{1}{2}}{3k+1}\right)\\ & = \sum_{k=1}^{\frac{p-1}{2}} \frac{1}{3k-1} - \frac{2}{3k} + \frac{1}{3k+1}\\ & = \sum_{k=1}^{\frac{p-1}{2}} \frac{1}{3k-1} + \frac{1}{3k} + \frac{1}{3k+1} - \frac{3}{3k}\\ & = \sum_{k=2}^{\frac{3(p-1)}{2}} \frac{1}{k} - \sum_{k=1}^{\frac{p-1}{2}} \frac{1}{k}\\ & = -1 + \sum_{\frac{p+1}{2}}^{\frac{3(p-1)}{2}} \frac{1}{k}. \end{align*} Therefore, \begin{align*} \frac{m}{n} & = \frac{1}{p} - 2S_q\\ & = \frac{1}{p} + 1 - \sum_{\frac{p+1}{2}}^{\frac{3(p-1)}{2}} \frac{1}{k} \end{align*} which implies that \begin{align*} \frac{m-n}{n} & = \frac{1}{p} -\sum_{\frac{p+1}{2}}^{\frac{3(p-1)}{2}} \frac{1}{k}\\ \end{align*} Note that there are exactly $p$ numbers from $\tfrac{p+1}{2}$ to $\tfrac{3(p-1)}{2}$, so the set of integers in between these two numbers (inclusive) is equal to the set $\{0, 1, \cdots, p-1\}$ modulo $p$. Therefore, after being subtracted from $\frac{1}{p}$, we have \begin{align*} \frac{1}{p} -\sum_{\frac{p+1}{2}}^{\frac{3(p-1)}{2}} \frac{1}{k} & = -\left(\sum_{k=1}^{p-1} \frac{1}{k}\right)\\ & \equiv -(1 + 2 + \cdots + p-1)\\ & \equiv -p\cdot \frac{p-1}{2}\\ & \equiv 0 \pmod{p} \end{align*} which implies the claim. $\square$
31.08.2021 16:53
Note that our sum is \[\frac1p - 2S_q = \frac1p - \sum_{k=1}^{\frac{p-1}{2}} \frac{2}{(3k-1)(3k)(3k+1)} = \frac1p - \sum_{k=1}^{\frac{p-1}{2}} (\frac{1}{3k-1}-\frac{2}{3k}+\frac{1}{3k+1})\]Which we may separate into \[=\frac1p-\sum_{i=2}^{q+2} \frac1i + 3\sum_{k=1}^{\frac{p-1}{2}} \frac{1}{3k} =\frac1p-\sum_{i=2}^{\frac{3p-1}{2}} \frac1i + \sum_{k=1}^{\frac{p-1}{2}} \frac{1}{k} = \frac1p + 1 - \sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}} \frac1k\]We may pair up terms, and cancel out the $\frac1p$, to get \[1- \sum_{i=0}^{\frac{p-3}{2}}\frac{1}{\frac{p+1}{2}+i} + \frac{1}{\frac{3p-1}{2}-i}=1- \sum_{i=0}^{\frac{p-3}{2}} \frac{2p}{(\frac{p+1}{2}+i)(\frac{3p-1}{2}-i)}\]We may write the term as $\frac{pa}{b}$ since it's divisible by $p$, so this equals \[1-\frac{pa}{b}= \frac{b-pa}{b}\]Thus, since $(b-pa)-b\equiv 0 \pmod{p}$, and since $b\not\equiv 0 \pmod{p}$, we have that no matter the choice of $m,n$ we always have $p\mid m-n$ and we're done. $\blacksquare$.
13.10.2021 18:51
31.03.2022 18:25
It's easy to see that $$\frac{1}{(3n-1)3n(3n+1)}=\frac{\tfrac{1}{2}}{3n-1}+\frac{-1}{3n}+\frac{\tfrac{1}{2}}{3n+1}.$$Thus \begin{align*} 2S_q&=\frac{1}{2}-\frac{2}{3}+\frac{1}{4}+\frac{1}{5}-\frac{2}{6}+\frac{1}{7}+\dots+\frac{1}{q}-\frac{2}{q+1}+\frac{1}{q+2} \\ &=\left(\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{q+2}\right)-\left(\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{\tfrac{q+1}{3}}\right) \\ &=-1+\left(\frac{1}{\tfrac{q+4}{3}}+\frac{1}{\tfrac{q+7}{3}}+\dots+\frac{1}{q+2}\right) \\ &=-1+\left(\frac{1}{\tfrac{p+1}{2}}+\frac{1}{\tfrac{p+3}{2}}+\dots+\frac{1}{\tfrac{3p-1}{2}}\right). \end{align*}We wish to show that if $$2S_q+1-\frac{1}{p}=\frac{a}{b},$$then $p\mid a$. Note that this expression is equal to \[\left(\frac{1}{\tfrac{p+1}{2}}+\frac{1}{\tfrac{3p-1}{2}}\right)+\left(\frac{1}{\tfrac{p+3}{2}}+\frac{1}{\tfrac{3p-3}{2}}\right)+\dots+\left(\frac{1}{p-1}+\frac{1}{p+1}\right)\]which is equal to \[\frac{2p}{\left(\tfrac{p+1}{2}\right)\left(\tfrac{3p-1}{2}\right)}+\frac{2p}{\left(\tfrac{p+3}{2}\right)\left(\tfrac{3p-3}{2}\right)}+\dots+\frac{2p}{(p-1)(p+1)}.\]At this point we can multiply through by the product of the denominators; evidently, the denominator of the final (possibly unsimplified) fraction will not be divisible by $p$, while the numerator is, which finishes the problem. $\blacksquare$
12.04.2022 21:43
It is easy to check that we can write $$\frac{1}{n(n+1)(n+2)}=\frac{1}{2}\left(\frac{1}{n}-\frac{2}{n+1}+\frac{1}{n+2}\right),$$which can be obtained through partial fraction decomposition. Therefore, \begin{align*} 2S_q&=\sum_{k=1}^{(p-1)/2} \left(\frac{1}{3k-1}-\frac{2}{3k}+\frac{1}{3k+1}\right)\\ &=\sum_{k=1}^{(p-1)/2} \left(\frac{1}{3k-1}+\frac{1}{3k}+\frac{1}{3k+1}\right)-\sum_{k=1}^{(p-1)/2} \frac{3}{3k}\\ &=-1+\sum_{k=1}^{(3p-1)/2} \frac{1}{k}-\sum_{k=1}^{(p-1)/2}\frac{1}{k}\\ &=-1+\sum_{k=(p+1)/2}^{(3p-1)/2} \frac{1}{k} \end{align*}Conveniently, subtracting $\tfrac{1}{p}$ from this makes all of the denominators not divisible by $p$, which means we can work modulo $p$; from here on, all congruences are modulo $p$. We have: \begin{align*} \frac{1}{p}-2S_q&=1-\sum_{k=(p+1)/2}^{p-1} \frac{1}{k}-\sum_{k=p+1}^{(3p-1)/2}\frac{1}{k}\\ &\equiv 1-\sum_{k=(p+1)/2}^{p-1} \frac{1}{k}-\sum_{k=1}^{(p-1)/2} \frac{1}{k}\\ &\equiv 1-\sum_{k=1}^{p-1} \frac{1}{k} \equiv 1, \end{align*}so $\tfrac{m}{n} \equiv 1 \pmod{p} \implies m \equiv n \pmod{p}$, yielding $p \mid m-n$ as desired. $\blacksquare$
16.07.2022 02:38
This is a kind of problem that basically forces its idea into your face. \begin{align*} \frac{m-n}n &= \frac 1p - 2S_q - 1 \\ &= \frac 1p - \sum_{i=1}^{\frac{q+1}3} \frac 1{(3i-1)(3i)(3i+1)} -1 \\ &= \frac 1p - \sum_{i=2}^{\frac{q+1}3} \left(\frac 1{3i-1} - \frac 2{3i} + \frac 1{3i+1}\right) -1\\ &= \frac 1p - \sum_{i=2}^{q+2} \frac 1i + 3 \sum_{i=1}^{\frac{q+1}3} \frac 1{3i}-1 \\ &= \frac 1p - \sum_{i=2}^{q+2} \frac 1i + \sum_{i=1}^{\frac{q+1}3} \frac 1i-1 \\ &= \frac 1p - \sum_{i=\frac{q+4}3}^{q+2} \frac 1i + 1 - 1 \\ &= \frac 1p - \sum_{i=\frac{q+4}3}^{\frac{2q+2}3} \frac{2p}{\frac i3 \cdot (4q+10-i)} - \frac 1p \\ &= -\sum_{i=\frac{q+4}3}^{\frac{2q+2}3} \frac{2p}{\frac i3 \cdot (4q+10-i)}. \end{align*}None of the terms in the denominators are multiples of $p$, so we are done.
01.01.2023 00:26
We will prove that $m \equiv n \pmod{p}$. Note that \begin{align*} S_q &= \sum_{k=1}^{(p-1)/2} \frac{1/2}{3k-1} - \frac{1}{3k} + \frac{1/2}{3k+1} \\ &= \frac{1}{2} \sum_{n=1}^{(p-1)/2} \frac{1}{3k-1} - \frac{2}{3k} + \frac{1}{3k+1} \\ &= \frac{1}{2} \sum_{n=1}^{(p-1)/2} \frac{1}{3k-1} + \frac{1}{3k} + \frac{1}{3k+1} - \frac{3}{3k} \\ &= \frac{1}{2} \sum_{n=1}^{(p-1)/2} \frac{1}{3k-1} + \frac{1}{3k} + \frac{1}{3k+1} - \frac{1}{2} \sum_{k=1}^{(p-1)/2} \frac{1}{k}. \end{align*}Since $\frac{1}{p} - 2S_q = \frac{m}{n}$ we know that $1 - \frac{1}{p} + 2S_q = 1 - \frac{m}{n} = \frac{n-m}{n}$. (I had to look at the solution for this idea). So we know \begin{align*} 1 - \frac{1}{p} + 2S_q &= 1 - \frac{1}{p} + \sum_{n=1}^{(p-1)/2} \frac{1}{3k-1} + \frac{1}{3k} + \frac{1}{3k+1} - \sum_{k=1}^{(p-1)/2} \frac{1}{k} \\ &= \left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{p-1}\right) + \left(\frac{1}{p+1} + \frac{1}{p+2} + \dots + \frac{1}{\frac{3p-1}{2}}\right) - \left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{\frac{p-1}{2}}\right). \end{align*}By Wolstenhole's Theorem or Sum of powers mod p lemma, we know that the first bracket is $0 \pmod{p}$. The second bracket contains $p-1$ terms and so by Sum of Powers mod p lemma we know that it too is $0 \pmod{p}$. Similarly the last bracket is also $0 \pmod{p}$. Hence we know that $\frac{n-m}{n} \equiv 0 \pmod{p}$. Thus we can conclude that $n - m \equiv 0 \pmod{p}$ or $n \equiv m \pmod{p}$ as desired.
03.01.2023 07:39
All congruences are taken modulo $p$. Note that if $m\equiv n$, then $\tfrac{m}{n}\equiv 1$, so we will show that $\tfrac{1}{p}-2S_q\equiv 1$. We have \begin{align*} \frac{1}{p}-2S_q&=\frac{1}{p}-\sum_{x=1}^{\frac{q+1}{3}}\frac{1}{(3x-1)(3x)(3x+1)} \\ &=\frac{1}{p}-\sum_{x=1}^{\frac{p-1}{2}}\left(\frac{1}{3x-1}-\frac{2}{3x}+\frac{1}{3x+1}\right) \\ &=\frac{1}{p}-\sum_{x=1}^{\frac{p-1}{2}}\left(\frac{1}{3x-1}+\frac{1}{3x}+\frac{1}{3x+1}\right)+\sum_{x=1}^{\frac{p-1}{2}}\frac{3}{3x} \\ &=\frac{1}{p}-\left(\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{\frac{3p-1}{2}}\right)+ \left(\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{\frac{p-1}{2}}\right) \\ &\equiv-\left(\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{p-1}\right). \end{align*}To finish, observe that \begin{align*} \sum_{x=1}^{p-1}\frac{1}{x}&=\sum_{x=1}^{\frac{p-1}{2}}\left(\frac{1}{x}+\frac{1}{p-x}\right)=\sum_{x=1}^{\frac{p-1}{2}}\frac{p}{x(p-x)} \equiv 0. \end{align*}This implies \begin{align*} \frac{1}{p}-2S_q&\equiv-\left(\frac{1}{2}+\dots+\frac{1}{p-1}\right)\equiv-(-1)\equiv 1, \end{align*}as desired.
12.08.2023 08:36
We will show that $\frac1p-2S_q=1\pmod p$, which it would follow $\frac mn\equiv 1\iff m\equiv n\pmod p$. Indeed, note that $$ \sum_{x=1}^{p-1}\frac{1}{x}=\sum_{x=1}^{\frac{p-1}{2}}\left(\frac{1}{x}+\frac{1}{p-x}\right)=\sum_{x=1}^{\frac{p-1}{2}}\frac{p}{x(p-x)}\equiv 0\text{ (1)}.$$$$\frac{1}{p}-2S_q=\frac{1}{p}-\sum_{x=1}^{\frac{q+1}{3}}\frac{1}{(3x-1)(3x)(3x+1)}=\frac{1}{p}-\sum_{x=1}^{\frac{p-1}{2}}\left(\frac{1}{3x-1}-\frac{2}{3x}+\frac{1}{3x+1}\right)$$$$=\frac{1}{p}-\sum_{x=1}^{\frac{p-1}{2}}\left(\frac{1}{3x-1}+\frac{1}{3x}+\frac{1}{3x+1}\right)+\sum_{x=1}^{\frac{p-1}{2}}\frac{3}{3x}=\frac{1}{p}-\left(\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{\frac{3p-1}{2}}\right)+\left(\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{\frac{p-1}{2}}\right)$$$$\equiv-\left(\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{p-1}\right)\equiv^{(1)}-(-1)\equiv1\pmod p,$$as desired.
10.11.2023 04:29
Note that $\frac{2}{(x)(x+1)(x+2)} = \frac{1}{x}-\frac{2}{x}+\frac{1}{x+1}$. This makes $S_{q}$ into \[2S_{q}= \frac{1}{2}-\frac{2}{3}+\frac{1}{4}+\ldots+\frac{1}{q}-\frac{2}{q+1}+\frac{1}{q+1}\]Note that if $m-n \equiv 0 \pmod{p}$, then $1-\frac{m}{n}\equiv 0 \pmod{p}$. It suffices to prove that \[1+2S_{q}-\frac{1}{p} \equiv 0 \pmod{p}\]Note \begin{align*} 1+2S_{q} &= 1+\frac{1}{2}-\frac{2}{3}+\frac{1}{4}+\ldots+\frac{1}{q}-\frac{2}{q+1}+\frac{1}{q+2} \\ &= \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{q+2} - \frac{3}{3}(\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{\frac{p-1}{2}}) \end{align*}Subtracting $\frac{1}{p}$ and taking$\pmod{p}$ on the denominators, causes everything to cancel, giving $\equiv 0 \pmod{p}$, finishing the proof.
26.12.2024 12:56
First, we simplify $S_q$, removing any instances of $q$ and replacing them with $p$: \[S_q = \sum_{k = 1}^{\frac{q+1}{3}} \frac{1}{(3k-1)3k(3k+1)}\]\[S_q = \sum_{k = 1}^{\frac{p-1}{2}} \frac{1}{(3k-1)3k(3k+1)}\] Using partial fraction decomposition, we obtain \[S_q = 2\sum_{k = 1}^{\frac{p-1}{2}} \frac{1}{3k - 1} + \frac{1}{3k + 1} - \frac{2}{3k}\] Thus, we will analyze \[\frac{1}{p} - \sum_{k = 1}^{\frac{p-1}{2}} \frac{1}{3k - 1} + \frac{1}{3k + 1} - \frac{2}{3k} = \frac{m}{n}\] Rewrite the expression as follows: \[\frac{1}{p} - \left(\sum_{k = 1}^{\frac{p-1}{2}} \frac{1}{3k - 1} + \frac{1}{3k} + \frac{1}{3k + 1} - \frac{1}{k}\right) = \frac{m}{n}\]\[\frac{1}{p} - \left(\sum_{k = 1}^{\frac{p-1}{2}} \frac{1}{3k - 1} + \frac{1}{3k} + \frac{1}{3k + 1} - \sum_{k = 1}^{\frac{p-1}{2}} \frac{1}{k}\right) = \frac{m}{n}\]\[\frac{1}{p} - \left(\sum_{k = 1}^{\frac{3p-1}{2}} \frac{1}{k} - \sum_{k = 1}^{\frac{p-1}{2}} \frac{1}{k} - 1\right) = \frac{m}{n}\]\[\frac{1}{p} - \sum_{k = \frac{p+1}{2}}^{\frac{3p-1}{2}} \frac{1}{k} = \frac{m - n}{n}\]\[-\sum_{k = \frac{p+1}{2}}^{p - 1} \frac{1}{k} - \sum_{k = p + 1}^{\frac{3p - 1}{2}} \frac{1}{k} = \frac{m - n}{n}\]\[-\sum_{k = \frac{p+1}{2}}^{p - 1} \frac{1}{k} + \frac{1}{2p - k} = \frac{m - n}{n}\]\[-2p\sum_{k = \frac{p+1}{2}}^{p - 1} \frac{1}{k(2p - k)} = \frac{m - n}{n}\] Because $p$ is prime, the denominators cannot contain any multiples of $p$. Thus, $m - n$ must be divisible by $p$ as the LHS has a factor of $p$, as desired.