$(2x + 1)(3x + 1) \equiv 0\pmod{\!n}$ has a root for all $n ≥ 2$

Question

I have a feeling that induction might be necessary since the question includes "for every integer $n ≥ 2$".

So with this in mind, the base case would be $n=2$. If $(2x+1)(3x+1)\equiv0\pmod 2$, then $x=1$ is a solution because $12\equiv 0\pmod 2$ is a true statement.

For the inductive step, we assume that $$(2x+1)(3x+1)\equiv0\pmod{k}$$ and we need to show that $$(2x+1)(3x+1)\equiv 0\pmod{ (k+1)}.$$ I'm unsure what to do from here.

Answer 1

Here is a solution without induction on $n$. Let $n=2^am$ with $m$ odd. Then $2^a$ is not a multiple of $3,$

so $2^a-1$ or $2^{a+1}-1$ is a multiple of $3, $ and $x=\dfrac{2^a-1}3$ or $x=\dfrac{2^{a+1}-1}3 $ is a solution$\mod 2^a$.

Also, $x=\dfrac{m-1}2$ is a solution $\mod m$.

Therefore, by the Chinese remainder theorem, there is a solution $\mod n$.

Answer 2

Theorem $\ f(x)= (ax\!+\!1)(bx\!+\!1)\ $ has a root $\!\bmod n\,$ for all $\,n\!>\!1\!\iff\! (a,b) = 1$

Proof $\ (\Rightarrow)\ $ if $\,1 < c\mid a,b\,$ then $\!\bmod c\!: f(x)\equiv 1\not\equiv 0.\,$ $(\Leftarrow)\,$ Factor $\,n = a'b'$ where $\,b'\,$ collects all prime factors of $\,n\,$ that divide $\,a,\,$ so $\,1 \!=\! (a,a'),\,$ and $\,1 \!=\! (b,b') = (a',b'),\,$ by $\,(a,b)\!=\!1,\,$ so $\,\color{#0a0}{ax\!+\!1}\,$ has root $\,\color{#0a0}{x\equiv -a^{-1}\!\pmod{\!a'}}\,$ and $\,\color{#c00}{bx\!+\!1}\,$ has root $\,\color{#c00}{x\equiv -b^{-1}\!\pmod{\!b'}}.\,$ Therefore $\,f(x)\!=\!(\color{#0a0}{ax\!+\!1})(\color{#c00}{bx\!+\!1})\,$ has a root $\!\color{#0a0}{\bmod a'}\,$ & $\!\color{#c00}{\bmod b'},\:\!$ which CRT lifts to a root $\!\bmod \color{#0a0}{a'}\color{#c00}{b'}\!=\!n$.

Answer 3

Without CRT but EL.

Let $n=2^km$ where $m$ is odd.

Since $\gcd(2,m)=1$ $\exists t_1,t_2\in\Bbb Z$ such that $2t_1+1=t_2m$.

Since $\gcd(3,2^k)=1$ $\exists s_1,s_2\in\Bbb Z$ such that $3s_1+1=s_22^k$.

Since $\gcd(m,2^k)=1$ $\exists u,v\in\Bbb Z$ such that $um+v2^k=1$.

Let $x=t_1+(s_1-t_1)um.$

Then $(2x+1)(3x+1)\equiv 0\pmod n.$