Puedes habría que hacerlo viendo si el cociente tiene decimales. Si divides A/B te dará un cociente, si ese cociente es igual al resultado de redondearlo entonces el resto es 0.   
Por ejemplo 9/2 da de cociente 4.5, al redondearlo obtienes 4, por tanto los números no son divisibles.    
Algo así.
```
        float P=9;
        float D=3;
        double cociente;
        cociente = P/D;
        //double entero = Math.floor(cociente);
        double entero = (int)cociente;
        if(cociente == entero)
            System.out.println("El número es divisible");
        else
            System.out.println("El número NO es divisible");
```
Esto te serviría para saber si dos números son divisibles sin usar %, podrías usar una función con este código para determinar si un número tiene divisores o sea si es primo o no.   
**EDITO**   
Sin usar Math se puede hacer una conversión de tipos.   
Pero sin usar divisiones se puede saber si un número es divisible por otra por sumas. Para saber si 9 es divisible entre 3, se le resta 3 a 9 hasta que de 0 o menos de 0. Si da 0 son divisibles si es negativo no es divisible.   
9 - 3 = 6   
6 - 3 = 3   
3 - 3 = 0   
Son divisilbes.    
9/4:  
9 - 4 = 5  
5 - 4 = 1  
1 - 4 = -3  
Da negativo, no son divisibles.