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.
-
$\begingroup$ 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. $\endgroup$– dxivCommented May 28, 2023 at 2:19
-
$\begingroup$ 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? $\endgroup$– Tanishq KumarCommented May 28, 2023 at 2:20
-
$\begingroup$ Because you know you can always carry out the euclidean division, but you cannot factor arbitrary polynomials unless you are very very lucky. $\endgroup$– dxivCommented May 28, 2023 at 2:21
-
$\begingroup$ @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. $\endgroup$– Bill DubuqueCommented May 28, 2023 at 14:21
-
2$\begingroup$ 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). $\endgroup$– Bill DubuqueCommented May 28, 2023 at 14:26
2 Answers
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}$
-
$\begingroup$ We used a fraction-free way to evaluate $\,b^k f(a/b)\,\bmod\, bn\!-\!a\,$ (I can elaborate if need be). $\ \ $ $\endgroup$ Commented May 28, 2023 at 3:22
-
1$\begingroup$ Don't you think this question is probably a duplicate, Bill? $\endgroup$ Commented May 28, 2023 at 3:52
-
1$\begingroup$ @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). $\endgroup$ Commented May 28, 2023 at 4:12
-
$\begingroup$ Maybe math.stackexchange.com/questions/3714351/… ? But if you couldn't find one, it's probably not there. $\endgroup$ Commented May 28, 2023 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) $$
