Number Theory I

Number Theory Level pending

Find the Smallest Positive Integer x x Such that

{ x 5 ( m o d 7 ) x 7 ( m o d 11 ) x 3 ( m o d 13 ) \begin{cases} x \equiv 5 (mod 7)\\ x \equiv 7 (mod 11)\\ x \equiv 3 (mod 13)\\ \end{cases}


The answer is 887.

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.

2 solutions

Himanshu Arora
May 29, 2014

Let the number be of the form 13 k + 3 13k+3 and 11 j + 7 11j+7 . This implies 13 k = 11 j + 4 13k=11j+4 . Note that the first number of this sort is 26 26 . Hence all the other numbers in this series are 143 l + 26 143l + 26 ; since the LCM is 143 143 . Don't forget the 3 in the original number; this gives us a number of the form 143 l + 29 143l + 29 . Now, again apply the same modular arithmetic rule along with 7 a + 5 7a+5 to get 887 \boxed{887} . Please note that this LCM method would work for any co-prime numbers. So the next number satisfying the given set of conditions would be 887 + 143 × 7 887 + 143 \times 7

For mod 11, the numbers would be 18,29,40.....
For mod 13, the numbers would be 16,29,.............. <..>29 satisfies 11 and 13. But
29 = 1 (mod 7 ). <.....> Next satisfactory number will be 11 * 13 = 143 more.. 143= 3 (mod 7)
For every addition of 143 to 29, we add 3 (mod 7). <..>For 29 we have 1 (mod 7 )
To have 5 (mod 7) we need .....12, 19, 26, 33, 40, ..... which should be 1 (mod 3) ..<..>1 for 29 and 3 for every 143.
The first to give this is 19 = 1 (mod 3) and.. 19 - 1 = 18 <..> 18/3 = 6. So, 6 of 143. <..> 29 + 6*143 = 887.



wait but , x=5 mod(7) then 11x=55mod(77) and 7x=49 mod (77) therefor 4x =6 mod (77) wich give us 77 / 2k ( 2k=4x -6) wich is a contradiction no ? can someone clear me up

Yas Inne - 7 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...