# Factors of a quadratic in modulo $9$

Prove: If $$a$$ is any integer and the polynomial $$f(x) = x^2 + ax + 1$$ factors mod $$9$$, then there are three distinct non-negative integers $$y$$ less than $$9$$ such that $$f(y) \equiv 0 \pmod 9$$.

I'm working through this problem right now, and I've found possible ways to factor it in the form $$(x+b)(x+c)$$ so that $$bc \equiv 1 \pmod 9$$ and $$b + c \equiv a \pmod 9$$. I'm finding that $$b+c$$ is congruent to either $$2$$ or $$7$$ (i.e. $$-2$$) mod $$9$$ for the first few cases, but I'm not sure how to prove this for all cases to solve the problem.

Am I going in the correct direction?

• This seems promising! Try using the fact that the polynomial factors (mod 9) precisely when its discriminant is a square (mod 9) (by the quadratic formula). Commented Jul 7 at 22:01
• You can brute force. Commented Jul 7 at 23:14
• Hint: $\!\bmod 9\!: \color{#0a0}{f(r)}\equiv 0\Rightarrow 0\equiv f(r\!+\!3j) = \color{#0a0}{f(r)}+3j(\color{#c00}{2r\!+\!a}),\,$ by $\!\bmod 3\!:\, f(r)\equiv 0\Rightarrow \color{#c00}{r\equiv a},\,$ so $\,3\mid \color{#c00}{2r+a}.\,$ This will become clearer if you study Hensel's Lemma. Commented Jul 7 at 23:36
• COMMENT.-It is clear that for $a=\pm2$ we factorice $f(x)=(x\pm1)^2$ and because $$(x+1)^2\equiv(x+4)(x+7)=x^2+11x+28\pmod9$$ which give that for $x=8,5,2$ one has $f(x)=0$.Your claim is there are three values and not only three. You can show this if you want. Commented Jul 8 at 0:19

All congruences in this answer are modulo $$9$$. Completing the square,

$$x^2+ax+1\equiv0\iff\left(x+\frac a2\right)^2\equiv\frac{a^2}4-1\iff(2x+a)^2\equiv a^2-4$$.

Squares are $$0^2\equiv0, (\pm1)^2\equiv1, (\pm2)^2\equiv4, (\pm3)^2\equiv0$$, and $$(\pm4)^2\equiv-2$$,

so, if $$a^2-4$$ is a square, then $$a^2\equiv4$$, i.e., $$a\equiv\pm2$$.

Furthermore, $$\left(x+\frac a2\right)^2\equiv0$$, which means $$(x+1)^2\equiv0$$ if $$a\equiv2$$, and $$(x-1)^2\equiv0$$ if $$a\equiv-2$$.

I.e., $$x+1\equiv0$$ or $$\pm3$$ if $$a\equiv2$$, and $$x-1\equiv0$$ or $$\pm3$$ if $$a\equiv-2$$.

Hence, if $$x^2+ax+1$$ factors, then there are three solutions to $$x^2+ax+1\equiv0$$.

• i.e. completing the square (mod quadratic formula) shows $\!\bmod 9\!:\ f\equiv (x\!-\!u)^2,\, u\equiv \pm1,\,$ so $\!\!\mod 9\!:\ f(n)\equiv 0\!\iff\! 3^2\mid(n\!-\! u)^2\!\!$ $\iff\! 3\mid n\!-\!u\!$ $\iff\! n\equiv u,\,u\!+\!3,\,u\!+\!6\pmod{\!9}\ \$ Commented Jul 9 at 3:47
• My answer explains/proves OP's finding that $b+c$ is congruent to either $2$ or $7$ (i.e., $−2$) mod $9$ Commented Jul 10 at 1:22

Assume that $$f(x)\equiv (x-b)(x-c)\pmod9.$$ You already observed that $$bc\equiv1\pmod9$$, so also $$bc\equiv1\pmod3$$. It follows that $$b$$ and $$c$$ must congruent to each other modulo three. For otherwise one of them is divisible by three, or one is congruent to $$+1$$ and the other to $$-1$$, but in both those cases $$bc\not\equiv1\pmod3$$.

So if $$n$$ is any integer congruent to both $$b$$ and $$c$$ modulo three, both factors, $$n-b$$ and $$n-c$$, are divisible by three. Consequently $$f(n)$$ is divisible by nine.

There are three integers $$n$$ in the range $$0\le n\le8$$ congruent to $$b$$ modulo three, so the claim follows.

• Duplicate of my answer yesterday (see also my comment on J.W.T's answer). $\ \$ Commented Jul 9 at 16:20

Key Idea $$\!\!$$ if $$f(x)$$ has a root $$\,x\equiv \color{0}b \pmod {\!p^2}\:\!$$ that's $$\rm\color{#c00}{repeated}$$ $$\!\bmod{p},\,$$ i.e. $$\,\color{#c00}{f'(b)\equiv 0}\pmod{\!p},\,$$ then it lifts to $$\,p\,$$ roots $$\,x\equiv b,\,b\!+\!\color{#0af}p,\,b\!+\!\color{#0af}{2p},\ldots \pmod{\!p^2}\,$$ since, by Taylor's Theorem $$\bmod p^2\!:\ f(b\!+\!\color{#0af}{kp})\equiv f(b)+\color{#c00}{f'(b)}\,kp\equiv f(b)\equiv 0,\,\ {\rm by}\,\ \color{#c00}{p\mid f'(r)}\ \$$

OP root $$\rm\color{#c00}{repeats}\bmod 3\,$$ by $$\,x^2\!+\!ax\!+\!1 \equiv (x\!-\!b)(x\!-\!b^{-1})\,$$ so $$\, b\not\equiv 0\Rightarrow b\equiv \pm1\Rightarrow b^{-1}\equiv b,\,$$ thus repeated root $$\,x\equiv b\pmod{\!3}\,$$ lifts to $$\:\!3\:\!$$ roots $$\,b,\,b\!+\!\color{#0af}3,\,b\!+\!\color{#0af}6 \pmod{\!3^2}$$. $$\bf\small \ QED$$

Below is an alternative direct proof. See Hensel Lifting for generalizations of the above.

$$\!\bmod 9\!:\ f(x)\equiv (x\!-\!b)(x\!-\!c)\,\Rightarrow\, \bmod 3\!:\ bc\equiv\overbrace{f(0)\equiv 1}^{\rm hypothesis}\,$$ $$\Rightarrow \color{#c00}{\overbrace{b\equiv c}^{\rm repeated}}\,(\equiv \pm1),\,$$ so by the Lemma: $$\,f(n)\equiv 0\pmod{\!9}^{\phantom{|^{|^|}}}\!\!\!\!\!$$ $$\iff\! n\equiv b\pmod{\!3}\!$$ $$\iff\! n\equiv b,\,b\!+\!\color{#0af}3,\,b\!+\!\color{#0af}6\pmod{\!9}$$.

Lemma $$\$$ If $$\,f(x)\equiv (x\!-\!b)(x\!-\!c)\,\pmod{\!p^2}\$$ and $$\,p\,$$ is prime then

$$f(n)\equiv 0\!\!\!\pmod{\!p^2} \iff \begin{cases} n\equiv b\ \ \ \,\pmod{\!p}, & {\rm if}\ \ \color{#c00}{p\mid b\!-\!c \ \rm\ \, (repeats)} \\[.3em] n\equiv b,\color{#0af}c\pmod{\!p^2}, & {\rm if}\ \ \color{darkorange}{p\nmid b\!-\!c}\\ \end{cases}\!\!\!\!\!\!$$

Proof $$\$$ Note that $$\, p\mid p^2\mid f(n)\!=\!(n\!-\!b)(n\!-\!c)\:\!$$ $$\overset{p\ \rm prime}\Longrightarrow\:\! p\mid n\!-\!b\$$ or $$\ p\mid n\!-\!\color{#0af}c$$.
$${\rm If}\,\ n=\overbrace{p\color{}k\!+\!b\,\ \rm then}^{\,\textstyle {\rm pk\!\color{#0af}{+\!c}\,\ \rm same}}$$ $$\,p^2\mid f(n)\!=\!p\color{darkorange}k\,(pk\!+\!\color{#c00}{b\!-\!c})\!\!\underset{p\ \rm prime\!\!\!}\iff\, \color{#c00}{p\mid b\!-\!c}\!\!\underbrace{\ {\rm or}\ \ \color{darkorange}{p\mid k}}_{n\,\equiv\, b\!\pmod{\!p^2}}$$

• The proof needs only $\,f(0)\equiv 1\pmod{\!3},\,$ not $\,f(0)=1.\ \$ Commented Jul 9 at 0:27
• @Jyrki But my claim $\!\bmod 3\!:\ bc\equiv 1\Rightarrow \color{#c00}{b\equiv c}\,$ is obvious: $\,b,c\not\equiv 0\,$ so $\,b,c\equiv \,1,1\,$ or $\,−1,−1.\,$ That's no excuse to essentially duplicate this answer (in less generality). The point of abstracting out the Lemma is that it highlights how $\,\color{#c00}{b\equiv c}\,$ governs the general case for any prime $\,p,\,$ an insight (not "muddying") that is destroyed by eliminating the Lemma as you do. $\ \$. Commented Jul 9 at 19:52
• @Jyrki I expanded the answer to show the more general ideal I sought to highlight, i.e. I suspect that the point of this exercise is to concretely illustrate exceptional cases in Hensel lifting. Commented Jul 10 at 19:07
• May be? That is certainly in the spirit of the site. I simply felt that the special property of $p=3$ (the product of two elements $=1$ if and only if they are equal and non-zero) was the intended key. And the fact that the product of two integers or residue classes is divisible by $p^2$ when both are multiples of $p$ was the "trivial" ingredient. Hard to tell for sure, but I do see your point. Commented Jul 11 at 7:00

Write the equation as

$$(x+b)^2 = b^2-1$$

with $$b = \frac{a}{2}$$. Now the ring $$\mathbb{Z}/9$$ has the property that any square of the form $$b^2-1$$ is $$0$$. We get $$(x+b)^2=0$$, which has $$3$$ solutions.

$$\bf{Added:}$$ The squares in $$\mathbb{Z}/9$$ are $$0$$, $$1$$, $$4$$, $$7$$, so no square can be decomposed non-trivially as a sum of two squares, hence the above.

• Duplicate of J.W.T's answer (but skipping all the work - cf. my comment there), $\ \$ Commented Jul 9 at 20:02