3
$\begingroup$

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?

Updated

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:

$\phi(n^2-k^2)=(n-1)^2-k^2$

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.

  • 2
    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$.2012-12-06

1 Answers 1

4

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