Lets say we have a polynomial $N$ which has been expressed in $p$ where $p$ is a prime and all the coefficients in the polynomial are less than $p$. We are asked to prove, that the highest power of $p$ contained in $N!$ would be $(N-s) \over (p-1)$ where $s$ is the sum of all the coefficients.
I tried to do the question by making up the expression of $N$
$$N=a_0+a_1p^1+a_2p^2.......+a_np^n$$
where $a_0+a_1+a_2+.........+a_n=s$
Now the highest power of p contained would be
$$[N/p]+[N/p^2]+[N/p^3]+......+[N/p^n]$$
$$[N/p]=a_0/p+a_1+a_2p+.....+a_np^{n-1}$$
$$[N/p^2]=a_0/p^2+a_1/p+a_2+.....+a_np^{n-2}$$
$$..$$$$..$$$$..$$$$[N/p^n]=a_0/p^n+a_1/p^{n-1}+a_2p^{n-2}+.....+a_n$$
adding them all would give
$[N/p]+[N/p^2]+[N/p^3]+......+[N/p^n]=(a_1+a_2+a_3....a_n)+{1/p}(a_0+a_1+a_2+a_3....a_{n-1})+{1/p^2}(a_0+a_1+a_2+a_3....a_{n-2})....+1/p^n(a_0)+p(a_2+a_3....+a_n)+p^2(a_3+a_4....+a_n)+....+p^n(a_n)$
Though the things can be summed up to a large extent by the use of GP and writing $a_0+a_1+a_2+a_3....a_n=s$ but the expression is becoming pretty much complicated and I am unable to extract as the expression has become so much complicated.
Please provide the solution/hint(more preferable) to the question using only basic number theory expressions as it was in the first exercise of my book and the author wants me to solve it the simple way only.
Answer
The integer parts do not include fractions, so for example
$$\lfloor N/p\rfloor=a_1+a_2p+...+a_np^{n-1}\\ \lfloor N/p^2\rfloor=a_2+a_3p+...+a_np^{n-2}$$
When you add them up, try collecting the $a_i$ instead of $p$. For example, $a_3$ is multiplied by $p^2+p+1$.
Multiply the full sum by $p-1$ and try to make the result equal $N-s$.
No comments:
Post a Comment