What is the value of

$$\large n\pmod {\phi(n)}$$

where $\phi(n)$ is the Euler function, I know that if $n$ prime the this value is $1$, because $\phi(n)=n-1$, but for random natural number this statement doesn't hold !!

So what to do ?
Is there a simple way to compute this question without computing ${\phi(n)}$ ?

  • 3
    $\begingroup$ What do you want the value to be in terms of? This question seems a little too broad. $\endgroup$ – dinoboy Jan 22 '13 at 21:29
  • 1
    $\begingroup$ Have you tried it out for $1\le n\le 36$, say? $\endgroup$ – Lubin Jan 22 '13 at 21:38
  • 1
    $\begingroup$ The sequence does appear in OEIS. $\endgroup$ – JavaMan Jan 22 '13 at 21:57
  • $\begingroup$ Computing $\phi(n)$ is computationally trivial (polynomial) knowing the factorization. Is "without knowing the number factorisation" what you want? $\endgroup$ – John Dvorak Jan 22 '13 at 21:58
  • $\begingroup$ I want to know if our input is n , does finding the above value is as hard to compute the Euler function ? $\endgroup$ – Fayez Abdlrazaq Deab Jan 22 '13 at 22:04

Let's do some specific cases ($p$,$q$,$r$ are distinct primes):

$$p \mod \phi(p)$$ $$=p \mod (p-1) = 1$$

$$pq \mod \phi(pq)$$ $$=pq \mod (p-1)(q-1) $$ $$= (pq-(p-1)(q-1)) mod (p-1)(q-1)$$ $$= p+q-1 $$ unless $q=2$ (or $p=2$) - then it equals $(p+2-1)-(p-1)=2$ (except for 6 - then it's zero)

$F(pqr) = pqr - k(p-1)(q-1)(r-1)$
$F(pqrs) = pqr - k(p-1)(q-1)(r-1)(s-1)$
(note that I no longer claim $k=1$)

$$ p^n \mod \phi(p^n) $$ $$ = p^n \mod (p-1) p^{n-1} $$ $$ = p^{n-1}$$ unless $p=2$ (then it equals zero).

In short: You need the factorisation to compute $F$. At this point, unless you know the form in advance you know in advance $n$ is a prime power or a product of two primes, the easiest way to compute $n \mod \phi(n)$ is $n \mod \phi(n)$.

Also note that if you have $n$ and $n \mod \phi(n)$, you also have $k*\phi(n)$, which aids in easy recovery of $\phi(n)$ if $k$ is supected to be low, which, in turn, yields complete factorisation to a very important class of $n$...

I am not saying you will not find an easy way of computing $f$ without a factorisation. I am saying: If you do - congratulations, you have cracked RSA (and discovered yet another primality test).

  • $\begingroup$ the first case is not correct for example : n=6=2*3 , n mod phi(n)=0 != p+q-1=4 , and in the case of power of prime for example : n=8 , $\endgroup$ – Fayez Abdlrazaq Deab Jan 22 '13 at 23:34
  • $\begingroup$ @FayezAbdlrazaqDeab I have already covered $2^n$. You are right about $2p$ - thanks, will reflect. The conclusion still holds. $\endgroup$ – John Dvorak Jan 22 '13 at 23:41
  • $\begingroup$ @FayezAbdlrazaqDeab Covered $2p$ - thanks for noting. $\endgroup$ – John Dvorak Jan 22 '13 at 23:47
  • 1
    $\begingroup$ The value of $k$ here is quite low, $O(\log \log n)$ at most. Even for much larger values of $k$, and any number of primes dividing $n$, there is a randomized algorithm to factor $n$ given a multiple $k\phi(n)$ (without knowing $k$ or $\phi(n)$ explicitly). So this problem is just as hard as factoring, even in general. $\endgroup$ – Erick Wong Jan 23 '13 at 2:37

I do not have a closed form solution, and I'm not sure there is one. I did look at the function $n \mod \phi(n)$ in mathematica and noticed some interesting patterns though.

Mathematica output

Notice that there are multiple "layers" similar to how the graph of the totient function itself looks.

Honestly, the form in which you have your question is probably the simplest form for the function.

  • $\begingroup$ A scatter plot might be more readable than a line plot $\endgroup$ – John Dvorak Jan 22 '13 at 21:50
  • $\begingroup$ @JanDvorak I agree. Let me make the new one. $\endgroup$ – guest196883 Jan 22 '13 at 21:55
  • $\begingroup$ oeis.org/… (thanks @JavaMan for the sequence number) shows some very dense lines with regular density, which might be worthwhile to explain. $\endgroup$ – John Dvorak Jan 22 '13 at 21:59
  • $\begingroup$ The new picture has been added. $\endgroup$ – guest196883 Jan 22 '13 at 22:10
  • 1
    $\begingroup$ Computing $\phi (n)$ is quite trivial if you know the factors, as it is simply $n \prod _{p|n} (1-\frac{1}{p})$. Factoring an integer can be remarkably complex, and the best known algorithms are exponential in the worst case. $\endgroup$ – guest196883 Jan 22 '13 at 22:29

The value that you are looking for is the sum of the factors - 1. Example 13199 - 12936 = 263, factors are 67 and 197.

  • $\begingroup$ How is "sum of the [prime?] factors - 1" related to the sequence in question? They are not equal... $\endgroup$ – John Dvorak Jan 22 '13 at 22:10
  • $\begingroup$ $\phi(4) = 2; 4 \mod \phi(4) = 0$. The factors of $4$ are $1,2,4$. $\endgroup$ – John Dvorak Jan 22 '13 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.