# Lehmer’s totient problem

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

Now Lehmer’s 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)$$.

• Would it work to say something like: there exist $x_1,\dotsc,x_6$ such that $n-m=x_1^2+\dotsb+x_4^2$, $n\neq m$, and $mx_5+nx_6=1$? – Zach Teitler Feb 27 at 9:59
• For the new question, let $\alpha$ be any sentence true in $\mathbb Z$ that is independent of the theory of rings, let $\psi_0(x,y)$ be any formula defining $y=\varphi(x)$ in $\mathbb Z$ as in James’s answer, and put $\psi(x,y)=\psi_0(x,y)\land\alpha$ and $A={}$ the theory of rings ${}+\neg\alpha$. – Emil Jeřábek Feb 28 at 8:50
• Why (1) is satisfied? – 喻 良 Feb 28 at 8:53
• Because in $A$, $\psi(x,y)$ implies a contradiction. – Emil Jeřábek Feb 28 at 9:50
• This is not going to help. Put, say, $\psi_1(x,y)=(x\text{ is prime}\land y=1)\lor(x\text{ is not prime}\land y=0)$ and $\psi(x,y)=(\alpha\land\psi_0(x,y))\lor(\neg\alpha\land\psi_1(x,y))$. – Emil Jeřábek Feb 28 at 13:36

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).

• Ah, you are right. But this is not what I want. I need a natural way to translate this. – 喻 良 Feb 27 at 8:10
• If you are changing your question, you should do that as an edit to the body of the question, not as a comment on an answer. Or, you should post a new question, asking what you now realize you ought to have asked (and linking each question to the other). – Gerry Myerson Feb 27 at 11:39
• @喻良 If you do wish to edit a question or ask a new one with clarification, then you should explain what you mean with "natural". – Wojowu Feb 27 at 16:07
• I accept the answer. – 喻 良 Mar 1 at 1:05

For a more algebraic approach, we can add $$\phi$$ to the language of rings, and then state Lehmer's conjecture as:

$$(\text{axiom for } \phi)\ \&\ \phi(n)|(n-1) \implies Prime(n)$$

Here $$Prime$$ is one of a few defintions in the language of rings alone:

\begin{align} x|y &:= \exists u \ ux=y \\ Prime(p) &:= \forall t\ t|p \implies p|t \vee t|1 \\ Power(p,q) &:= \forall t\ t|q \implies p|t \vee t|1 \\ RelPrime(q,r) &:= \forall t\ t|q\ \&\ t|r \implies t|1 \\ PosPrime(p) &:= Prime(p) \ \& \ \phi(p)=p-1 \end{align}

And the axiom for $$\phi$$ is the universally quantified conjunction of

\begin{align} (p=0) \vee (p|1) &\implies \phi(p)=p\\ Prime(p) &\implies \exists u\ u|1 \ \& \ \phi(up)=up-1 \\ Power(p,q) &\implies \phi(pq)=p \phi(q) \\ RelPrime(q,r) &\implies \phi(qr)=\phi(q)\phi(r) \\ \end{align}

If $$\mathbb{Z}$$ satisfies the conjecture, we can ask what induction axioms are necessary to prove it.

In any case, we can ask what other rings have functions $$\phi$$ which satisfy the conjecture in one of these forms.

Update: To make this more recognizable as Lehman's conjecture, we should also ensure that the axioms determine the value of $$\phi$$ for every element in $$\mathbb{Z}$$. The axioms above leave open whether $$\phi(2)=2-1$$ or $$\phi(-2)=-2-1$$, which lead to $$\phi(2)=1$$ or $$\phi(2)=3$$ respectively. The values of $$\phi$$ for 3 and higher primes are also independent of this axiom and this choice.

We have at least three ways to determine $$\phi$$ completely in $$\mathbb{Z}$$ if we want to: either by adding the infinite set of axioms $$\{ PosPrime(2),\ PosPrime(3),\ PosPrime(5),\ PosPrime(7),\ \ldots\}$$ or by working with ordered rings and using the axiom $$1 or by adding the single axiom $$PosPrime(2) \ \&\ PosPrime(3) \ \&\ PosPrime(5) \ \&\ \Big(Prime(p+q+r) \implies$$ $$(PosPrime(p) \ \&\ PosPrime(q) \ \&\ PosPrime(r)) \implies PosPrime(p+q+r)\Big)$$

I like the single axiom, but you can decide which gives the conjecture the most ring-theoretic look.

• Thanks, this does look more algebraic. However, as you said, to prove $\phi$ is exactly Euler's function, we need some complex induction axioms. Is there definition of $\varphi$ so that Lehmer's problem holds for the polynomial ring over $Q$? – 喻 良 Mar 13 at 2:23
• I think there is a definition of $\phi$ which makes this hold in $Q[x]$; let $\phi(q)=q$ for $q\in Q$, and $\phi(p(x))=p(x)-1$ for any monic irreducible $p$. But it would hold trivially because the hypothesis $\phi(p)|p-1$ would only be satisfied in the trivial cases. – Matt F. Mar 18 at 18:42