Multiples of 7 & 11 with remainders

How many positive integers are there, less than 1000 1000 , when divided by 7 7 , give a remainder of 4 4 , and when divided by 11 11 , give a remainder of 9 9 ?


The answer is 13.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Jerry McKenzie
Jan 7, 2018

If a 4 m o d 7 a\equiv 4 \enspace mod \enspace 7 and a 9 m o d 11 a\equiv 9\enspace mod\enspace 11

Then a = 11 k + 9 a= 11k+9 for any integer k, looking at ( 11 k + 9 ) m o d 7 = 4 (11k+9)\enspace mod\enspace 7 = 4 leads to the L.H.S. to cycle {2,6,3,0,4,1,5} for k={0,1,2,3,4,5,6} thus ( 11 k + 9 ) m o d 7 = 4 (11k+9)\enspace mod\enspace 7 = 4 k = 4 + l c m ( 7 , 11 ) 11 N \Rightarrow k=4+\frac{lcm(7,11)}{11} \ell \enspace\forall\enspace\ell\in \mathbb{N} with smallest natural number a = 11 4 + 9 = 53 a=11\cdot 4+9 = 53 . l c m ( 7 , 11 ) = 77 lcm(7,11)=77 since 7 and 11 are coprime. Thus a = 53 + 77 m m N a=53+77m \enspace\forall\enspace m \in \mathbb{N}

0 < a < 1000 0<a<1000 0 + 77 0 < 53 + 77 m < 76 + 77 12 \Rightarrow 0+77\cdot 0 <53+77m<76 + 77 \cdot 12 0 m 12 \Rightarrow 0\leq m\leq 12

which is 12 0 + 1 = 13 12-0+1=13 solutions.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...