Vad räknar du som lekmansmatematik?
Låt n vara ett udda tal.
Finn heltal r, s sådana att n = 2^r * s + 1 och s inte innehåller någon faktor av 2. (Vilket alltid är möjligt).
Välj ett tal a från intervallet [1, n - 1].
Beräkna resten av division av a^s med n. Om denna rest är 1, så "klarar" n testet.
Beräkna resten av division av a^(2^j * s) med n, för alla j i intervallet [0, r - 1]. Om någon av resterna är lika med n - 1, så "klarar" n testet.
Annars "klarar" n inte testet.
Repetera för så många a du känner för (finns säkert uppskattningar på hur stor sannolikheten för att n är ett primtal är beror på hur många olika "a" man testar med).