Skip to content
GitHub

Quadrados Perfeitos Tem um Número Ímpar De Divisores

Eu estava resolvendo o URI1371 e encontrei uma propriedade interessante.

Suponha que você queira saber o número de divisores de um número natural a. Com o Teorema Fundamental da Aritmética, você pode decompor a em seus fatores primos, desse modo:

a=p1k1⋅p2k2… pn−1kn−1⋅pnkna = p_1^{k_1} \cdot p_2^{k_2} \dots \ p_{n-1}^{k_{n-1}} \cdot p_n^{k_n}

O número de divisores de a vai ser o resultado do produto dos expoentes, somados 1, dos fatores primos, ou seja, sendo d o número de divisores:

d=(k1+1)⋅(k2+1)… (kn−1+1)⋅(kn+1)d = (k_1+1) \cdot (k_2+1) \dots \ (k_{n-1} + 1) \cdot (k_n+1)

Quando elevamos a ao quadrado, obtemos:

a2=p12⋅k1⋅p22⋅k2… pn−12⋅kn−1⋅pn2⋅kna^2 = p_1^{2 \cdot k_1} \cdot p_2^{2 \cdot k_2} \dots \ p_{n-1}^{2 \cdot k_{n-1}} \cdot p_n^{2 \cdot k_n}

Note que, agora, todos os expoentes são pares, ou seja, quando calcular o número de divisores de a2, teremos um produto de ímpares, logo todo quadrado perfeito tem um número ímpar de divisores.