Integer division problem

Question

I'm trying to solve the following problem:

For any positive integer $a$, find the least positive integer $n$ for which the formula below produces an integer result

$$\frac {a-n}{2n+1}$$

except for the trivial solutions with $n$ being $0$ or $a$.

I'm a beginner in discrete math, so I'm clueless from which direction to approach this problem in order to solve it.

Note that such a positive integer $n$ does not exist for all positive integers $a$. — Servaes, Mar 24 '14 at 16:55
@labbhattacharjee Thanks. As I understand it, the piece within curly brackets is a set that is the left part of an equation, right? But I still cannot see what should I do to find the $n$ for a given $a$. Would you please be so kind to explain the process? — Desmond Hume, Mar 24 '14 at 18:15
@DesmondHume, I meant $$2(a-n)+2n+1=2a+1$$ will be divisible by $2n+1$ — lab bhattacharjee, Mar 24 '14 at 18:16

Bill Dubuque · Accepted Answer · 2014-03-24T18:42:54.957

1

Hint $\ {\rm mod}\ 2n\!+\!1\!:\,\ 2n\equiv-1\,\Rightarrow\, \color{#c00}{n\equiv -\dfrac{1}2}\ \, $ so $\ \ 0\equiv a\!\color{#c00}{-\!n} \equiv a+\color{#c00}{\dfrac{1}2}\overset{\large\rm\ \times\ 2}\iff 0\equiv 2a\!+\!1$

Alternatively if modular fractions are unfamilar we can scale the above by $2$ yielding

$\qquad\ {\rm mod}\ 2n\!+\!1\!:\,\ \color{#c00}{2n\equiv -1},\ \ 0\equiv a-n\overset{\rm\large times\ 2}\iff 0\equiv 2a\color{#c00}{-2n}\equiv 2a\color{#c00}{+1}$

The reverse direction $\,(\Leftarrow)\,$ arises by scaling by $\,\color{#c00}{2^{-1}\equiv -n}.$

Alternatively if congruences are unfamiliar, rewriting the above using divisibility

$$\ 2n\!+\!1\mid a\!-\!n\color{#c00}\iff 2n\!+\!1\mid 2(a\!-\!n)\iff 2n\!+\!1\mid 2(a\!-\!n)+(2n\!+\!1) = 2a+1$$

because $\ 2n\!+\!1\mid \color{#0a0}{2k}\,\color{#c00}\Rightarrow\, 2n\!+\!1\mid k = -\color{#0a0}{2k}n + k(2n\!+\!1),\,$ or, since $\,2n\!+\!1\,$ and $\,2\,$ are coprime, therefore $\,2^{-1}\,$ exists mod $\,2n\!+\!1.$

edited Mar 24 '14 at 18:42

answered Mar 24 '14 at 17:02

Bill Dubuque

272,048

Thank you for this info, but as a beginner I'm having hard time grasping it. Could please help me derive the actual solution, perhaps an algorithmic one? – Desmond Hume Mar 24 '14 at 18:04
@Desmond By the above $,2n!+!1,$ divides $,a!-!n,$ iff it divides $,2a+1,,$ so it amounts to finding the least proper divisor of $,2a+1,,$ i.e. its least prime factor (necessarily odd). If you tell me specifically which parts are not clear then I can elaborate. – Bill Dubuque Mar 24 '14 at 18:10
And is there an efficient way of finding the least prime factor of an arbitrary number? – Desmond Hume Mar 24 '14 at 18:23
@Desmond That's equivalent to integer factorization, which is generally quite hard. – Bill Dubuque Mar 24 '14 at 18:28
Great explanations. Thanks again. Not being able to find a solution is a huge bummer though.. – Desmond Hume Mar 24 '14 at 18:44

Integer division problem

1 Answers1