How many non-negative integers x less than 1 0 0 1 are there such that ( x − 3 ) ( x + 1 ) ( x + 3 ) is divisible by 1 0 0 1 ?
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.
We have that x satisfies the condition if and only if ( x − 3 ) ( x + 1 ) ( x + 3 ) is divisible by 7 , 1 1 , and 1 3 , and since these are all prime, this is equivalent to x x x ≡ − 3 , − 1 , 3 ( m o d 7 ) ≡ − 3 , − 1 , 3 ( m o d 1 1 ) ≡ − 3 , − 1 , 3 ( m o d 1 3 ) and each choice of one of the three possibilities gives a unique solution mod 1 0 0 1 , so there are 3 ⋅ 3 ⋅ 3 = 2 7 solutions.
Problem Loading...
Note Loading...
Set Loading...
Directly quoting from Wikipedia: "the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime".
In this case, our divisors are 7 , 1 1 , 1 3 (since 1 0 0 1 = 7 ⋅ 1 1 ⋅ 1 3 ). We have three brackets in the factorisation, and three divisors. As an example of how we can use this, say we want to find x such that 7 ∣ x − 3 , 1 1 ∣ x − 3 , 1 3 ∣ x + 3 (assigning divisors to brackets). The CRT states there will be exactly one solution in the range (in this case it's x = 4 6 5 , but the point is we don't have to work out the particular value).
Any one of the divisors can divide at most one of the brackets; so there are 3 3 = 2 7 such integers.