For how many positive integers does the following statement hold ?
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.
By using Bezout's theorem we can say that there exists exactly 1 positive integer k < 1 4 3 which has the stated property . It's possible to find the number by using Bezout's theorem , as g c d ( 6 7 , 1 4 3 ) = 1
Thus 1 can be expressed as 1 4 3 x + 6 7 y for some integers x and y .
1 4 3 = 2 × 6 7 + 9
6 7 = 7 × 9 + 4
9 = 2 × 4 + 1
Hence 1 = 9 − 4 × 2
∴ 1 = ( 1 4 3 − 2 × 6 7 ) − ( 6 7 − 7 × 9 ) 2
∴ 1 = ( 1 4 3 − 2 × 6 7 ) − [ 2 × 6 7 − 1 4 ( 1 4 3 − 2 × 6 7 ) ]
∴ 1 = 1 4 3 − 2 × 6 7 + 1 4 × 1 4 3 − 3 0 × 6 7
∴ 1 = 1 4 3 × 1 5 − 6 7 × 3 0
∴ 1 = 1 4 3 × 1 5 + 6 7 × ( − 3 0 )
This tells us that 6 7 × ( − 3 0 ) ≡ 1 ( m o d 1 4 3 ) hence 6 7 × ( 1 4 3 − 3 0 ) ≡ 1 ( m o d 1 4 3 )
So the smallest positive integer for which given statement hold is 143-30 i.e. 1 1 1
The other numbers will be of the form 1 1 1 + 1 4 3 k as they also will be congruent to 1 mod 143 .
The multiple of 143 next to 10000 is 1 4 3 × 7 0 = 1 0 0 1 0 so the biggest of our required numbers is 1 0 0 1 0 − 1 1 1 = 1 1 1 + 6 9 × 1 4 3 .
Hence all the numbers we require are 1 1 1 , 1 1 1 + 1 4 3 , 1 1 1 + 2 × 1 4 3 , … , 1 1 1 + 6 9 × 1 4 3
Thus there are 7 0 such numbers k ............. ( k < 1 0 0 0 0 )