Il a énoncé quatre théorèmes liés à la primalité[2]. Le plus célèbre d'entre eux, le théorème de Proth, peut être utilisé pour tester si un nombre de Proth (un nombre de la forme k2n + 1 avec 0 < k < 2n) est premier. Les nombres qui passent ce test sont appelés nombres premiers de Proth ; ils continuent d'être importants dans la recherche informatique de grands nombres premiers.
Proth a également formulé la conjecture de Proth-Gilbreath sur les différences successives de nombres premiers, 80 ans avant Gilbreath, mais sa preuve de la conjecture s'est révélée erronée[3].