A characterization of nonprime powers

Authors: RAUL DURAN DIAZ, LUIS HERNANDEZ ENCINAS, AGUSTIN MARTIN MUÑOZ, JAIME MUÑOZ MASQUE, SEOK-ZUN SONG

Abstract: A criterion is presented in order to decide whether agiven integer is a prime power or not. The criterion associatesto each positive integer $m$ a finite set of integers$\mathcal{S}(m)$, each of them $\le m$ and the propertiesof this set are studied. The notion of complementary pairsin $\mathcal{S}(m)$ is introduced and it is proved that if one isable to determine a complementary pair $n,n^\prime$, thena partial factorization of the odd integer $m$ can be obtainedin polynomial time. Some particular cases and examples of these resultsare given.

Keywords: Complementary pair, partial factorization, prime power,

Full Text: PDF