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.
float P=9;
float D=3;
float ac = P;
while (ac >0)
{
ac = ac - D;
}
if (ac ==0)
System.out.println(P+" es divisible entre "+D);
else
System.out.println(P+" NO es divisible entre "+D);
Es menos eficiente, pero cumple con lo que pides. Si te das cuenta la división no son más que restas consecutivas. Es en lo que se bse este algoritmo.
EDITO
Por el comentario de código no optimizado añado esta solución, una mejora de la primera:
int num = 9;
int div = 2;
int resto= num/div*div;
System.out.print("¿Es divisible "+num+" entre "+ div +"? : "+ (resto== num));
Por supuesto esto lo metería en una función devolverá verdadero o falso