Diophantine Question

How many non-negative integers x x less than 1001 1001 are there such that ( x 3 ) ( x + 1 ) ( x + 3 ) (x-3)(x+1)(x+3) is divisible by 1001 1001 ?


The answer is 27.

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

Chris Lewis
Oct 13, 2020

Directly quoting from Wikipedia: "the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n n by several integers, then one can determine uniquely the remainder of the division of n n by the product of these integers, under the condition that the divisors are pairwise coprime".

In this case, our divisors are 7 , 11 , 13 7,11,13 (since 1001 = 7 11 13 1001=7\cdot11\cdot13 ). 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 x such that 7 x 3 , 11 x 3 , 13 x + 3 7|x-3,\;\;11|x-3,\;\;13|x+3 (assigning divisors to brackets). The CRT states there will be exactly one solution in the range (in this case it's x = 465 x=465 , 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 = 27 3^3=\boxed{27} such integers.

Patrick Corn
Oct 15, 2020

We have that x x satisfies the condition if and only if ( x 3 ) ( x + 1 ) ( x + 3 ) (x-3)(x+1)(x+3) is divisible by 7 , 11 , 7,11, and 13 , 13, and since these are all prime, this is equivalent to x 3 , 1 , 3 ( m o d 7 ) x 3 , 1 , 3 ( m o d 11 ) x 3 , 1 , 3 ( m o d 13 ) \begin{aligned} x &\equiv -3, -1, 3 \pmod 7 \\ x &\equiv -3, -1, 3 \pmod{11} \\ x &\equiv -3, -1, 3 \pmod{13} \end{aligned} and each choice of one of the three possibilities gives a unique solution mod 1001 , 1001, so there are 3 3 3 = 27 3 \cdot 3 \cdot 3 = \fbox{27} solutions.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...