$a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$

[mutasimmim]

Let $F(n)=1+2n+3n^2+...+(p-1)n^{p-2}$ and $p$ be a prime. Prove that if $F(a)\equiv F(b)$, then $a\equiv b(mod p) $.

[mutasimmim]

If you're completely stuck:

Find $F(n) (mod p)$ in terms of $n$. Then use the fact that every $a$ coprime to $p$ has a unique multiplicative inverse.

I forgot to mention: this problem is from Putnam 1986

[Nirjhor]

For \(p=2\) we have \(F(n)=1\) for all \(n\) so I guess the question asks to prove for odd primes. Notice that
\[F(n) = \sum_{k=1}^{p-1} kn^{k-1} = \sum_{k=1}^{p-1} \dfrac{\text{d}}{\text{d}n} n^k=\dfrac{\text d}{\text d n}\sum_{k=1}^{p-1} n^k=\dfrac{\text d}{\text d n}\left(\dfrac{n^p-n}{n-1}\right)=\dfrac{pn^{p-1}-1}{n-1}-\dfrac{n^p-n}{(n-1)^2}.\] Now if \(p\nmid n-1\) then using Fermat's Little Theorem
\[F(n)=\dfrac{pn^{p-1}-1}{n-1}-\dfrac{n^p-n}{(n-1)^2}\equiv -\dfrac{1}{n-1}\pmod p.\]
So we have \[F(a)\equiv F(b)~\Leftrightarrow ~-\dfrac{1}{a-1}\equiv -\dfrac{1}{b-1}~\Leftrightarrow ~a\equiv b\pmod p.\]
For the case when \(p\mid n-1\), we have \(n\equiv 1~(\bmod ~p)\). Hence
\[F(n)=1+2n+\cdots+(p-1)n^{p-2}\equiv 1+2+\cdots+(p-1)=\dfrac{1}{2}p(p-1)\equiv 0\pmod p.\] And notice that for some \(n\) such that \(p\nmid n-1\) if \(F(n)\equiv 0~(\bmod ~p)\) then \(-1/(n-1)\equiv 0~(\bmod~p)\) which is not possible. So we've proved that \(p\mid F(n)\) iff \(p\mid n-1\). Hence
\[F(a)\equiv F(b)\equiv 0~\Leftrightarrow ~a\equiv b\equiv 1\pmod p.\]

[SANZEED]

For \(p=2\) we have \(F(n)=1\) for all \(n\) so I guess the question asks to prove for odd primes. Notice that
\[F(n) = \sum_{k=1}^{p-1} kn^{k-1} = \sum_{k=1}^{p-1} \dfrac{\text{d}}{\text{d}n} n^k=\dfrac{\text d}{\text d n}\sum_{k=1}^{p-1} n^k=\dfrac{\text d}{\text d n}\left(\dfrac{n^p-n}{n-1}\right)=\dfrac{pn^{p-1}-1}{n-1}-\dfrac{n^p-n}{(n-1)^2}.\] Now if \(p\nmid n-1\) then using Fermat's Little Theorem
\[F(n)=\dfrac{pn^{p-1}-1}{n-1}-\dfrac{n^p-n}{(n-1)^2}\equiv -\dfrac{1}{n-1}\pmod p.\]
So we have \[F(a)\equiv F(b)~\Leftrightarrow ~-\dfrac{1}{a-1}\equiv -\dfrac{1}{b-1}~\Leftrightarrow ~a\equiv b\pmod p.\]
For the case when \(p\mid n-1\), we have \(n\equiv 1~(\bmod ~p)\). Hence
\[F(n)=1+2n+\cdots+(p-1)n^{p-2}\equiv 1+2+\cdots+(p-1)=\dfrac{1}{2}p(p-1)\equiv 0\pmod p.\] And notice that for some \(n\) such that \(p\nmid n-1\) if \(F(n)\equiv 0~(\bmod ~p)\) then \(-1/(n-1)\equiv 0~(\bmod~p)\) which is not possible. So we've also proved that \(p\nmid F(n)\) if \(p\nmid n-1\). Hence
\[F(a)\equiv F(b)\equiv 0~\Leftrightarrow ~a\equiv b\equiv 1\pmod p.\]

What if there exists $a,b$ such that $p\mid (a-1)$ but $p\nmid (b-1)$? I mean if you write $F(a)\equiv -\dfrac{1}{a-1}$ and $F(b)\equiv -\dfrac{1}{b-1}$ mod $p$ at the same time, then it means you are assuming that $p\mid (a-1), p\mid (b-1)$ which is what to prove. Isn't that so?

[Nirjhor]

I've proved that \(p\mid a-1\) iff \(p\mid F(a)\). So if \(p\mid a-1\) but \(p\nmid b-1\) then \(F(a)\equiv F(b)~(\bmod~p)\) is never possible (because then \(F(a)\equiv 0~(\bmod~p)\) but \(F(b)~\text{not}\equiv 0~(\bmod~p)\)) i.e. that kind of pair \((a,b)\) doesn't exist.

And notice that when I'm writing \(F(a)\equiv -1/(a-1)\) and \(F(b)\equiv -1/(b-1)~(\bmod~p)\) then I'm assuming \(p\nmid a-1\) and \(p\nmid b-1\) at the same time, not \(p\mid a-1\) and \(p\mid b-1\). I think you misread that part.

[SANZEED]

oh, I missed it actually. My bad, sorry.

[*Mahi*]

Notice that
\[F(n) = \sum_{k=1}^{p-1} kn^{k-1} = \sum_{k=1}^{p-1} \dfrac{\text{d}}{\text{d}n} n^k=\dfrac{\text d}{\text d n}\sum_{k=1}^{p-1} n^k=\dfrac{\text d}{\text d n}\left(\dfrac{n^p-n}{n-1}\right)=\dfrac{pn^{p-1}-1}{n-1}-\dfrac{n^p-n}{(n-1)^2}.\]

There are major controversies about using calculus in olympiad problems. Even when you are allowed to use it, you have to define a lot of additional parameters just for the sake of rigor. (And all of that just for an inequality problem, not even NT).
Instead, try expressing the sum as a summation of summations of series to derive the same formulation.

[Nirjhor]

I've heard that as long as you're not brute forcing using calculus (using Lagrange multipliers, partial derivatives on multivariable functions), and the approach is beautiful enough, it's not bad to use a little calculus in Olympiads. Correct me if I've heard wrong?

Here's another way to manipulate the sum: notice that for \(n\neq 1\) \[(1-n)F(n)=F(n)-nF(n)=\left(\sum_{k=0}^{p-2} n^k\right)-(p-1)n^{p-1}=\left(\dfrac{n^{p-1}-1}{n-1}\right)-(p-1)n^{p-1}\] and the rest is easy. The \(n=1\) case is also easy to deal with.

[*Mahi*]

Well, as I have SEEN, anything but established tools (double-derivatives for convexity) is looked down upon. Also, this type of cases (integration with integer parameters) can cause problems.

For example, in this case, you need to define at least one other function, because

1. $\textbf{Differentiation works in } \textit{at least continuous } \textbf{functions}$, which means you can't differentiate $F(n)$ unless you extend it to reals or some subset of it.

2. $\textbf{FLT works in } \textit{(extended) integer } \textbf{functions}$, which means if you extend $F$ to reals you can't write $F(n) \equiv -\dfrac{1}{n-1}\pmod p$

Yes, I know what you did is correct $\textbf{ with proper definitions}$ but in olympiads like IMO/APMO as calculus is out of syllabus, you will not get any "benefit of doubt". This solution of course won't get a 0, but may lose ~2 marks.

What you did in the second post is definitely acceptable. I recommend that even if you derive the formula using differentiation, prove it in some other way.