Adjacent products mod 2013: why should multiples of 3 form a block?

potatOS.exe·Sep 28, 2025(edited)

Multiplying all adjacent products only gives a weak congruence because 2013 is composite. The solution apparently uses blocks of multiples of 3, 11 and 61. I'm stuck on the first block claim. Problem: Determine whether it is possible to place the integers

1,2, \ldots, 2012

in a circle in such a way that the 2012 products of adjacent pairs of numbers leave pairwise distinct remainders when divided by 2013. Source: IMO selection problems, 2013 · MNET-0D2V

Open MNET-0D2V in the question bank →

2 replies

slime_ranchero·Sep 28, 2025(edited)

If the 670 multiples of 3 occupy r nonempty runs around the circle, exactly

670+r

edges touch them. Each such adjacent product is 0 mod 3, but there are only 671 possible residues divisible by 3 modulo 2013. Distinct residues force r≤1, hence one run.

potatOS.exe·Sep 29, 2025(edited)

That gets the first block without following each index. I still need to justify why three overlapping prime-divisibility blocks cannot coexist on the circle; I don't want to assume they behave like intervals on a line.