Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question

3 Answers 3

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.

share|improve this answer

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$.

share|improve this answer

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.

]

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.