0

How can i prove if a $\frac{c-xk}{a+xr}$ has a positive integer solution when r,c,a and k are given ? For example, $\frac{115-11x}{2+13x}$ has a solution in positive integer ranging 2..3, while $\frac{109-10x}{10+13x}$ has no integer solution.Something like proving a Diophantine equation has an integer solution.

Could someone illustrate with proper examples please?

D. Sikilai
  • 92
  • 5
    What do you mean with solution of a simple expression? – Hagen von Eitzen Jun 23 '18 at 15:38
  • You've written two expressions, not two equations. An expression can be simplified, but not "solved". – amWhy Jun 23 '18 at 16:04
  • OP used a short form, like $x^2$ for a norm parabola $y = x^2$. This interpretation fits the Diophantine equations tag and the statements about the examples and their solutions. – mvw Jun 23 '18 at 18:10
  • Equation (c-xk)/(r+xk) may or may not have a solution in integer where c,k and r are given. I am actually stack in proving(not solving) the condition necessary for the two instances.Thanks in advance. – D. Sikilai Jun 26 '18 at 15:10

1 Answers1

1

1. Reformulation as solution of a quadratic Diophantine equation:

We have $$ y = \frac{c - k x}{a+r x} \iff \\ (a+r x) y =c -kx \iff \\ r xy + kx + ay = c \quad (*) $$ assuming $r, k, a, c$ are integers, this is a special case of the quadratic Diophantine equation: $$ A x^2 + B xy + C y^2 + Dx + E y + F = 0 $$ Your example with solutions $$ y = \frac{115-11x}{2+13x} \iff \\ 13xy+11x+2y-115 = 0 $$ has $A=0$, $B=13$, $C=0$, $D=11$, $E=2$, $F=-115$ as coefficients.

2. General solution:

I put the coefficients in Dario Alpern's Generic Two integer variable equation solver and got solutions and explanations.

You might try it as well, selecting the "Step-by-step" option for "Modes".

He also provides an explanation of the general method here:

3. Solution for the special case (*):

For our equation $(*)$ we got the Simple Hyperbolic case $A=C=0; B\ne 0$ explanation.

Before this step, the greatest common divisior of the non-constant coefficients $g = \gcd(r, k, a)$ is determined, and if $g \not\mid c$ then no integer solutions exist. For the example we have $g=1$ and solutions might exist.

Otherwise the equation is normalized by dividing both sides of the equation by $g$. (Instead of $r' = r/g$ etc, we are lazy and keep using $r$ etc). For the example this is not needed.

$$ r x y + k x + a y = c \iff \\ r^2 x y + r k x + r a y = r c \iff \\ r^2 x y + r k x + r a y + k a = k a + rc \iff \\ (r x + a) (r y + k) = k a + rc $$

If the RHS vanishes, one has two lines, one parallel to the $x$-axis, one parallel to the $y$-axis, as solutions over the real numbers.

Otherwise a hyperbola results as solution over the reals. This case we have for the example: $$ (13 x + 11)(13 y + 2) = 1517 $$

Here the approach is then to find the divisors for the RHS $$ d \mid ka + rc $$ and checking the pairs $$ r x + a = d \quad r y + k = (k a + r c) / d \iff \\ x = \frac{d - a}{r} \quad y = \frac{(k a + r c) / d - k}{r} $$ for integer solutions.

4. Solution for the example with integer solutions:

For the example we have $$ d \mid 1517 = 37 \cdot 41 \iff \\ \lvert d \rvert \in \{ 1, 37, 41, 1517 \} $$ and the solution candidates: $$ x = \frac{d - 2}{13} \quad y = \frac{1517/d-11}{13} $$ The positive solution exists for $d = 41$: $$ x = 3 \quad y = 2 $$

5. Solution for the example without integer solutions:

$$ y = \frac{109-10x}{10+13x} \iff \\ 13 x y + 10 x + 10 y = 109 \iff \\ (13 x + 10)(13 y + 10) = 1517 = 37 \cdot 41 $$ Again we have $g=1$ and the divisors $$ d \mid 1517 = 37 \cdot 41 \iff \\ \lvert d \rvert \in \{ 1, 37, 41, 1517 \} $$ and here the solution candidates are $$ x = \frac{d - 10}{13} \quad y = \frac{1517/d-10}{13} $$ where no integer solution is among the candidates.

mvw
  • 34,562