1
$\begingroup$

I had just solved this problem of Sierpinski

Prove that the sequence $2^n - 3, \; n = 2,3,4, \dots$ contains infinitely many terms divisible by $5$ and $13$ but no terms divisible by $5\cdot 13$.

For showing the existence of infinite terms divisible by $5$ and $13$ I basically applied Fermat's little theorem and some congruences.

Now for showing whether a term exists such that it is divisible by $65$ I thought of using the fact that if $a|b$ and $c | b$ and $gcd(a,c) = 1$ then $ac|b$. But for that, I would require to show that there is a common term divisible by both $5$ and $13$.

I finally found that values of $n$ satisfying $3 + 4k, \; k \in \mathbb{N}$ are divisible by $5$ and values of $n$ satisfying $4 + 12m, \; m \in \mathbb{N}$ are divisible by $13$. So now I have to prove that no $k$ and $m$ exist such that $3 + 4k = 4 + 12m$. This comes out to be:

$$4k - 12m = 1$$

Which is a linear diophantine equation. Now $gcd(4,12) \not\mid 1$ so no solution exists.

But I feel that doing it this way is wrong as $k, m \in \mathbb{N}$ but due to the $-$ (minus) sign in the equation negative values of $k$ and $m$ are also being considered.

So now coming to my main question, when are diophantine equations $ax + by = c$ and $ax - by = c$ equivalent and what are their differences?

P.S I did solve this without using the diophantine part by proving that no positive integers $k$ and $m$ exist such that $k - 3m = \frac{1}{4}$.

$\endgroup$
  • $\begingroup$ There is no reason why you can't use $k, m \in \mathbb Z$. $\endgroup$ – steven gregory May 3 at 23:08
1
$\begingroup$

No need to worry about signs $4k-12m$ is a multiple of $\gcd(4,12)=4$, while $1$ is not.

Edit: Let$a,b>0$.

Then, $ax+by=c$ is practically the same as $ax-by=c$ if $x,y\in\mathbb{Z}$ because if $(x',y')$ is a solution of the first one, then $(x',-y')$ is a solution for the other one.

Now, if you are just looking for $x,y\in\mathbb{N}$, then $ax+by=c$ will have a finite number of solutions, while $ax-by=c$ may have infinite solutions (note that if $(x',y')$ is a solution then $(x'+kb,y'+ka)$ is a solution)

$\endgroup$

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.