2017 was a prime failure

Suppose there is a 2016 x 2016 matrix. In how many ways can you fill all the cells with integers so that if you multiply all the entries in any particular row or column, the result is always 2? As the result is large, find the result modulo 2017. That means if the number of ways can be written in the form 2017 k + r , 2017k + r, find r . r.


The answer is 2015.

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

First, solve the problem if the target was to get 1 for each row and each column. 1 can be formed from a multiplicative combination of 1 and -1. So, for a row or a column, we are free to set either of 1 or -1 in 2015 of the 2016 cells. This can be done in 2 ( 2016 1 ) ( 2016 1 ) 2^{(2016-1)(2016-1)} ways. How? We can do this for first 2015 rows:- fill according to your wish in the first 2015 cell of the row, the cell that is left can be filled by 1 if all the 2015 other cells multiply into 1 or by -1 if the other 2015 multiply into -1. That ensures 1 in each row and each column after the multiplication of the 2016 integers we have filled in. The last row is deterministic and consistent due to the constraint.

Now how to make the result 2 from here? Simple. We have to make sure in each row and each column, we multiply a single 2 in any of the 2016 cells. That makes the result 1x2 = 2 in each row and each column. This can be done in 2016! ways (a combination of rows with columns fixed or vice versa).

So the answer is 2 ( 2016 1 ) ( 2016 1 ) 2^{(2016-1)(2016-1)} x 2016! mod 2017

Now, 2017 is a prime. We know from FLT, a p 1 = 1 a^{p-1}=1 mod p for any prime p. And from Wilson's theorem, ( p 1 ) ! = 1 (p-1)!=-1 mod p if p is prime.

So, 2016 ! = 1 2016! = -1 mod 2017

2 ( 2016 1 ) ( 2016 1 ) 2^{(2016-1)(2016-1)} = 2 ( 201 6 2 2.2016 + 1 ) 2^{(2016^{2} -2.2016+1)} = 2 2016 k 2^{2016k} x 2. As, 2 2016 2^{2016} = 1 mod 2017, so, 2 2016 k 2^{2016k} x 2 = 1 k 1^{k} x 2 mod 2017 = 2 mod 2017

So, finally, 2 ( 2016 1 ) ( 2016 1 ) 2^{(2016-1)(2016-1)} x 2016! = 2 x -1 mod 2017 = 2017-2 = 2015. This is the answer modulo 2017.

Thank you!

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...