heureka

avatar
Usernameheureka
Score26367
Membership
Stats
Questions 17
Answers 5678

 #2
avatar+26367 
+5

 If $f$ is a polynomial of degree $4$ such that $$f(0) = f(1) = f(2) = f(3) = 1$$ and $$f(4) = 0,$$ then determine $f(5)$.

 

\(\small{ \begin{array}{lrrrrrrrrrrrrr} & f(0) && f(1) && f(2) && f(3) && f(4) && {\color{red}f(5)} && \cdots \\ & d_0=1 && 1 && 1 && 1 && 0 && {\color{red}-4} && \cdots \\ \text{1. Difference } && d_1=0 && 0 && 0 && -1 && {\color{red}-4} && \cdots \\ \text{2. Difference } &&& d_2=0 && 0 && -1 && {\color{red}-3} && \cdots \\ \text{3. Difference } &&&& d_3=0 && -1 && {\color{red}-2} && \cdots \\ \text{4. Difference } &&&&& {\color{red}d_4=-1 } && {\color{red}-1} && \cdots \\ \end{array} }\)

 

\(\text{ ${\color{red}d_4=-1}$ is constant, if a polynomial is of degree 4.} \)

 

\(f(5) = {\color{red}-1}+(-1)+(-1)+(-1)+0 = -4\)

 

 

polynomial:

\(\small{ \begin{array}{rcll} \hline a_n &=& \binom{n-1}{0}\cdot {\color{red}d_0 } + \binom{n-1}{1}\cdot {\color{red}d_1 } + \binom{n-1}{2}\cdot {\color{red}d_2 } + \binom{n-1}{3}\cdot {\color{red}d_3 } + \binom{n-1}{4}\cdot {\color{red}d_4 } \\\\ && \quad {\color{red}d_0 } = 1 \quad {\color{red}d_1}={\color{red}d_2}={\color{red}d_3} = 0 \quad {\color{red}d_4 } = -1 \\\\ a_n &=& \binom{n-1}{0}\cdot 1 + \binom{n-1}{1}\cdot 0 + \binom{n-1}{2}\cdot 0 + \binom{n-1}{3}\cdot 0 + \binom{n-1}{4}\cdot (-1) \\ a_n &=& \binom{n-1}{0}\cdot 1 - \binom{n-1}{4} \quad & | \quad \binom{n-1}{0} = 1 \\ a_n &=& 1 - \dbinom{n-1}{4} \quad & | \quad n = x+1 \\ \mathbf{f(x)} &\mathbf{=}& \mathbf{ 1 - \binom{x}{4} } \\\\ && \quad \dbinom{x}{4} = \left(\dfrac{x}{4}\right)\left(\dfrac{x-1}{3}\right)\left(\dfrac{x-2}{2}\right)\left(\dfrac{x-3}{1}\right) \\\\ \mathbf{f(x)} &\mathbf{=}& \mathbf{ 1 - \dfrac{x(x-1)(x-2)(x-3)}{24} } \\ \end{array} } \)

 

laugh

Jan 30, 2018
 #5
avatar+26367 
+1
Jan 29, 2018
 #3
avatar+26367 
+3

What is the smallest positive integer N  for which

\((12{,}500{,}000)\cdot n\) 

leaves a remainder of 111 when divided by 999,999,999?

1.

\(\begin{array}{|rcll|} \hline (12~500~000)\cdot n & \equiv & 111 \pmod{999~999~999} \quad & | \quad :(12~500~000) \\ n & \equiv & 111\cdot \dfrac{1}{12~500~000} \pmod{999~999~999} \\ \hline \end{array}\)

 

\(\begin{array}{|lcll|} \hline \text{According to Euler's theorem,} \\ \text{if $a$ is coprime to $m$, that is, $gcd(a, m) = 1$, then }\\ {\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}\\ \text{where ${\displaystyle \phi } $ is Euler's totient function.}\\ \text{Therefore, a modular multiplicative inverse can be found directly:} \\ {\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.} \\ \hline \end{array}\)

 

2.

\(\text{greatest common divisor $gcd(12~500~000,999~999~999) = 1$ }\)

 

\(\begin{array}{|rcll|} \hline && \dfrac{1}{12~500~000} \pmod{999~999~999} \\\\ & \mathbf{\equiv} & \mathbf{12~500~000^{-1} \pmod{999~999~999}} \\\\ & \equiv & 12~500~000^{\phi (999~999~999)-1} \pmod{999~999~999} \\\\ & \equiv & 12~500~000^{648~646~704-1} \pmod{999~999~999} \\\\ & \equiv & 12~500~000^{648~646~703} \pmod{999~999~999} \\\\ & \mathbf{\equiv} & \mathbf{80 \pmod{999~999~999}} \\ \hline \end{array}\)

 

3. n = ?

\(\begin{array}{|rcll|} \hline n & \equiv & 111\cdot \dfrac{1}{12~500~000} \pmod{999~999~999} \\\\ & \equiv & 111\cdot \left( 12~500~000^{-1} \pmod{999~999~999} \right) \\\\ & \equiv & 111\cdot 80 \pmod{999~999~999} \\\\ & \mathbf{\equiv} & \mathbf{ 8880 \pmod{999~999~999} } \\ \hline \end{array}\)

 

The smallest positive integer n is 8880.

 

\(\begin{array}{rcll} 12 ~500~000 \cdot 8880 &\equiv & 111 \pmod{999~999~999} \\ 110~000~000~000 &\equiv & 111 \pmod{999~999~999}\ \checkmark\\ \end{array}\)

 

laugh

Jan 29, 2018