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.

  • 1
    I don't think there is much you can do.2012-12-03
  • 6
    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.2012-12-03
  • 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