Finding K value to solve a problem using diophantine equation

Question

I have to prove that any number that divided by 5 gives a remainder of 1 and divided by 7 a remainder of 2, also gives a remainder of 16 when divided by 35, using a diophantine equation.

So first I made the following proposition: $(n=5q_1+1 \land n=7q_2+2) \implies 16=n-35q_3$ and started by working with the hipothesis hoping to reach the conclusion.

Since $(n=5q_1+1 \land n=7q_2+2)$, then $5q_1+1=7q_2+2$, thus I can also say that $5q_1-7q_2=1$.

Here I have my diophantine equation. From now on, $x=q_1$ and $y=q_2$ so I can have $5x-7y=1$

$GCD(5, -7)=1$, and a linear combination for $5p-7q=GCD(5, -7)$ is $p=3$ and $q=2$. Since $GCD(5, -7) = c = 1$, $x_0=(c*p)/d=3$ and $y_0=(c*q)/d=2$

$$x=x_0+k*(b/d)=3-7k$$$$y=y_0-k(a/d)=2-5k$$

But now that I have this, I don't have any clue how to continue. How should I limit the value of $k$?

Answer 1

As you have already identified the number $y$ is of the form $5a+1$, and $7b+2$

So, $$5a+1=y=7b+2$$

$$5a=7b+1=7b+5\cdot3-2\cdot7$$ as $1=5\cdot3-2\cdot7$ (find the derivation below)

$$\implies 5(a-3)=7(b-2)$$

$$\implies \frac{7(b-2)}5=a-3 \text{ an integer as } a \text { is.}$$

So, $$5\mid 7(b-2)\implies 5\mid (b-2) \text{ as }(7,5)=1$$

So, $$\frac{a-3}7=\frac{b-2}5 \text{ is an integer }=c\text{( say)}$$

So, $b=5c+2\implies y=7b+2=7(5c+2)+2=35c+16$

or $a=7c+3\implies y=5a+1=5(7c+3)+1=35c+16$

[

Expressing $\frac75$ as continued fraction,

$$\frac75=1+\frac25=1+\frac1{\frac52}=1+\frac1{2+\frac12}$$

So, the last but one convergent of $\frac75$ is $1+\frac12=\frac32\implies 5\cdot3-7\cdot2=1$

Again,

$$\frac75=1+\frac25=1+\frac1{\frac52}=1+\frac1{2+\frac12}=1+\frac1{2+\frac1{1+1}}$$

So, the next convergent of $\frac75$ is $1+\frac1{2+\frac1{1}}=\frac43\implies 7\cdot3-5\cdot4=1$

We could replace $1$ with $7\cdot3-5\cdot4$ too.

]

Answer 2

Once you get to $5 \cdot 3 + (-7) \cdot 2 = 2 - 1$, moving the appropriate summands to the other side you get $1 + 5 \cdot 3 = 16 = 2 + 7 \cdot 2$, which is your solution.

Answer 3

You know that:

$n = 5q_1 + 1$

$n = 7q_2 + 2$

for some integers $q_1,q_2$.

Thus:

$7n = 35q_1 + 7$

$5n = 35q_2 + 10$

Now there must exist integers $a,b$ such that $7a + 5b = 1$ since $7,5$ are coprime. We can easily see that $a=3, b=-4$ will do. Multiply the first equation by $a$, the second by $b$ and subtract to get:

$n = 35(4q_1 - 3q_2) - 19$

So $n$ leaves a remainder of $35-19 = 16$ upon division by $35$.