Convoluted Congruence

Determine the total number of positive integers x x less than 2016 that satisfy the following:

  • when 2017 is divided by x x , it gives a remainder of 1;
  • when 2018 is divided by x x , it gives a remainder of 2;
  • when 2019 is divided by x x , it gives a remainder of 3.


The answer is 32.

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

Efren Medallo
Jun 18, 2017

Let us try to interpret what each congruence means.

1 2017 ( m o d x ) 1 \equiv 2017 \: (\!\! \mod x)

This means that when 2017 2017 is divided by an integer x x , a remainder of 1 1 is left. Or, in math-ese, 2017 = k x + 1 2017 = kx + 1 for some integer k k . We can deduce from here that k x = 2016 kx = 2016 , so that x x must be a factor of 2016 2016 .

Similarly, we can derive that same piece of information from the two remaining systems ( since 2018 = j x + 2 2018 = jx + 2 for some integer j j , and 2019 = m x + 3 2019 = mx + 3 for some integer m m ). This allows us to investigate on the factors of 2016 2016 .

2016 = 2 5 3 2 7 2016 = 2^5 \cdot 3^2 \cdot 7 , which means there are 36 36 factors, including 2016 2016 itself and 1 1 . Now, we will remove the values of x x which may be factors of any of 2017 2017 , 2018 2018 , or 2019 2019 as well. Since 2017 2017 is prime, there's no worry that any x x from the factors of 2016 2016 will divide it evenly.

As for 2018 2018 , we know that gcd ( 2016 , 2018 ) = 2 \gcd (2016, 2018) = 2 , so we remove 2 2 from the list.

As for 2019 2019 , we know that gcd ( 2016 , 2019 ) = 3 \gcd (2016, 2019) = 3 , letting us remove 3 3 now.

Having removed 1 1 , 2 2 , 3 3 , and 2016 2016 from the 36 36 factors leaves us with 32 \boxed{32} .

Let us try to interpret what each congruence means. 1 2017 ( m o d x ) 1 \equiv 2017 \: (\!\! \mod x)

Like I said in the report section, you're using the wrong math notations. The statement above suggests that we are looking for all positive integers x<2016 such that it is a factor of (1-2017=-2016), this suggest that x=1,2,3 could also the solution.

Pi Han Goh - 3 years, 11 months ago

Why are you removing 2 from the list? Are you saying that 2 2018 ( m o d 2 ) 2 \equiv 2018 { \pmod 2 } is not a true statement?

The answer should be 36.

Calvin Lin Staff - 3 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...