Determine the total number of positive integers less than 2016 that satisfy the following:
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.
Let us try to interpret what each congruence means.
1 ≡ 2 0 1 7 ( m o d x )
This means that when 2 0 1 7 is divided by an integer x , a remainder of 1 is left. Or, in math-ese, 2 0 1 7 = k x + 1 for some integer k . We can deduce from here that k x = 2 0 1 6 , so that x must be a factor of 2 0 1 6 .
Similarly, we can derive that same piece of information from the two remaining systems ( since 2 0 1 8 = j x + 2 for some integer j , and 2 0 1 9 = m x + 3 for some integer m ). This allows us to investigate on the factors of 2 0 1 6 .
2 0 1 6 = 2 5 ⋅ 3 2 ⋅ 7 , which means there are 3 6 factors, including 2 0 1 6 itself and 1 . Now, we will remove the values of x which may be factors of any of 2 0 1 7 , 2 0 1 8 , or 2 0 1 9 as well. Since 2 0 1 7 is prime, there's no worry that any x from the factors of 2 0 1 6 will divide it evenly.
As for 2 0 1 8 , we know that g cd ( 2 0 1 6 , 2 0 1 8 ) = 2 , so we remove 2 from the list.
As for 2 0 1 9 , we know that g cd ( 2 0 1 6 , 2 0 1 9 ) = 3 , letting us remove 3 now.
Having removed 1 , 2 , 3 , and 2 0 1 6 from the 3 6 factors leaves us with 3 2 .