Finding a number when its remainder is given.

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$

• It looks like you forgot to multiply all terms by two after substituting $r=\frac{5k+1}{2}$ in $w=7r+5$. – peoplepower Jul 20 '12 at 13:02
• Chinese remainder theorem – draks ... Jul 20 '12 at 13:03
• Look at the sequence of positive integers congruent to 1 mod 5, 5r+1, for $r\ge 0$. The sequence is 1, 6, 11, .. Eventually one of them will be congruent to 5 mod 7. – i. m. soloveichik Jul 20 '12 at 13:08
• @draks Yes it is based on the Chinese Remainder theorem – Rajeshwar Jul 20 '12 at 13:18

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)

• I thought that this was being solved according to CRT. Am i doing it wrong ? It does give me the correct answer – Rajeshwar Jul 20 '12 at 23:48
• Yes, this method is essentially CRT. The only problem was your arithmetic error. If you follow my Easy CRT link you'll find many examples of CRT presented in a very simple form. – Bill Dubuque Jul 20 '12 at 23:53
• CRT this explains a lot. Thanks – Rajeshwar Jul 21 '12 at 1:41
• @Rajeshwar I think you'll find that in practice the Easy CRT method is simpler than the method presented in that video. I also show various tricks and optimizations in the linked posts. – Bill Dubuque Jul 21 '12 at 2:10

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

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

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