# Checking when quotient of polynomials is integer

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.

• Idea is to do the long division between the two polynomials, which leaves a fraction with the remainder in the numerator, which is a constant. Multiplying by $8$ makes the calculations easier, but is not required.
– dxiv
May 28 at 2:19
• And why is thinking to bash the long division a better idea than factorizing in the way I described? Because we literally can't factorize (easily) here? May 28 at 2:20
• Because you know you can always carry out the euclidean division, but you cannot factor arbitrary polynomials unless you are very very lucky.
– dxiv
May 28 at 2:21
• @dxiv Yes, (polynomial) euclidean division (with remainder) is the key idea. This special case (division by a linear polynomial $\,x-c)\,$ is so important it has a name, viz. the Polynomial Remainder Theorem, i.e. $\,f(x)\bmod x-c = f(c).\,$ Choosing $\,c = 1/2\,$ then scaling to get integer divisibilities we can easily solve the OP, e.g. as in my answer. May 28 at 14:21
• Beware that $\,a\mid 8b\Rightarrow a\mid b\,$ is true $\iff (a,8)=1\iff (a,2)=1,\,$ i.e. $\,a\,$ is odd. Many arguments omit this crucial step (which is essential in the OP). May 28 at 14:26

I'm particularly looking for motivation or a perspective that makes their approach obvious so I can apply similar techniques in future.

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

• We used a fraction-free way to evaluate $\,b^k f(a/b)\,\bmod\, bn\!-\!a\,$ (I can elaborate if need be). $\ \$ May 28 at 3:22
• Don't you think this question is probably a duplicate, Bill? May 28 at 3:52
• @Gerry Maybe, but I didn't have any luck searching (and I spent quite some time). I need to figure out some better keywords to facilitate searching on problems like this. If you know some good targets then please do share them. I'll delete this if I later find a good target (as I ususally do in cases like this). May 28 at 4:12
• Maybe math.stackexchange.com/questions/3714351/… ? But if you couldn't find one, it's probably not there. May 28 at 9:19

Well, if the fraction is an integer, the GCD of numerator and denominator is large.... the outcome of extended GCD is, after multiplying by 27,

$$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$

$$8 \left( x^{3} - 3 x^{2} + 4 \right) - \left( 2 x - 1 \right) \left( 4 x^{2} - 10 x - 5 \right) = 27$$ then divide through by $$(2x-1)$$ to get to your $$\frac{27}{2x-1}$$

$$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$

$$\left( x^{3} - 3 x^{2} + 4 \right)$$

$$\left( 2 x - 1 \right)$$

$$\left( x^{3} - 3 x^{2} + 4 \right) = \left( 2 x - 1 \right) \cdot \color{magenta}{ \left( \frac{ 4 x^{2} - 10 x - 5 }{ 8 } \right) } + \left( \frac{ 27}{8 } \right)$$ $$\left( 2 x - 1 \right) = \left( \frac{ 27}{8 } \right) \cdot \color{magenta}{ \left( \frac{ 16 x - 8 }{ 27 } \right) } + \left( 0 \right)$$ $$\frac{ 0}{1}$$ $$\frac{ 1}{0}$$ $$\color{magenta}{ \left( \frac{ 4 x^{2} - 10 x - 5 }{ 8 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 4 x^{2} - 10 x - 5 }{ 8 } \right) }{ \left( 1 \right) }$$ $$\color{magenta}{ \left( \frac{ 16 x - 8 }{ 27 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 8 x^{3} - 24 x^{2} + 32 }{ 27 } \right) }{ \left( \frac{ 16 x - 8 }{ 27 } \right) }$$ $$\left( x^{3} - 3 x^{2} + 4 \right) \left( \frac{ 8}{27 } \right) - \left( 2 x - 1 \right) \left( \frac{ 4 x^{2} - 10 x - 5 }{ 27 } \right) = \left( 1 \right)$$