Take the 2-minute tour ×

I know that Euler totient function is multiplicative, that is $\phi(mn) = \phi(m) * \phi(n)$. And obviously it would't have additive feature.

So i'm looking for any existing formula which facilitate calculation of $\phi(N)$ if $\phi(N-1)$ is known. Is there any?


On this page, I found an interesting conjecture, which is hold for some numbers:

For all $n=>4$ it always exists an integer $k, 1<=k<=n-1$ such that:


Solving that would lead to $$\phi((n-k)(n+k))=(n-1)^2-k^2$$ $$\phi(n-k)*\phi(n+k)=(n-1)^2-k^2$$ $$\phi(n+k)=\frac{(n-1)^2-k^2}{\phi(n-k)}$$

and if $n-k$ is prime, then $\phi(n-k) = n-k-1$ $$\phi(n+k)=\frac{(n-1)^2-k^2}{n-k-1}=\frac{(n-1-k)(n-1+k)}{n-k-1}$$ $$\phi(n+k)=n+k-1$$

and since $\phi(n+k)=n+k-1$ then $n+k$ should be prime.

Examples of $n, k$ for which the above conjecture holds:

$n = 27, k=4$

$n = 300, k=31$

$n= 1500, k=1231$

Finding an order among solutions, would lead to a rewritten conjecture:

If $n-k$ is prime then $n+k$ should be prime.

share|improve this question
I don't think there is much you can do. –  Thomas Andrews Dec 3 '12 at 14:45
As number theorists say, 'addition is very hard to understand': prime factorization varies from $N$ to $N+1$ in a very undetermined way, so does Euler's $\phi$ function. –  Berci Dec 3 '12 at 15:10
You can rewrite $\phi((n-k)(n+k))$ as $\phi(n-k)\phi(n+k)$ only if you know that $\gcd(n-k,n+k)=1$. –  Gerry Myerson Dec 6 '12 at 11:30

1 Answer 1

If $\phi(n-1)=8$, then $\phi(n)$ could be $8$ --- or $12$ --- or $16$ --- or $20$ --- or $30$. If $\phi(n-1)=16$, then $\phi(n)$ could be any one of $6,20,24,40,42$, or $60$. More examples available on request (or make 'em yourself from this list), but the point is, knowing $\phi(n-1)$ tells you very little about $\phi(n)$.

share|improve this answer

Your Answer


