Context: Presburger arithmetic is the theory $\tau$ of structure $$ A = (\mathbb{N},0,1,+,\{c|\cdot\}_{c\in\mathbb{N}})$$ where for each integer $c > 1$, the unary predicate c|n holds if and only if n is divisible by c. Recall that $\tau$ has quantier-elimination.
The first part is to show that suppose a set $S \in \mathbb{N}$ is ultimately periodic if there exist positive integers $n_0$ and $p$ such that for all $n > n_0$, $n \in S$ iff $ n + p \in S$. Show that any quantifier-free formula that mentions a single variable $x$ defines an ultimately periodic subset of $\mathbb{N}$.
Afterwards we should be able to use this result to show that there is no formula on free variables $x$, $y$ and $z$ that defines the multiplication relation $M = \{(a,b,c)\in \mathbb{N}^3: ab = c\}$ on the structure $A$.
I'm completely lost on this question and I cannot see a relation on the two parts of the question. I have read the post here Presburger arithmetic but don't think it is too helpful. Any help would be appreciated!
Clearly, the unions, intersections and complements of ultimately periodic sets are again ultimately periodic. Since a quantifier-free formula is a boolean combination of atomic formulas, all we have to do is to prove the following claim :
Up to equivalence, there are of two kinds of atomic formulas in the variable $x$ :
Atomic formulas of kind 1. define singletons (or the empty set if $n>m$, or the whole set if $n=m$), which are clearly ultimately periodic.
Atomic formulas of kind 2. define a ultimately periodic set with period $p = c$ because if $c \mid (x + n)$, then $c \mid (x + n + c)$. $\square$
Hence, every quantifier-free formula in a single variable defines a ultimately periodic set.