For the equation \begin{equation} a = \frac{n(4m-1)}{4b} \end{equation} where $n,m,a$ and $b$ are positive integers and $1\leq a,b\leq n$, how many valid, unique solutions $(a,m)$ exist for fixed $n$ and $b$? I am also interested in a weaker form of the question: what is the maximum number of solutions possible for any given $n$?

I understand that $n$ has to be divisible by 4, but I am unsure about the division by $b$ since it could be any integer from $1$ to $n$ and $m$ is a "free" parameter that does not have any constraints (besides being integer). Unfortunately, my handle on number theory is rather weak so I also don't know how to convert this information into finding the number of solutions.

  • $\begingroup$ Can you please clarify what would constant a solution? Like you want to know how many tuples(m,n,a) there are given a fixed b? $\endgroup$ – Corey Jul 14 '16 at 21:04
  • $\begingroup$ Let $n=4q$. If we forget about the condition $a\le n$, there is a solution if $b'=b/(\gcd(b,q)$ is odd. Now we need to worry about the condition $a\le n$. This gets somewhat messy, but one can produce an answer. $\endgroup$ – André Nicolas Jul 14 '16 at 21:22
  • $\begingroup$ @Corey, $n$ and $b$ are both fixed, I will edit my question to clarify; but yes, I am looking for how many tuples $(a,m)$ exist which satisfy the equation. $\endgroup$ – Banach space fan Jul 14 '16 at 21:34
  • $\begingroup$ @AndréNicolas, Thanks for the insight. I suppose my main question, though, is how do we go about determining how many such solutions exist (assuming we've determined the additional necessary conditions)? $\endgroup$ – Banach space fan Jul 14 '16 at 21:39

Since $n$ is a multiple of $4$, we might as well let $n=4q$ and we are looking at $ab=q(4m-1)$.

Temporarily let us not worry about the condition $a\le n=4q$. Then $m$ gives a solution precisely if $b$ divides $q(4m-1)$. Let $\gcd(b,q)=d$ and let $b=db'$, $q=dq'$. So we want $b'$ to divide $q'(4m-1)$, and therefore we want $b'$ to divide $4m-1$.

If $b'$ is even, there is no solution. So let $b'$ be odd. Then, without considering the condition $a\le n$, we have infinitely many solutions.

Now the condition $a\le n$ can be dealt with easily. If there is a solution, then $m$ gives a solution if and only if $4nb\ge n(4m-1)$, that is, if $4m-1\le 4b$. There are $b$ possibilities.

| cite | improve this answer | |

So, if I understood exactly you question, you are looking for the $(x,y)$ solutions to $$ \left\{ \begin{gathered} x = \frac{{n\left( {4y - 1} \right)}} {{4b}}\quad \Rightarrow \quad 4ny - 4bx = n \hfill \\ 0 \leqslant y \hfill \\ 1 \leqslant x,b \leqslant n \hfill \\ \end{gathered} \right. $$ which can be recasted as: $$ \left\{ \begin{gathered} z = x-1 \hfill \\ 4ny - 4bz = n + 4b \hfill \\ 0 \leqslant z \leqslant n-1 \hfill \\ 0 \leqslant y \hfill \\ 1 \leqslant b \leqslant n \hfill \\ \end{gathered} \right. $$ and which is a classical linear diophantine equation (in $y,z=x-1$), with non-negative solutions, and apart the upper-bond to z.
Then, as how to solve it you may refer to this other post.

| cite | improve this answer | |
  • $\begingroup$ I'm afraid I don't understand why $4b$ was added in the recasted formulation. Also, shouldn't the $1$ be $n$ instead? Thank you for the link though, I will check it out (and linear Diophantine equations in general). $\endgroup$ – Banach space fan Jul 14 '16 at 22:58
  • $\begingroup$ Sorry, the $1$ should have been $n$ indeed. Concerning the addition of $4b$, that was to bring $x$ to start from $0$ instead than from $1$. I changed the variable now to make that evident, and corrected the error. $\endgroup$ – G Cab Jul 14 '16 at 23:45
  • $\begingroup$ However you can keep with the first equation alone, but considering the bounds on $x$. $\endgroup$ – G Cab Jul 14 '16 at 23:52
  • $\begingroup$ +1 Great, thanks! I've accepted André's answer since his result is most immediately useful for my situation, but I do appreciate you showing me this solution method. $\endgroup$ – Banach space fan Jul 15 '16 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.