2 To The Ten Is 2 High

Number Theory Level pending

How many 20 20 -element subsets of { 0 , 1 , 2 , . . . , 1024 } \{0,1,2,...,1024\} can be ordered to form a geometric progression modulo 1025 1025 with common ratio 2 ? 2?

Details and assumptions

The sequence { a i } \{a_i \} is a geometric progression modulo 1025 1025 with common ratio 2 2 if a i a 1 × 2 i 1 ( m o d 1025 ) a_i \equiv a_1 \times 2^{i-1} \pmod{1025} .


The answer is 51.

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

Calvin Lin Staff
May 13, 2014

Note that 1025 = 5 2 41. 1025=5^2\cdot 41. Since 2 10 1 ( m o d 1025 ) , 2^{10}\equiv -1 \pmod {1025}, the order of 2 2 in the multiplicative group modulo 41 41 is 20. 20. It is easy to check that the order of 2 2 in the multiplicative group modulo 25 25 is also 20 20 . This implies that if a , 2 a , 4 a , . . . , 2 19 a a,2a,4a,...,2^{19}a is a geometric progression modulo 1025 , 1025, then 2 20 a = a , 2^{20}a=a, and the progression can be "rotated" to start from every 2 i a . 2^i a.

The numbers 1 , 2 , . . . , 2 19 1,2,...,2^{19} are distinct modulo 41 41 and modulo 25 , 25, but they are not distinct modulo 5. 5. Indeed, 2 4 2 0 ( m o d 5 ) . 2^4\equiv 2^0 \pmod 5. So if a 0 ( m o d 5 41 ) , a\equiv 0 \pmod {5\cdot 41}, then a 2 4 a ( m o d 1025 ) , a\equiv 2^4a \pmod {1025}, and we do not get a 20 20 -term geometric progression. There are 5 5 such residues a a modulo 1025. 1025. All other a a do give a geometric progression of 20 20 distinct residues: if a 0 ( m o d 41 ) , a\neq 0 \pmod{41}, then they are distinct modulo 41 41 and if a 0 ( m o d 41 ) , a\equiv 0 \pmod{41}, but a 0 ( m o d 5 ) , a\neq 0 \pmod{5}, then they are distinct modulo 25. 25. Note that, from the discussion in the first paragraph, each set gets counted 20 20 times, so the answer is 1025 5 20 = 51. \frac{1025-5}{20}=51.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...