En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos.
Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones

  
    
      
        
          a
          
            n
            −
            1
          
        
         
        ≡
         
        1
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle a^{n-1}\ \equiv \ 1{\pmod {n}}}
  así como

  
    
      
        
          a
          
            (
            
              n
              −
              1
            
            )
            
              /
            
            q
          
        
         
        ≢
         
        1
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}}
  para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto.
Este algoritmo es correcto ya que si a pasa el primer paso, podemos deducir que a y n son coprimos. Si a también pasa el segundo paso, entonces el orden de a en el grupo (Z/nZ)* es igual a n − 1, lo que significa que el orden de ese grupo es n − 1, implicando que n es primo. Recíprocamente, si n es primo, entonces existe una raíz primitiva módulo n y cualquier raíz primitiva pasará ambos pasos del algoritmo.