diophantine equationselementary-number-theory
Given positive integers a,b,c, how to find all positive integers m,n such that $an+b=cm$?
Is there always infinitely many m,n for all a,b,c?
If $(n_0, m_0)$ is the smallest solution, are all other solutions of the form $(n_0+ct, m_0+at)$ for some positive integer t?
There is such a solution if and only if both $k-1$ and $k+2$ have (well, different) integer expressions as some $u^2 + 3 v^2.$
The justification for that is in several answers I posted at
Find a solution: $3(x^2+y^2+z^2)=10(xy+yz+zx)$
$$ $$ $$ $$
Given $$ p^2 + 3 q^2 = 2 + k, $$ $$ r^2 + 3 s^2 = 4(k-1), $$ we can solve $$ (x^2 + y^2 + z^2) = k (yz + zx + xy) $$ with $$ x = 2 p^2 + 6 q^2 - p r - 3 p s + 3 q r - 3 q s, $$ $$ y = 2 p^2 + 6 q^2 - p r + 3 p s - 3 q r - 3 q s, $$ $$ z = 2 p^2 + 6 q^2 + 2 p r + 6 q s. $$
I did not immediately realize, the process of Vieta Jumping lets us take a mixed solution and create one with all the same $\pm$ sign. Suppose $x < 0,$ $y > 0,$ $z>0.$ We do a single jump: $$ x \mapsto k(y+z) - x, $$ where the new $x$ value is then positive!
The permissible values of your $k$ from 2 to 1000 are
2 5 10 14 17 26 29 37 50 62
65 74 77 82 98 101 109 110 122 125
145 149 170 173 190 194 197 209 226 242
245 257 269 290 302 305 314 325 334 362
365 398 401 410 434 437 442 469 482 485
497 509 514 530 554 557 577 590 602 605
626 629 674 677 685 689 701 722 725 730
770 773 785 794 830 842 845 869 874 890
901 917 962 965 973 974 989
These all lead to solutions $(a,b,c) $ where it may be that some variables are negative, some positive.
Let me work up some of the smallest such $k,$ see whether positive solutions appear.
$$ k = 17; \; \; \; (377,17,5) $$
$$ k = 26; \; \; \; (418,13,3) $$
$$ k = 29; \; \; \; (1109,11,27) $$
BY RECIPE .........................................
Mon Jul 6 19:11:55 PDT 2020
2 ( 1, 1 , 4 ) p 1 q 1 r 1 s 1
5 ( -1, 5 , 17 ) ( 111, 5 , 17 ) p 2 q 1 r 2 s 2
10 ( 2, -1 , 5 ) ( 2, 71 , 5 ) p 0 q 2 r 3 s 3
14 ( -1, 2 , 11 ) ( 183, 2 , 11 ) p 2 q 2 r 2 s 4
17 ( -13, 23 , 47 ) ( 1203, 23 , 47 ) p 4 q 1 r 4 s 4
26 ( 3, -2 , 13 ) ( 3, 418 , 13 ) p 1 q 3 r 5 s 5
29 ( -7, 11 , 89 ) ( 2907, 11 , 89 ) p 2 q 3 r 2 s 6
37 ( -11, 19 , 31 ) ( 1861, 19 , 31 ) p 6 q 1 r 6 s 6
50 ( -5, 7 , 76 ) ( 4155, 7 , 76 ) p 2 q 4 r 2 s 8
62 ( -5, 7 , 22 ) ( 1803, 7 , 22 ) p 4 q 4 r 1 s 9
65 ( -61, 107 , 155 ) ( 17091, 107 , 155 ) p 8 q 1 r 8 s 8
74 ( 22, -17 , 109 ) ( 22, 9711 , 109 ) p 1 q 5 r 7 s 9
77 ( -13, 17 , 233 ) ( 19263, 17 , 233 ) p 2 q 5 r 2 s 10
82 ( 5, -4 , 41 ) ( 5, 3776 , 41 ) p 3 q 5 r 9 s 9
98 ( -4, 5 , 29 ) ( 3336, 5 , 29 ) p 5 q 5 r 5 s 11
101 ( -97, 173 , 233 ) ( 41103, 173 , 233 ) p 10 q 1 r 10 s 10
109 ( -29, 43 , 97 ) ( 15289, 43 , 97 ) p 6 q 5 r 0 s 12
110 ( -4, 5 , 83 ) ( 9684, 5 , 83 ) p 2 q 6 r 2 s 12
122 ( 6, -5 , 61 ) ( 6, 8179 , 61 ) p 4 q 6 r 11 s 11
125 ( -37, 59 , 105 ) ( 20537, 59 , 105 ) p 10 q 3 r 8 s 12
145 ( 7, -5 , 19 ) ( 7, 3775 , 19 ) p 0 q 7 r 12 s 12
149 ( -19, 23 , 449 ) ( 70347, 23 , 449 ) p 2 q 7 r 2 s 14
170 ( -15, 19 , 82 ) ( 17185, 19 , 82 ) p 5 q 7 r 1 s 15
173 ( -23, 31 , 97 ) ( 22167, 31 , 97 ) p 10 q 5 r 10 s 14
190 ( 5, -4 , 23 ) ( 5, 5324 , 23 ) p 0 q 8 r 9 s 15
194 ( -11, 13 , 292 ) ( 59181, 13 , 292 ) p 2 q 8 r 2 s 16
197 ( -61, 159 , 101 ) ( 51281, 159 , 101 ) p 14 q 1 r 4 s 16
209 ( -97, 119 , 611 ) ( 152667, 119 , 611 ) p 8 q 7 r 8 s 16
226 ( 8, -7 , 113 ) ( 8, 27353 , 113 ) p 6 q 8 r 15 s 15
242 ( 31, -24 , 115 ) ( 31, 35356 , 115 ) p 1 q 9 r 14 s 16
245 ( -25, 29 , 737 ) ( 187695, 29 , 737 ) p 2 q 9 r 2 s 18
257 ( 131, -109 , 755 ) ( 131, 227811 , 755 ) p 4 q 9 r 16 s 16
269 ( -79, 123 , 227 ) ( 94229, 123 , 227 ) p 14 q 5 r 10 s 18
290 ( 9, -8 , 145 ) ( 9, 44668 , 145 ) p 7 q 9 r 17 s 17
302 ( -7, 8 , 227 ) ( 70977, 8 , 227 ) p 2 q 10 r 2 s 20
305 ( -55, 69 , 293 ) ( 110465, 69 , 293 ) p 8 q 9 r 4 s 20
314 ( 43, -38 , 469 ) ( 43, 160806 , 469 ) p 4 q 10 r 13 s 19
325 ( -107, 199 , 235 ) ( 141157, 199 , 235 ) p 18 q 1 r 18 s 18
334 ( -11, 13 , 82 ) ( 31741, 13 , 82 ) p 6 q 10 r 3 s 21
362 ( 27, -23 , 178 ) ( 27, 74233 , 178 ) p 1 q 11 r 11 s 21
365 ( -31, 35 , 1097 ) ( 413211, 35 , 1097 ) p 2 q 11 r 2 s 22
398 ( -14, 19 , 55 ) ( 29466, 19 , 55 ) p 10 q 10 r 1 s 23
401 ( -79, 101 , 381 ) ( 193361, 101 , 381 ) p 16 q 7 r 20 s 20
410 ( -59, 67 , 610 ) ( 277629, 67 , 610 ) p 7 q 11 r 7 s 23
434 ( -17, 19 , 652 ) ( 291231, 19 , 652 ) p 2 q 12 r 2 s 24
437 ( -121, 179 , 381 ) ( 244841, 179 , 381 ) p 14 q 9 r 4 s 24
442 ( -34, 41 , 215 ) ( 113186, 41 , 215 ) p 9 q 11 r 6 s 24
469 ( -137, 211 , 397 ) ( 285289, 211 , 397 ) p 18 q 7 r 12 s 24
482 ( -4, 5 , 21 ) ( 12536, 5 , 21 ) p 11 q 11 r 7 s 25
485 ( -481, 905 , 1037 ) ( 942351, 905 , 1037 ) p 22 q 1 r 22 s 22
497 ( -313, 407 , 1403 ) ( 899883, 407 , 1403 ) p 16 q 9 r 16 s 24
509 ( -37, 41 , 1529 ) ( 799167, 41 , 1529 ) p 2 q 13 r 2 s 26
514 ( 44, -37 , 251 ) ( 44, 151667 , 251 ) p 3 q 13 r 18 s 24
530 ( 151, -125 , 772 ) ( 151, 489315 , 772 ) p 5 q 13 r 23 s 23
554 ( -29, 33 , 274 ) ( 170107, 33 , 274 ) p 7 q 13 r 5 s 27
557 ( -283, 347 , 1613 ) ( 1092003, 347 , 1613 ) p 14 q 11 r 14 s 26
577 ( -191, 361 , 409 ) ( 444481, 361 , 409 ) p 24 q 1 r 24 s 24
590 ( -10, 11 , 443 ) ( 267870, 11 , 443 ) p 2 q 14 r 2 s 28
602 ( 61, -50 , 291 ) ( 61, 211954 , 291 ) p 4 q 14 r 23 s 25
605 ( -81, 95 , 593 ) ( 416321, 95 , 593 ) p 10 q 13 r 8 s 28
626 ( 13, -12 , 313 ) ( 13, 204088 , 313 ) p 11 q 13 r 25 s 25
629 ( -511, 743 , 1661 ) ( 1512627, 743 , 1661 ) p 22 q 7 r 22 s 26
674 ( 133, -116 , 997 ) ( 133, 761736 , 997 ) p 1 q 15 r 13 s 29
677 ( -43, 47 , 2033 ) ( 1408203, 47 , 2033 ) p 2 q 15 r 2 s 30
685 ( -191, 283 , 595 ) ( 601621, 283 , 595 ) p 18 q 11 r 6 s 30
689 ( 101, -87 , 677 ) ( 101, 536129 , 677 ) p 4 q 15 r 20 s 28
701 ( -129, 161 , 671 ) ( 583361, 161 , 671 ) p 14 q 13 r 10 s 30
722 ( -140, 163 , 1063 ) ( 885312, 163 , 1063 ) p 7 q 15 r 1 s 31
725 ( -211, 323 , 615 ) ( 680261, 323 , 615 ) p 22 q 9 r 14 s 30
730 ( 14, -13 , 365 ) ( 14, 276683 , 365 ) p 12 q 14 r 27 s 27
770 ( -23, 25 , 1156 ) ( 909393, 25 , 1156 ) p 2 q 16 r 2 s 32
773 ( -71, 85 , 451 ) ( 414399, 85 , 451 ) p 10 q 15 r 4 s 32
785 ( -235, 653 , 369 ) ( 802505, 653 , 369 ) p 28 q 1 r 8 s 32
794 ( -47, 54 , 391 ) ( 353377, 54 , 391 ) p 11 q 15 r 10 s 32
830 ( -9, 10 , 103 ) ( 93799, 10 , 103 ) p 8 q 16 r 7 s 33
842 ( 15, -14 , 421 ) ( 15, 367126 , 421 ) p 13 q 15 r 29 s 29
845 ( -15, 19 , 73 ) ( 77755, 19 , 73 ) p 22 q 11 r 26 s 30
869 ( -49, 53 , 2609 ) ( 2313327, 53 , 2609 ) p 2 q 17 r 2 s 34
874 ( 41, -37 , 434 ) ( 41, 415187 , 434 ) p 3 q 17 r 15 s 33
890 ( 97, -89 , 1330 ) ( 97, 1270119 , 1330 ) p 5 q 17 r 17 s 33
901 ( 181, -149 , 871 ) ( 181, 948001 , 871 ) p 6 q 17 r 30 s 30
917 ( -859, 1415 , 2201 ) ( 3316731, 1415 , 2201 ) p 26 q 9 r 14 s 34
962 ( -65, 76 , 471 ) ( 526279, 76 , 471 ) p 14 q 16 r 13 s 35
965 ( 245, -223 , 2879 ) ( 245, 3014883 , 2879 ) p 10 q 17 r 28 s 32
973 ( -61, 155 , 101 ) ( 249149, 155 , 101 ) p 30 q 5 r 0 s 36
974 ( -13, 14 , 731 ) ( 725643, 14 , 731 ) p 2 q 18 r 2 s 36
989 ( -277, 411 , 857 ) ( 1254329, 411 , 857 ) p 22 q 13 r 8 s 36
Mon Jul 6 19:11:55 PDT 2020
This answer is based on the excellent work of Will Jagy. This solves all cases of $k>3.$
Let $p<k$ be an odd prime such that $p\not\mid k.$
Solve $kd\equiv -1\pmod{p}.$ Let $n=(kd+1)/p.$ Note that since $p<k,$ $n>d.$
Then for any integer $t,$ we can take $z=a^{d}t^p$ so that $$\begin{align}az^k+1&=a^{kd+1}t^{kp}+1\\&=\left(a^nt^k\right)^p+1\\ &=(a^nt^k+1)\left(1+a^nt^k\sum_{j=1}^{p-1} (-1)^j\left(a^nt^k\right)^{j-1}\right) \end{align}$$
Where the last equation is because when $p$ is odd, $$ \begin{align}u^p+1&=(u+1) \sum_{j=0}^{p-1} (-1)^ju^j \\&=(u+1)\left(1+u\sum_{j=1}^{p-1}(-1)^ju^{j-1}\right)\end{align}$$
Now, since $n>d,$ we can set $$ \begin{align}x&=a^{n-d}t^{k-p}\\ y&=a^{n-d}t^{k-p}\sum_{j=1}^{p-1} (-1)^j\left(a^nt^k\right)^{j-1} \end{align}$$
For $k\geq 4$ we can always find such a $p$ by taking a prime factor of $n-1$ or $n-2$ if $n$ is even or odd, respectively.
So this solves all cases $k>3.$
You don't need $p$ prime, just that $1<p<k$ is odd and $\gcd(p,k)=1.$
k even
So when $k$ is even, we can take $p=k-1.$ Then $d=p-1$ and $n=p.$
Then for any integer $t,$ $$\begin{align}z&=a^{k-2}t^{k-1}\\x&=at\\y&=at\sum_{j=1}^{k-2}(-1)^j\left(a^{k-1}t^k\right)^{j-1}.\end{align}$$
k odd
Likewise, if $k=2m+1$ is odd, then you can take $p=2m-1,$ $d=m-1$ and $n=m.$ Then for any integer $t$:
$$\begin{align}z&=a^{m-1}t^{2m-1}\\ x&=at^2\\ y&=at^2\sum_{j=1}^{2m-2}(-1)^j\left(a^mt^{2m+1}\right)^{j-1} \end{align}$$
is a solution.
In particular, for $k>3$ there are infinitely many solutions $(x,y,z)$ with $a\mid x$ and $x\mid y$ and $x\mid z.$
Best Answer
How: For how to do it, look for the Extended Euclidean Algorithm. It is not particularly hard to carry out, but a proper description would be quite lengthy. The Extended Euclidean Algorithm is also described in most books on Elementary Number Theory. There are many computer implementations, but for $a$ and $c$ of modst size, the procedure can be easily carried out by hand.
If $d$ is the greatest common divisor of $a$ and $c$, the Extended euclidean algorithm produces integers $x$ and $y$ such that $ax+d=cy$. But from that one can solve your more general problem.
Existence of solution: Certainly there do not always exist such $m$ and $n$. For example, let $a=2$, $b=1$, $c=2$. Then $an+b$ (that is, $2n+1$) is always odd, and $cm$ (that is, 2m$) is always even, so they can never be equal.
In general, if the greatest common divisor of $a$ and $c$ divides $b$, there always is a solution. If the greatest common divisor of $a$ and $c$ does not divide $b$, there is no solution.
Infinitely many solutions: If there is a solution $(n_0,m_0)$, then there are infinitely many solutions. For suppose that $an_0+b=cm_0$. Then for any integer $t$, we have $$a(n_0 +ct)+b=c(n_0+at).$$ (Just expand. There will be a term $act$ on the left, and a term $cat$ on the right, and they cancel.)
So if $(n_0,m_0)$ is a solution, then so is $(n_0+ct, m_0+at)$ for any positive integer $t$.