How can I find all the cases where y is positive integer in the next equation:
$$\frac{ax + b}{c-x} = y$$
- $a,b,c,x$ are not negative integers
- $a,b,x < c$
- $ax + b = 0$ is a trivial solution
Asked
Active
Viewed 277 times
1
Ilya Gazman
- 1,440
-
1A good place to begin is to show us what you've already tried! – daOnlyBG Jan 19 '15 at 17:50
-
@daOnlyBG this equation is part of a bigger project that I am working on, this is the most encapsulated version of my problem that I can ask. I really have no idea how to address this issue. I been googeling a lot, and I found that "Diophantine equation" could be relevant, but I don't see how can I use it. So if all what you have its an idea, that works too. – Ilya Gazman Jan 19 '15 at 17:54
-
That's fair, although I do have one question: if $AX+B=0$, how are $A,B,C,$ and $X$ positive integers? – daOnlyBG Jan 19 '15 at 18:03
-
@daOnlyBG sorry I meant not negative. – Ilya Gazman Jan 19 '15 at 18:08
-
@AndréNicolas rewriting $xy+ax-cy=-b$ will give: $(x-c)(y+a)=-b-ac$. May be I did not mention this in the question, but I know what $A,B,C$ are. I only need to find such $X$ that will give me integer $Y$. – Ilya Gazman Jan 19 '15 at 20:32
-
@AndréNicolas Also this question is not supposed to be easy. Solving it will allow me to solve the integer factorization problem, this is part of my algorithm that I am building for it. – Ilya Gazman Jan 19 '15 at 20:35
-
If the intent is to build a factorization algorithm, then what I wrote is useless to you since it uses factorization. – André Nicolas Jan 19 '15 at 20:45
-
@AndréNicolas It only useless if it's as hard as the original factorization, and I think it is not. So may be, just may be, it could be the right direction, so what ever you got there: Bring it on! – Ilya Gazman Jan 19 '15 at 22:50
2 Answers
1
In accordance with the usual convention, we avoid caps, which make equations harder to solve.
We are looking for positive integer solutions $(x,y)$ of $$\frac{ax+b}{c-x}=y,$$ where $a$, $b$, $c$ are non-negative and $x\lt c$.
Equivalently, we want, together with the bound on $x$, $ax+b=cy-xy$, that is, $xy+ax-cy=-b$, that is, $(x-c)(y+a)=-ac-b$, which looks better if written as $$(c-x)(y+a)=ac+b.$$ To find all solutions, we factor $ac+b$ as $ac+b=uv$, where $1\le u\le c-1$ and $v\gt a$.
Finding non-trivial such factors (if there are any) may be computationally very difficult if $ac+b$ is large.
André Nicolas
- 507,029
-
Thanks. I went back to my usual way of looking at things, fewer opportunities for algebra mistakes. – André Nicolas Jan 20 '15 at 00:15
-
lols this is where I started. ac + b will be my original number that I want to factor. I thought that the way that I wrote it, will brings me close for solving it. – Ilya Gazman Jan 20 '15 at 04:09
-
It looks then as if the basic problem has been reworded, but not fundamentally changed. Perhaps the approach will yield fruit, but the two problems are quite close to each other, and I am not optimistic. – André Nicolas Jan 20 '15 at 04:17
-
-
You are welcome. A notoriously difficult problem, with a very large literature. – André Nicolas Jan 20 '15 at 04:46
