I'm learning some elementary number theory, and seek integers $n$ for which $\frac{n^3 – 3n^2 + 4}{2n-1}$ is an integer. My instinct was to let such an integer be denoted by $k$ and get the condition $n^3 – 3n^2 – 2kn + (4+k)=0$ then try to factorize to get a condition on $n$. However, I couldn't see how to factorise. In the solutions, instead, they start by observing that multiplying the fraction by $8$ means its still an integer, and seeing that $8 \cdot \frac{n^3 – 3n^2 + 4}{2n-1} = 4n^2 – 10n -5 + \frac{27}{2n-1}$ and checking when $2n-1$ divides $27$. My question is: why was my instinct to factorize incorrect, and how on Earth would one think to observe that multipling by eight still gives an integer. I understand their solution, I'm particularly looking for motivation or a perspective that makes their approach obvious so I can apply similar techniques in future.
Checking when quotient of polynomials is integer
divisibilityelementary-number-theoryfactoringproblem solving
Related Solutions
This may not be as simple as hoped, but it is pure Bezout.
We will use a couple of the results proven in this answer: $$ (ac,bc)=c(a,b)\tag{1} $$ and $$ (a,b)=1\quad\text{and}\quad(a,c)=1\implies(a,bc)=1\tag{2} $$ Furthermore, since $(a,b)\mid a$ and $(a,b)\mid bc$, we have $$ (a,b)\mid(a,bc)\tag{3} $$
Lemma 1: If $(a,b)=1$, then $$ \begin{align} 1.&(a,n)(b,n)\mid n\\ 2.&(a+b,a^mb^n)=1 \end{align} $$ Proof: Suppose that $(a,b)=1$. Then for some $x,y$ we have $$ ax+by=1\tag{4} $$ Thus, we have $$ \begin{align} n &=n(ax+by)\\ &=\left(\frac{n}{(b,n)}\frac{ax}{(a,n)}+\frac{n}{(a,n)}\frac{by}{(b,n)}\right)(a,n)(b,n)\tag{5} \end{align} $$ and therefore, we conclude that $$ (a,n)(b,n)\mid n\tag{6} $$ Furthermore, from $(4)$, we also have $$ \begin{align} 1&=a(x-y)+(a+b)y&&(4)-ay+ay\tag{7}\\ 1&=(a+b)x+b(y-x)&&(4)+bx-bx\tag{8}\\ \end{align} $$ $(7)$ and $(8)$ say that $(a+b,a)=1$ and $(a+b,b)=1$. Repeatedly applying $(2)$ yields $$ (a+b,a^mb^n)=1\tag{9} $$ $\square$
Lemma 2: $$ \left(a,\frac{n}{(a^n,n)}\right)=1 $$ Proof: Since $(a^k,n)\mid(a^{k+1},n)\mid n$, we must have, for some $k\le n$, that $(a^{k+1},n)=(a^k,n)$.
Suppose that $(a^{k+1},n)=(a^k,n)$. Then $\left(a\frac{a^k}{(a^k,n)},\frac{n}{(a^k,n)}\right)=1$ and therefore, $\left(a,\frac{n}{(a^k,n)}\right)=1$.
Since $k\le n$, we have $(a^k,n)\mid(a^n,n)$, and consequently, $$ \left(a,\frac{n}{(a^n,n)}\right)=1\tag{10} $$ $\square$
Theorem: If $(a,b)=1$, then $$ \left(a+\frac{nu}{(a^n,n)(b,n)}b,n\right)=1 $$ where $u$ satisfies $(b,n)=bu+nv$.
Proof: Suppose that $(a,b)=1$ and $(b,n)=bu+nv$. Using $(2)$ repeatedly, we get $$ (a^n,b)=1\tag{11} $$ Combining $(6)$ and $(11)$ yield $$ (a^n,n)(b,n)\mid n\tag{12} $$ Thus, $\dfrac{n}{(a^n,n)(b,n)}\in\mathbb{Z}$ and $(10)$ says that $$ \left(a,\frac{n}{(a^n,n)(b,n)}(b,n)\right)=1\tag{13} $$ $(9)$ and $(13)$ imply that $$ \left(a+\frac{n}{(a^n,n)(b,n)}(b,n),a^n\frac{n}{(a^n,n)(b,n)}(b,n)\right)=1\tag{14} $$ Since $(a^n,n)\mid a^n$, we have $\left.n\,\middle|\,a^n\dfrac{n}{(a^n,n)(b,n)}(b,n)\right.$, so using $(3)$ and $(14)$ yields $$ \left(a+\frac{n}{(a^n,n)(b,n)}(b,n),n\right)=1\tag{15} $$ The rest is Bezout. $(15)$ says that there are $x,y$ so that $$ \left(a+\frac{n}{(a^n,n)(b,n)}(b,n)\right)x+ny=1\tag{16} $$ Furthermore, since $(b,n)=bu+nv$, we get $$ \left(a+\frac{nu}{(a^n,n)(b,n)}b\right)x+n\left(y+\frac{nv}{(a^n,n)(b,n)}\right)=1\tag{17} $$ which just says that $$ \left(a+\frac{nu}{(a^n,n)(b,n)}b,n\right)=1\tag{18} $$ $\square$
A note on application
At first, $(18)$ may seem like a theoretical answer in the sense that it shows that we can find a $k$ so that $(a+bk,n)=1$, but computationally, it might appear a bit daunting due to the appearance of $(a^n,n)$ in the denominator. However, $n/(a^n,n)$ is simply $n$ with all the factors common to $a$ removed. To compute $n/(a^n,n)$, we can start with $n_0=n$, and generate the sequence $$ n_{k+1}=\frac{n_k}{(a,n_k)}\tag{19} $$ at some point $(a,n_k)=1$. For that $k$, we have $$ \frac{n}{(a^n,n)}=n_k\tag{20} $$
The arithmetic has been explained. I explain how to eliminate such hairy error-prone arithmetic by replacing the painful back-substitution with simpler forward-computation of the Bezout identity using row-operations. Using the verson of the Extended Euclidean Algorithm described here yields
$$\begin{array}{rrr} x^5+1 & 1 & 0\\ x^3+1 & 0 & 1\\ x^2+1 & 1 & x^2\\ x+1 & \color{#c00}x & \color{#0a0}{x^3+1}\\ 0 & \ldots & \ldots \end{array}$$
where above lines $\,\ a\ \ b\ \ c\ \,$ mean $\ a = b(x^5+1) + c(x^3+1).\ $ So the Bezout identity is
$$ x+1 \,=\, \color{#c00}{x}(x^5+1)+ (\color{#0a0}{x^3+1})(x^3+1)\quad $$
The linked post describes the algorithm in great detail, in a way that is easy to remember.
Here is another example computing $\rm\ gcd(141,19),\,$ with the equations written explicitly
$$\rm\begin{eqnarray}(1)\quad \color{#C00}{141}\!\ &=&\,\ \ \ 1&\cdot& 141\, +\ 0&\cdot& 19 \\ (2)\quad\ \color{#C00}{19}\ &=&\,\ \ \ 0&\cdot& 141\, +\ 1&\cdot& 19 \\ \color{#940}{(1)-7\,(2)}\, \rightarrow\, (3)\quad\ \ \ \color{#C00}{ 8}\ &=&\,\ \ \ 1&\cdot& 141\, -\ 7&\cdot& 19 \\ \color{#940}{(2)-2\,(3)}\,\rightarrow\,(4)\quad\ \ \ \color{#C00}{3}\ &=&\, {-}2&\cdot& 141\, + 15&\cdot& 19 \\ \color{#940}{(3)-3\,(4)}\,\rightarrow\,(5)\quad \color{#C00}{{-}1}\ &=&\,\ \ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \end{eqnarray}\qquad$$
Best Answer
Easy general way: $ $ via a $ $ fractional $ $ generalization of the polynomial remainder / factor theorems. If $\,a,b,n,m\,$ are integers and $\,f(x)\,$ is a polynomial with integer coefficients then
$$\begin{align}\,n\!-\!a\mid f(n) &\iff \ \ n\!-\!a\mid f(a),\ \ \ {\rm by}\ \ \ f(n)\equiv f(a)\!\pmod{\!n\!-\!a}\\[.6em] \leadsto\ \ bn\!-\!a\mid f(n) &\iff bn\!-\!a\mid b^k f\left(\frac{a}b\right),\ \ {\rm if}\ \ \color{#90f}{(a,b)=1},\ \ k\ge \deg f \end{align}\qquad\qquad$$
since $\,(bn\!-\!a,b) = \color{#90f}{(-a,b)}=1,\ $ so $\ bn\!-\!a\mid b^k m \iff bn\!-\!a\mid m,\,$ by Euclid's Lemma.
so $\,2n\!-\!1\mid n^3\!-\!3n^2\!+\!4 \iff \color{#0a0}{2n}\!-\!\color{#c00}1\mid 2^3(n^3\!-\!3n^2\!+\!4) = \underbrace{(\color{#0a0}{2n})^3\!-\!6(\color{#0a0}{2n})^2\!+\!32}_{\large\equiv\ \color{#c00}1^3-6(\color{#c00}1)^2+32\ \equiv\ 27}$