O matemático húngaro Paul Erdös (1913-1996) é um velho conhecido nosso – sempre aparece por aqui com algo interessante. Além de ter sido um dos matemáticos mais importantes e prolíficos do século passado, com contribuições em diversas áreas da matemática, Erdös também foi um grande proponente de ‘problemas elementares’, aqueles que exigem pouca ‘bagagem’ matemática para serem entendidos, mas que podem ser bem desafiadores. Além disso, ele tinha uma lista de problemas favoritos, que passava adiante sempre que possível. Relembremos um deles.

Em uma visita anterior de nosso amigo húngaro a esta coluna (‘Erdös e épsilons’, CH 346), apresentamos o seguinte problema: considere os inteiros de 1 a 100. Feito isso, escolha 51 entre eles. Nesse conjunto, haverá um par de números que não têm divisor comum, ou seja, que são primos entre si. Que tal conferir aquela coluna? 

O problema que vamos tratar nesta coluna é parecido, mas, de certa forma, complementar: novamente, considere os números inteiros positivos de 1 a 100, escolhendo 51 entre eles. Mas, desta vez, mostre que, entre os números escolhidos, há dois deles tais que um divide o outro.

Como sempre, comecemos com observações simples para nos situarmos melhor. Primeiro, qualquer número pode ser decomposto em fatores primos, ou seja, ser escrito como um produto de números primos, que são aqueles que são divisíveis só por 1 e por eles mesmos, como 5 e 13. Já 15 não é primo, pois 15 = 3 x 5 – nota: essa decomposição é única, um resultado importante que vamos usar adiante.