Find $(a,b)$ for $\gcd(a,b) = 13$. I think the book is wrong here.

Question

$49a - 125b = 169$

$a = 125k + 6$

$b = 49k + 1$

$a$ and $b$ are natural

$\gcd(a,b) = d$

The question says: Find what $\gcd(a,b)$ could be then find $a$ and $b$ where their $\gcd$ is equal to $13$.

My solution:

Of course, $d$ possibilities is going to be $169$ divisors by applying division properties.

So $d$ is $\left \{ 1,13,169 \right \}$

What I don't understand is how the book found $a$ and $b$

The book found $a$ and $b$ like this:

$d = 13$ $\Rightarrow$ $\left\{\begin{matrix} b= 0\pmod {13} \\ a = 0 \pmod {13} \end{matrix}\right.$

\begin{Bmatrix} 125k + 6 = 0\pmod {13} \\ 49k + 1 = 0 \pmod {13} \end{Bmatrix}

So: $125k + 6 - 49k - 1 = 0\pmod {13}$

In the end we find $k = 9\pmod {13}$ which is $k = 13m + 9$ where $k$ is a natural number. Then by putting this in $a$ and $b$ we find:

$a = 1625m + 1131$

$b = 637m + 442$

where $m$ is a natural number.

I understand almost all this and I know this way.

What I don't understand is I don't think this way should be correct. Correct me if I'm wrong but doesn't $a, b = 0\pmod {13}$ for $d = 13$ only work when $13$ is the highest number in the possibilities? But here it isn't $13$ it is $169$ so I don't think it works.

Because $a,b$ can be divided by $13$ and $169$ at same time this way. So if $169$ is a divisor of both then it's already the $\gcd$ not $13$ since $13$ is a divisor of $169$ so if $a$ and $b$ were multiples of $169$ they will be both $0 \pmod {13}$ even though their $\gcd$ is going to be $169$

TL;DR: I don't think $a, b = 0\pmod {13}$ should work here and I think the book is wrong. If I'm wrong, can you explain it to me please?

Answer 1

The OP is correct in having concerns about the answer $$a = 1625m + 1131, b = 637m + 442.$$ In particular, there is nothing in the method shown that prevents $a$ and $b$ from having a gcd of $169$.

In fact, if $m=7$ then $a$ and $b$ do have gcd $169$. So, the correct answer must state 'for $m\ne 13l+7$'.

To see this, consider the numbers $\frac{a}{13}=49m+34$ and $\frac{b}{13}=125a+87$. We are interested in when both of these numbers are divisible by $13$.

Working modulo $13$ the numbers are $10m+8$ and $8m+9$ and it is now easy to see that $m= 7$ makes both expressions multiples of $13$. Then any $m$ of the form $13l+7$ would do just as well.

Answer 2

The usual approach is via the first equation solving.

If $\;d=13,\;$ then $$a=13x,\quad b=13y,\quad 49x-125y=13,$$ $$x_1=x-2y,\quad 49x_1-27y=13,$$ $$y_1=y-x_1=3y-x,\quad 22x_1–27y_1=13,$$ $$x_2=x_1-y_1=2x-5y,\quad 22x_2-5y_1=13,$$ $$y_2=y_1-4x_2=23y-9x,\quad 2x_2-5y_2=13,$$ $$x_3=x_2-2y_2=20x-51y,\quad 2x_3-y_2=13,$$ \begin{cases} 20x-51y=m+6\\[4pt] -9x+23y=2m-1, \end{cases} $$x=\begin{vmatrix} m+6 & -51\\ 2m-1 & 23 \end{vmatrix}=87+125m,\quad y=\begin{vmatrix} 20 & m+6\\ -9& 2m-1 \end{vmatrix}=34+49m,\quad m\in\mathbb N,$$ $$a=13(87+125m),\quad b=13(34+49m),\quad m\in\mathbb N.$$

And from the overdefined system \begin{cases} 13(87+125m)=125k+6\\[4pt] 13(34+49m)=49k+1 \end{cases} should $\;k=13m+9.\;$

If $\;d=169,\;$ then similarly $$a=169x,\quad b=169y,\quad 49x-125y=1,\dots$$ \begin{cases} 20x-51y=m\\[4pt] -9x+23y=2m-1, \end{cases} $$x=\begin{vmatrix} m & -51\\ 2m-1 & 23 \end{vmatrix}=125m-51,\quad y=\begin{vmatrix} 20 & m\\ -9 & 2m-1 \end{vmatrix}=49m-20,\quad m\in\mathbb N,$$ $$a=169(125m-51),\quad b=169(49m-20),\quad m\in\mathbb N.$$

And from the overdefined system \begin{cases} 169(125m-51)=125k+6\\[4pt] 169(49m-20)=49k+1 \end{cases} should $\;k=169m+69.\;$