-element subsets of can be ordered to form a geometric progression modulo with common ratio
How manyDetails and assumptions
The sequence is a geometric progression modulo with common ratio if .
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.
Note that 1 0 2 5 = 5 2 ⋅ 4 1 . Since 2 1 0 ≡ − 1 ( m o d 1 0 2 5 ) , the order of 2 in the multiplicative group modulo 4 1 is 2 0 . It is easy to check that the order of 2 in the multiplicative group modulo 2 5 is also 2 0 . This implies that if a , 2 a , 4 a , . . . , 2 1 9 a is a geometric progression modulo 1 0 2 5 , then 2 2 0 a = a , and the progression can be "rotated" to start from every 2 i a .
The numbers 1 , 2 , . . . , 2 1 9 are distinct modulo 4 1 and modulo 2 5 , but they are not distinct modulo 5 . Indeed, 2 4 ≡ 2 0 ( m o d 5 ) . So if a ≡ 0 ( m o d 5 ⋅ 4 1 ) , then a ≡ 2 4 a ( m o d 1 0 2 5 ) , and we do not get a 2 0 -term geometric progression. There are 5 such residues a modulo 1 0 2 5 . All other a do give a geometric progression of 2 0 distinct residues: if a = 0 ( m o d 4 1 ) , then they are distinct modulo 4 1 and if a ≡ 0 ( m o d 4 1 ) , but a = 0 ( m o d 5 ) , then they are distinct modulo 2 5 . Note that, from the discussion in the first paragraph, each set gets counted 2 0 times, so the answer is 2 0 1 0 2 5 − 5 = 5 1 .