Q44 Matemática  (Tournament Of Towns 2012)

Há $1000000$ soldados em uma linha. O sargento divide a linha em segmentos de $100$ (o comprimento dos diferentes segmentos pode ser diferente) e permuta os segmentos (sem alterar a ordem dos soldados em cada segmento) formando uma nova linha. O sargento repete esse procedimento várias vezes (divide a nova linha em segmentos do mesmo comprimento e os permuta exatamente da mesma maneira que na primeira vez). Cada soldado originário do primeiro segmento registrou o número de procedimentos realizados que o levaram a retornar ao primeiro segmento pela primeira vez. Prove que no máximo $100$ desses números são diferentes.