Questions are from Mathematics for Computer Science by Albert R. Meyer, Eric Lehman, and Frank Thomson Leighton.
The question asks us to write the following statements in formal logic notation:
(a) $m$ is a divisor of $n.$
(b) $n$ is a prime number.
(c) $n$ is a power of prime.
The domain of discourse is nonnegative integer, $\mathbb{N} \cup \{0\}.$ In addition to the propositional operators, variables and quantifiers, we may define predicates using addition, multiplication, and equality symbols, and nonnegative constants $(0, 1, \dots),$ but no exponentiation (like $x^y$).
MY SOLUTIONS:
(a) $\text{DIV}(m, n) ::= \exists k : (k \cdot m=n)$
(b) $\text{PRIME}(n) ::= \forall k: [\text{DIV}(k, n) \Rightarrow (k=1 \vee k=n)].$
(c) $\text{POWER PRIME}(n) ::= \exists m : \text{PRIME}(m) \wedge $$\forall k: [\text{DIV}(k, n) \Rightarrow (\text{DIV}(m, k) \vee k=1)].$
Are the answers correct or not? And I would like to know whether somebody can provide more concise and alternative solutions to any of these questions. I would appreciate your answers.
Your solution for (a) is correct. Note that, according to this definition, every nonnegative integer ($0$ included) is a divisor of $0$, and $0$ is not a divisor of any other nonnegative number.
Some textbooks exclude $0$ from the definition of divisor (see here for a short justification), in that case the correct formalization of "$m$ is a divisor of $n$" would be:
(a') $\ \text{DIV}(m,n) \ : \quad m \neq 0 \land n \neq 0 \land \exists \, k \, (m \cdot k = n)$
The choice between (a) and (a') depends on the definition of divisor adopted by your textbook or course. The way you formalize $\text{DIV}(m,n)$ affects the way you formalize the other statements.
Note that $m \neq n$ is just a shorthand for $\lnot (m = n)$, so it can be expressed in your language.
A nonnegative integer $n$ is prime if its only divisors are $1$ and $n$ and it is greater than $1$ (see here for a short discussion about the advantages of excluding $1$ from prime numbers). Since $0$ has many divisors other than $1$ and $0$, it is equivalent to say that a nonnegative integer $n$ is prime if its only divisors are $1$ and $n$ and it is different from $1$. So, your answer is wrong, the correct formalization of "$n$ is prime" is:
(b) $ \ \text{PRIME}(n) \ : \quad n \neq 1 \land \forall k \, (\text{DIV}(k,n) \to (k=1 \lor k = n))$
Formalization (b) above assumes that the definition of divisor includes $0$, i.e. $\text{DIV}(m,n)$ is defined as in your answer (a). If your definition of divisor excludes $0$, i.e. $\text{DIV}(m,n)$ is defined as in (a'), then $\text{DIV}(k,0)$ is false for all $k$ and so $\forall k \, (\text{DIV}(k,0) \to (k=1 \lor k = 0))$ is vacuously true, hence it is necessary to explicitly exclude $0$ from the definition of prime number. Therefore, if $\text{DIV}(m,n)$ is defined as in (a'), then the correct formalization of "$n$ is prime" is:
(b') $ \ \text{PRIME}(n) \ : \quad n \neq 0 \land n \neq 1 \land \forall k \, (\text{DIV}(k,n) \to (k=1 \lor k = n))$
Your solution for (c) is correct, if you use (a) as definition of $\text{DIV}(m,n)$.
Note that $0$ is not a power of any prime number.
If your definition of divisor excludes $0$, i.e. $\text{DIV}(m,n)$ is defined as in (a'), then $\text{DIV}(k,0)$ is false for all $k$ and so $\forall k \, (\text{DIV}(k,0) \to (\text{DIV}(m,k) \lor k = 1))$ is vacuously true, hence it is necessary to explicitly exclude $0$ from the definition of power of prime number. Therefore, if $\text{DIV}(m,n)$ is defined as in (a'), then the correct formalization of "$n$ is power of a prime" is:
(c') $\ \text{POWER_PRIME}(n) \ : $
$$\quad n \neq 0 \land \exists m \,\Big(\text{PRIME}(m) \land \forall k \, \big(\text{DIV}(k, n) \to (\text{DIV}(m, k) \vee k=1) \big) \Big).$$