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

share|improve this question
2  
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
3  
Chinese remainder theorem –  draks ... Jul 20 '12 at 13:03
1  
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
add comment

4 Answers

up vote 1 down vote accepted

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)

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.