5
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ 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). $\endgroup$ Commented Jul 7 at 22:01
  • 1
    $\begingroup$ You can brute force. $\endgroup$ Commented Jul 7 at 23:14
  • $\begingroup$ 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. $\endgroup$ Commented Jul 7 at 23:36
  • $\begingroup$ 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. $\endgroup$
    – Piquito
    Commented Jul 8 at 0:19

4 Answers 4

1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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}\ \ $ $\endgroup$ Commented Jul 9 at 3:47
  • $\begingroup$ My answer explains/proves OP's finding that $b+c$ is congruent to either $2$ or $7$ (i.e., $−2$) mod $ 9$ $\endgroup$ Commented Jul 10 at 1:22
1
$\begingroup$

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.

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

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}}$

$\endgroup$
4
  • $\begingroup$ The proof needs only $\,f(0)\equiv 1\pmod{\!3},\,$ not $\,f(0)=1.\ \ $ $\endgroup$ Commented Jul 9 at 0:27
  • $\begingroup$ @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. $\ \ $. $\endgroup$ Commented Jul 9 at 19:52
  • $\begingroup$ @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. $\endgroup$ Commented Jul 10 at 19:07
  • $\begingroup$ 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. $\endgroup$ Commented Jul 11 at 7:00
0
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .