A characterization of nonprime powers
Authors : Raul Duran Diaz, Luis Hernandez Encinas, Agustin Martin Muñoz, Jaime Muñoz Masque, Seok-zun Song
Pages : 1248-1259
View : 7 | Download : 5
Publication Date : 9999-12-31
Article Type : Makaleler
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