I am trying to solve this problem
W is a positive integer when divided by 5 gives remainder 1 and when divided by 7 gives remainder 5. Find W.
I am referring back to an earlier post I made. Now I am attempting to solve it that way.
We know that $$w\equiv1(mod~5)$$ $$w\equiv5(mod~7)$$
$w=7r+5$
$w=5r+5+2r$
Since $5r+5$ is divisible by 5
$w=5(r+1)+2r$ this shows the remainder is $2r$
Now $2r$ divided by 5 gives a remainder 1 , thus giving the equation
$2r = 5k + 1$ or $r=\frac{5k+1}{2}$
Putting r back in $w=7r+5$ we get
$2w = 35k + 12$
So I guess $w= \frac{35+12}{2} = 23.5$
This is wrong and the answer is suppose to be 26. Any suggestions what I might be doing wrong ? or anything that I might be missing ?
Edit: The problem was in calculation
$w= \frac{35+17}{2} = 26$
$\endgroup$ 44 Answers
$\begingroup$There is an error: $\rm\:w=7r\!+\!5\,\Rightarrow\,2w = 7(2r)\!+\!\color{#C00}{10} = 7(5k\!+\!1)\!+\!\color{#C00}{10} = 35k\!+\!\color{#C00}{17},\:$ not $\rm\:35k\!+\!\color{#0A0}{12}.$ Since $\rm\:35k\!+\!17 = 2w\:$ is even, $\rm\:k\:$ is odd, $\rm\:k = 2j\!+\!1,\,$ so $\rm\:w = (35(2j\!+\!1)\!+\!17)/2 = 35j+26.$
Remark $\ $ It is easier to do the division by $2$ before the substitution. Namely, we have $\rm\:2r = 5k\!+\!1\:$ so $\rm\:k\:$ is odd, $\rm\:k = 2j\!+\!1,\:$ thus $\rm\:r = (5k\!+\!1)/2 = (5(2j\!+\!1)\!+\!1)/2 = 5j\!+\!3.\:$ Therefore $\rm\:w = 7r\!+\!5 = 7(5j\!+\!3)\!+\!5 = 35j\!+\!26.$ Notice how the numbers remain smaller this way.
I emphasize again, it's much more intuitive if you learn about modular arithmetic (congruences). For many examples see my posts on Easy CRT (easy version of the Chinese Remainder Theorem)
$\endgroup$ 4 $\begingroup$By above we have $w=7r+5= 7(5r+1)/2 +5= 35r/2 + 7/2 +5 = 17r+r/2 +1/2 +8$. So do $r$ odd and we obtain $26, 61=(17 \cdot 3 +2 +8) \cdots$.
$\endgroup$ $\begingroup$w is of the form 5a+1=7b+5 where a,b are integers.
=>5a=7b+4
=>5a+10=7b+14
=>5(a+10)=7(b+2)
=>5 divides (b+2) as (5,7)=1
=>b is of the form 5c-2 where c is any integer.
w=7b+5=7(5c-2)+5=35c-9=35d+26 where d=c-1
Alternatively, according to Euclid's GCD algorithm,
there exists integers c,d such that cx+dy=(x,y).
As (5,7)=1 => 5c+7d=1.
(i)By observation, one set of values of (c,d) = (3,-2).
Or (ii)$\frac{7}{5} = 1 + \frac{2}{5} = 1 + \frac{1}{2+\frac{1}{2}} $,
The 2nd convergent = $ 1 + \frac{1}{2} = \frac{3}{2}$
Then, 3(5)-2(7) must be ±1 is actually 1. So, (c,d) = (3,-2)
Then, 5a+1=7b+5 =>5a=7b+4
=>5a=7b+4(5(3)+7(-2))
=>5(a-12)=7(b-8)
=>5=7$\frac{b-8}{a-12}$ an integer.
=>7|(a-12)
=>$\frac{b-8}{5}$=$\frac{a-12}{7}$=h(some integer)
=>b=5h+8
=>w=7b+5=7(5h+8)+5=35h+61=35k+26 if k=h+1
$\endgroup$ $\begingroup$$w\equiv 1 \mod5 \Longrightarrow w=5a+1$, and
$w\equiv 5 \mod7 \Longrightarrow w=7b+5$ .
Multiply the first by 7 and the second by 5:
$7w=35a+7$ , and
$5w=35b+25$.
Subtract:
$2w = 35(a-b) - 18$.
$\Longrightarrow 2w \equiv -18 \mod 35$,
$\Longrightarrow 2w \equiv 17 \mod 35$
$\Longrightarrow 2w \equiv 52 \mod 35$
$\Longrightarrow w \equiv 26 \mod 35$
