\documentstyle[12pt]{article} %This is spec.tex % Paper is 8/\12inches. Top and left margins are 1in each and text is %centred. \textwidth 6.4in \textheight 9in \setlength{\oddsidemargin}{0in} \setlength{\topmargin}{0in} %\addtolength{\topmargin}{-1.5in} \pagestyle{empty} \addtolength{\topmargin}{-0.55in} \renewcommand{\baselinestretch}{1.5} \baselineskip0.90cm %\def\by#1#2{\displaystyle {#1}\over \displaystyle {#2}} \begin{document} \indent For any polynomial \ $F(x)$, let \ $\bar{F}$ \ denote the reduction (to the least nonnegative residue) (\mbox{mod} \ 3) \noindent Question: \ \ If \ $F(x) \ = \ (1 + x)^n, \ \mbox{find} \ \bar{F}(1)$ \indent Write \ $n = \displaystyle{\sum^J_{j=1}} a_j e^j$ Let \ $A \ = \ \{j: \ a_j=1\}; \ \ B = \{j: \ a_j=2\} \\ \ \ \ \ |A| = a; \ \ \ |B| = b$. \indent Let \ $G(x) = \ \displaystyle{\pi^J_{j=1}} \ (1+x^{3^j})^{a_j}$ \indent Since \ $(1 + x)^3 \ \equiv \ 1 + x^{3^j} \ (\mbox{mod} \ 3)$, \ we have \ $G(x) \ \equiv \ F(x) \ (\mbox{mod} \ 3)$. \indent Hence the problem reduces to finding \ $\bar{G}(1)$. The advantage in \ $G$ \ is that there is no carry over, that is every monomial in the product occurs exactly once. \indent Now, \ $G(x) = \displaystyle{\Pi_{j\in B}} (1 + 2x^{3^j} + x^{2 \star 3^j}) \displaystyle{\Pi_{j \in A}} \left(1 + x^{3^j}\right) \ = \ \sum b_j x^j$ $$\begin{array}{lccl} \mbox{Let} & R & = & |\{j: b_j \equiv 2 (\mbox{mod} \ 3)\} \\ & S & = & \{j: \ b_j \equiv 1 (\mbox{mod} \ 3)\} \end{array}$$ \indent so that \ $\bar{G}(1) \ = \ S + 2R$. \indent From the expansion of \ $G(x)$, \ it is clear that if each non zero \ $b_j$, is replaced by \ $1$, we get $$\displaystyle{H(x) = \Pi_{j\in B}} \ (1 + x^{3^j} + x^{2 \star 3^j}) \ \displaystyle{\Pi_{j\in A}} \ \left(1 + x^{3^j}\right)$$ \noindent and hence \ $R + S = H(1) = 3^b 2^a$. \indent Also if we replace \ $b_j$ \ by \ $(-1)$ \ for \ $j \in R$, \ and \ $b_j \ \mbox{by} \ (+1)$ \ for \ $j \in S$, \ we end up with $$\displaystyle{\Pi_{j\in B}} \left(1 - x^{3^j} + x^{2 \star 3^j}\right) \ \displaystyle{\Pi_{j\in A}} \left(1 + x^{3^j}\right)$$ \noindent and hence \ $S - R \ = \ 2^a$. \indent Thus \ $S \ = \ 2^{a-1} (3^b + 1)$ \ and \ $R \ = \ 2^{a-1} (3^b - 1)$. \indent Hence \ $\bar{G}(1) \ = \ S + 2R \ = \ 2^{a-1} (3^{b+1} - 1)$ \end{document}