A criterion is presented in order to decide whether a given integer is a prime power or not. The criterion associates to each positive integer m a nite set of integers S(m) , each of them < m, and the properties of this set are studied. The notion of complementary pairs in S(m) is introduced and it is proved that if one is able to determine a complementary pair n; n ′ , then a partial factorization of the odd integer m can be obtained in polynomial time. Some particular cases and examples of these results are given. Key words: Complementary pair, partial factorization, prime power
Acknowledgment
This work was supported by the European Union FEDER funds distributed through Ministerio de Economía y Competitividad (Spain) under the project TIN2014-55325-C2-1-R (ProCriCiS) and through Comunidad de Madrid (Spain) under the project S2013/ICE-3095-CM (CIBERDINE).
