Polynomials in Number Theory
One of my favorite lemmas is “Freshman’s Dream,” which states this:
- Given a prime \(p\) and integers \(a, b\), the identity \((a+b)^p \equiv a^p + b^p \mod{p}\) holds true.
I honestly don’t see it show up too often, but the name is funny, so I’ll certainly never forget this one.
It relies on the fact that all binomial coefficients of the form \({p \choose k} = \frac{p!}{k!(p-k)!}\) have \(p \text{ }\vert \text{ } p!\) but \(p \nmid k!(p-k)!\), so \(p \text{ }\vert \text{ } {p \choose k}\). This same concept can be applied more generally to prove the following:
- \((a+b)^{p^k} \equiv a^{p^k} + b^{p^k} \mod{p}\).
- If \(\operatorname{P_1}(x), \operatorname{Q_1}(x), \operatorname{P_2}(x), \operatorname{Q_2}(x)\) are two pairs of polynomials satisfying \(\operatorname{P_1}(x) - \operatorname{Q_1}(x) \equiv\) \(\operatorname{P_2}(x) - \operatorname{Q_2}(x)\equiv 0 \mod{p}\) (meaning \(p\) divides every coefficient of \(\operatorname{P_1} - \operatorname{Q_1}\) and of \(\operatorname{P_2} - \operatorname{Q_2}\)), then \(\operatorname{P_1}\operatorname{Q_1} \equiv \operatorname{P_2}\operatorname{Q_2} \mod{p}\) and \(\operatorname{P_1} + \operatorname{Q_1} \equiv \operatorname{P_2} + \operatorname{Q_2} \mod{p}\).
MAA Likes NT and Polynomials
Another lemma this reminds me of is the following statement:
- If \(\operatorname{P}\) is a polynomial with integer coefficients and \(a, b\) are two integer inputs, then \((a - b) \text{ } \vert \text{ } (\operatorname{P}(a) - \operatorname{P}(b))\).
This one has showed up on AIMEs and AMCs quite a few times, and here’s one example using it:
-
Problem: Let \(f(x)=ax^2+bx+c\), where \(a\), \(b\), and \(c\) are integers. Suppose that we have \(f(1)=0\), \(50<f(7)<60\), \(70<f(8)<80\), \(5000k<f(100)<5000(k+1)\) for some integer \(k\). What is \(k\)?
- Solution: We have an integer polynomial with integer inputs, and we can conveniently solve for the values of each of \(f(7), f(8)\) given our above lemma.
- \(6 \text{ } \vert \text{ } f(7) - f(1)\), which implies that \(f(7)\) is an integer multiple of \(6\) in the range \((50, 60)\), or \(f(7) = 54\).
- Similarly, \(7 \text{ } \vert \text{ } f(8) - f(1)\), so \(f(8)\) must equal \(77\).
- We now have the following system:
- Which I argue isn’t terrible to solve. But you can also write the polynomial as \(f(x) = a(x-1)(x-r)\) as we’re given one root, \(1\), where it’s a bit faster to see that \(a = 2\).
- Our polynomial ends up being \(f(x) = 2(x-1)(x-\frac{5}{2}) = 2x^2-7x+5\), and \(f(100) = 19305\), so \(k = 3\).
Lucas’ Theorem
This theorem is really cool to me, and it says the following:
- Let \(m = \overline{m_k . . . m_1m_0}, n = \overline{n_k . . . n_1n_0}\) in base \(p\). Then we can write:
- In this, we assume \({0 \choose 0} = 1\), and \({n_i \choose m_i} = 0\) when \(n_i < m_i\).
As an example, let’s consider \({6 \choose 3} \mod{2}\). We get:
\[{6 \choose 3} = {110_2 \choose 011_2} = {1 \choose 0}{1 \choose 1}{0 \choose 1} = 1*1*0 = 0 \mod{2}\]Or, for instance, \({56 \choose 26} \mod{5}\).
\[{56 \choose 26} = {211_5 \choose 101_5} = {2 \choose 1}{1 \choose 0}{1 \choose 1} = 2*1*1 = 2 \mod{5}\]Proof: This turns out to be a direct application of Freshman’s Dream!
Consider a binomial expansion on \((1+x)^n\). In this, every power \(x^m\) has coefficient \({n \choose m}\).
Rewriting \(n\) in base \(p\) as \(n_kp^k+n_{k-1}p^{k-1} + ... + n_1p + n_0\), we have:
\[(1+x)^n = (1+x)^{n_kp^k+n_{k-1}p^{k-1} + ... + n_1p + n_0}\] \[= {\prod_{i=0}^{k}}(1+x)^{n_ip^i}\] \[= {\prod_{i=0}^{k}}((1+x)^{p^i})^{n_i}\] \[\equiv {\prod_{i=0}^{k}}(1+x^{p^i})^{n_i}\]In factor \(i = j\), can create \(x^m\) in \({n_j \choose m_j}\) ways, where \(m_j\) is the coefficient of \(p^j\) in \(m\)’s base-\(p\) expansion. So, our coefficient of \(x^m\) is also equivalent to \({n \choose m} = {n_k \choose m_k}{n_{k-1} \choose m_{k-1}} ... {n_1 \choose m_1}{n_0 \choose m_0} \mod{p}\).