Question

Given that $p\ge 7$ is a prime number, evaluate $$1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + (p-2)^{-1} \cdot (p-1)^{-1} \pmod{p}.$$

Answer 1

p >= 7*

Answer 2

Let's try different values of p to see how the sum is expanded out


I'm going to try p = 7 first since it's the smallest prime p allowed here

\[1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + (p-2)^{-1} \cdot (p-1)^{-1} \pmod{p}.\]

\[1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + (7-2)^{-1} \cdot (7-1)^{-1} \pmod{7}.\]

\[1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + 5^{-1} \cdot 6^{-1} \pmod{7}.\]

\[1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1}+ 4^{-1} \cdot 5^{-1} + 5^{-1} \cdot 6^{-1} \pmod{7}.\]

\[1 \cdot 4 + 4 \cdot 5 + 5 \cdot 2+ 2 \cdot 3 + 3 \cdot 6 \pmod{7}.\]

\[4+20+10+6+18 \pmod{7}.\]

\[58 \pmod{7}.\]

\[2 \pmod{7}.\]

Answer 3

That's a specific case (p = 7). I'm still trying to think of how to do this in general for any prime p >= 7

Answer 4

Did your professor give you any hints or formulas to use? I'm still stuck. I have a feeling this uses fermat's little theorem somehow. I'm not sure though.

Answer 5

Nope haha its an Alcumus problem on AOPS
It's supposed to use fermat's little theorem but im sorta confused

@jim_thompson5910

Answer 6

Let me try p = 7 a different way

\[1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + (p-2)^{-1} \cdot (p-1)^{-1} \pmod{p}.\]

\[1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + (7-2)^{-1} \cdot (7-1)^{-1} \pmod{7}.\]

\[1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + 5^{-1} \cdot 6^{-1} \pmod{7}.\]

\[1^{-1} \cdot 2^{-1} + 2^{-1} \cdot 3^{-1} + 3^{-1} \cdot 4^{-1}+ 4^{-1} \cdot 5^{-1} + 5^{-1} \cdot 6^{-1} \pmod{7}.\]

\[(1*2)^{-1} + (2*3)^{-1} + (3*4)^{-1}+ (4*5)^{-1} + (5*6)^{-1} \pmod{7}.\]

\[2^{-1} + 6^{-1} + 12^{-1}+ 20^{-1} + 30^{-1} \pmod{7}.\]

\[2^{-1} + 6^{-1} + 5^{-1}+ 6^{-1} + 2^{-1} \pmod{7}.\]

So that's a bit interesting. We have this symmetry going on. Let me try p = 11 next

Answer 7

I'm going to skip a few steps to save time/space

\[(1*2)^{-1} + (2*3)^{-1} + (3*4)^{-1}+ (4*5)^{-1} + (5*6)^{-1} + (6*7)^{-1}\\+ (7*8)^{-1} + (8*9)^{-1} + (9*10)^{-1} \pmod{11}.\]


\[2^{-1} + 6^{-1} + 12^{-1}+ 20^{-1} + 30^{-1} + 42^{-1} + 56^{-1} + 72^{-1} + 90^{-1} \pmod{11}.\]


\[2^{-1} + 6^{-1} + 12^{-1}+ 9^{-1} + 8^{-1} + 8^{-1} + 1^{-1} + 6^{-1} + 2^{-1} \pmod{11}.\]

This has a bit of symmetry but not as much as the last on did. The 9 and 1 don't match up. I'll try p = 13 next

Answer 8

p = 13

\[(1*2)^{-1} + (2*3)^{-1} + (3*4)^{-1}+ (4*5)^{-1} + (5*6)^{-1} + (6*7)^{-1} + (7*8)^{-1}\\+(8*9)^{-1} + (9*10)^{-1}+(10*11)^{-1} + (11*12)^{-1} \pmod{13}.\]


\[2^{-1} + 6^{-1} + 12^{-1}+ 20^{-1} + 30^{-1} + 42^{-1} + 56^{-1} + 72^{-1} + 90^{-1}+110^{-1}+132^{-1} \pmod{13}.\]


\[2^{-1} + 6^{-1} + 12^{-1}+ 7^{-1} + 4^{-1} + 3^{-1} + 4^{-1} + 7^{-1} + 12^{-1}+6^{-1}+2^{-1} \pmod{13}.\]

Now this has perfect symmetry. I may have made a mistake with p = 11 somewhere?

Answer 9

so p = 13 works?

@jim_thompson5910

Answer 10

i cant try entering 13 as the answer in alcumus and see the result and get the explanation @jim_thompson5910

Answer 11

p = 13 has the same type of symmetry p = 7 does

Answer 12

I'm still stumped on what the answer would be in general for any p

I'm curious what explanation they give

Answer 13

i can try entering 13 @jim_thompson5910

Answer 14

I doubt the answer is 13. That seems too easy, but yeah sure go ahead. Please post the explanation they give. I'm curious how to solve this one

Answer 15

haha it's incorrect..i have 2 chances so should i type in something random just to find the answer? my score will go down but its okay lol @jim_thompson5910 this is a really hard problem

Answer 16

yeah I've never seen anything this tough before. I'm probably overthinking

Answer 17

As $p$ is a prime number, it follows that the modular inverses of $1,2, \ldots, p-1$ all exist. We claim that $n^{-1} \cdot (n+1)^{-1} \equiv n^{-1} - (n+1)^{-1} \pmod{p}$ for $n \in \{1,2, \ldots, p-2\}$, in analogue with the formula $\frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}$. Indeed, multiplying both sides of the congruence by $n(n+1)$, we find that $$1 \equiv n(n+1) \cdot (n^{-1} - (n+1)^{-1}) \equiv (n+1) - n \equiv 1 \pmod{p},$$as desired. Thus, \begin{align*}&1^{-1} \cdot 2^{-1} + 2^{-1} + 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + (p-2)^{-1} \cdot (p-1)^{-1} \\ &\equiv 1^{-1} - 2^{-1} + 2^{-1} - 3^{-1} + \cdots - (p-1)^{-1} \pmod{p}.\end{align*}This is a telescoping series, which sums to $1^{-1} - (p-1)^{-1} \equiv 1 - (-1)^{-1} \equiv \boxed{2} \pmod{p}$, since the modular inverse of $-1$ is itself.

@jim_thompson5910

Answer 18

answer is 2 somehow it didn't quite show up correctly on here i apologize

@jim_thompson5910

Answer 19

You have to change the dollar signs to \ ( and \ )

As \(p\) is a prime number, it follows that the modular inverses of \(1,2, \ldots, p-1\) all exist. We claim that \(n^{-1} \cdot (n+1)^{-1} \equiv n^{-1} - (n+1)^{-1} \pmod{p}\) for \(n \in \{1,2, \ldots, p-2\}\), in analogue with the formula \(\frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}\). Indeed, multiplying both sides of the congruence by \(n(n+1)\), we find that
1=n(n+1)·(n-1-(n+1)-1)=(n+1)-n=1(modp),
as desired. Thus,
\[\begin{align*}&1^{-1} \cdot 2^{-1} + 2^{-1} + 3^{-1} + 3^{-1} \cdot 4^{-1} + \cdots + (p-2)^{-1} \cdot (p-1)^{-1} \\ &\equiv 1^{-1} - 2^{-1} + 2^{-1} - 3^{-1} + \cdots - (p-1)^{-1} \pmod{p}.\end{align*}\]
This is a telescoping series, which sums to \(1^{-1} - (p-1)^{-1} \equiv 1 - (-1)^{-1} \equiv \boxed{2} \pmod{p}\), since the modular inverse of \(-1\) is itself.

Answer 20

Definitely a tough problem. I don't know if I would have come up with that.

Answer 21

Same haha it didn't drop my score that much tho bc it was such a hard one @jim_thompson5910

Answer 22

I think this is a recognizeable telescoping series and in mod p ensures that all the inverses exist I guess.

Answer 23

I think the key lies with this part

\[n^{-1} \cdot (n+1)^{-1} \equiv n^{-1} - (n+1)^{-1} \pmod{p}\]

if you can see how that works, then the telescoping part is a bit more clear

Answer 24

Here's one way to the solution:

\[\sum_{n=1}^{p-2} \frac{1}{n(n+1)} = \sum_{n=1}^{p-2} \frac{1}{n} -\frac{1}{n+1}= 1 - \frac{1}{p-1}\]

Funny thing about \(p-1\) is that it is it's own inverse since \((-1)^2 =1\)
\[p-1 \equiv -1\]\[(p-1)(p-1) \equiv 1\]
So you can replace in the above,
\[\frac{1}{p-1} = p-1\] and we have:
\[1- (p-1) \equiv 2\]

Answer 25

thanks for your help nevertheless :)

@jim_thompson5910
@Kainui