I'm trying to express this idea using FO+TC (First-order Logic with Transitive closure) with the signature $\Sigma = \{+, s\}$ (+ addition function, s is a successor function) over the standard structure of the natural numbers:
$y = x^N$
($x$ is a power on $N$, for some natural $N$)
N.B: I expressed GCD using FO+TC, so i tried to play with something like "the GCD of $x$ and $y$ is $x$" but actually its just a starting direction i have.
Any ideas how can i express it ?
Consider the formula $$ \varphi(x, y,z) := z = x*y. $$ Then $$ \varphi(1,x,x), \varphi(x,x,x^2), \dotsc, \varphi(x^n, x, x^{n+1}), \text{ and }(\forall y)\,\varphi(y, x, x*y). $$ Let $T$ abbreviate the transitive closure of $\varphi(a,x,b)$, which uses $x$ as a parameter, so that $$ T(x,y) := \operatorname{TC}(a,b)\varphi(a,x,b)(x,y). $$ Then $$ y = x^N \text{ for some $N\ge 0$}\iff (y = 1 \lor T(1,y)). $$