Euler’s totient function $\varphi$ is a function defined over $\mathbb{N}$ so that $\varphi(n)=|\{m\mid m<n\wedge (m,n)=1\}|$.


Now [Lehmer’s totient problem](https://en.wikipedia.org/wiki/Lehmer%27s_totient_problem) asks whether $n$ is prime iff $\varphi(n)$ divides $n-1$. 


I am curious whether the question can be expressed as a question in ring language. More specifically, whether there is a firs order formula $\psi(x)$ in the ring language so that $\mathbb{Z}\models \psi(n)$ if and only if $\varphi(n)$ divides $n-1$. 


**Remark** As James pointed out, the question has a positive answer. But what I really want is an algebraic answer. Probably the question was not in a proper shape. How about this: 


Whether there is a first order formula $\psi(x,y)$ in the ring language so that there is theory $A$ extending axioms of ring theory in a proper way (which is not necessary consistent with theory of $\mathbb{Z}$) so that 


(1). $ A\vdash\forall x\exists y\psi(x,y)\wedge (\forall x \forall y(\psi(x,y)\rightarrow( y\mbox{ divides } x-1\leftrightarrow x\mbox{ is prime})) ) $; and


(2). For all $m$ and $n$, $\mathbb{Z}\models \psi(n,m)$ if and only if $m=\varphi(n)$.



Lehmer’s totient problem
Yes. Every computable relation on $\mathbb{Z}$ can be defined with a first-order formula in the language of rings. 


The idea is to "arithmetize" computation: encode Turing machines and their states as natural numbers in such a way that the basic operations like changing the state of the head, writing a bit, etc. are all given by arithemtic relations. This is the basis of Kleene's proof of Godel's incompleteness theorem (Godel's proof used the arithmetization of syntax, rather than computation). 


