Here is the question:
A polynomial $f$ is given. All its coefficients are non-negative integers, $f(1) = 6$ and $f(7) = 3438$. What is the value of $f(3)$?
And here is the solution:
We do not know the degree of the polynomial, so let it be n.
$\therefore f(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + … + a_0$
$f(1) = a_n + a_{n-1} + a_{n-2} + … + a_0 = 6$
Since all the coefficients are $ \geq 0 \implies a_i \leq 6 \;\forall i \leq n$
$f(7) = a_n7^n + a_{n-1}7^{n-1} + a_{n-2} 7^{n-2} … + a_0 = 3438$
Since all coefficients $a_i \leq 6 \;\forall i \leq n$, this is the base expansion of the number 3438.
So all we need to do is keep dividing by 7 and observe the remainders :
$3438 = 7 \cdot 491 + 1 \implies a_0 = 1$
$491 = 7 \cdot 70 + 1 \implies a_1 = 1$
$70 = 7 \cdot 10 + 0 \implies a_2 = 0$
$10 = 7 \cdot 1 + 3 \implies a_3 = 3$
$1 = 7 \cdot 0 + 1 \implies a_4 = 1$
$\therefore f(x) = x^4 + 3x^3 + x + 1 \implies f(3) = 166$
I don't understand the process that they used, and what "base 7 expansion" is and why they use it. Someone please explain. Thanks
Best Answer
Suppose that $p$ is a positive integer, $M\in\Bbb N$ and $$M=\sum_{k=0}^na_kp^k=\sum_{k=0}^nb_kp^k$$ such that $$a_k,b_k\in\{0,1,...,p-1\}\tag1$$ Then $$\sum_{k=0}^n(a_k-b_k)p^k=0\tag2.$$ From $(2)$, we have $a_0-b_0\equiv0 \pmod p$ which implies that $a_0=b_0$ because of $(1)$. Now assume that $a_k=b_k$ for all $k<i.$ Then from $(2)$ we have $(a_i-b_i)p^i\equiv 0\pmod{p^{i+1}}$ which implies that $a_i=b_i$ because of $(1).$ By induction $a_k=b_k$ for all $k$. Therefore, there is a unique polynomial $f(x)$ whose coefficients are in $\{0,1,...,p-1\}$ and $f(p)=M.$
Now let $p=7$ and $M=3438.$