$a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
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) $.
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
Re: $a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
If you're completely stuck:
I forgot to mention: this problem is from Putnam 1986
Last edited by mutasimmim on Thu Oct 02, 2014 10:26 am, edited 1 time in total.
Re: $a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
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.\]
\[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.\]
Last edited by Nirjhor on Thu Oct 02, 2014 1:25 pm, edited 1 time in total.
- What is the value of the contour integral around Western Europe?
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
Re: $a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
Nirjhor wrote: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?
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$
Re: $a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
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.
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.
- What is the value of the contour integral around Western Europe?
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
Re: $a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
oh, I missed it actually. My bad, sorry.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$
Re: $a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
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).Nirjhor wrote: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}.\]
Instead, try expressing the sum as a summation of summations of series to derive the same formulation.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: $a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
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.
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.
- What is the value of the contour integral around Western Europe?
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
Re: $a\equiv b$ whenever $F(a)\equiv F(b) (mod p)$
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.
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.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi