Bilangan komposit  yang memenuhi  disebut bilangan prima semu. Kongruensi tersebut merupakan kongruensi pada Teorema Little Fermat yang telah dimodifikasi oleh Euler. Bilangan prima semu yang basis dan bilangan kompositnya saling relatif prima disebut bilangan prima semu absolut. Bilangan prima semu yang memenuhi uji Miller dikenal dengan bilangan prima semu kuat. Selanjutnya, bilangan prima semu yang memenuhi kriteria Euler disebut dengan bilangan prima semu euler. Penelitian ini membahas ketakhinggaan bilangan prima semu dan bilangan prima semu kuat dengan basis , syarat cukup bilangan prima semu absolut, kemudian hubungan bilangan prima semu dan bilangan prima semu kuat dengan bilangan prima semu Euler.

Selanjutnya, pada jenis-jenis bilangan prima semu, terdapat beberapa hubungan. Hubungan yang pertama, jika  merupakan bilangan prima semu Euler dengan basis , maka  merupakan bilangan prima semu dengan basis . Hubungan yang kedua, jika  merupakan bilangan prima semu kuat dengan basis , maka  merupakan bilangan prima semu Euler dengan basis . Hubungan yang ketiga, jika m merupakan bilangan prima semu Euler dengan basis a dan , maka m merupakan bilangan prima semu kuat dengan basis a dan jika  dan m merupakan bilangan prima semu Euler dengan basis a, maka m merupakan bilangan prima semu kuat dengan basis a.