modulo question 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)}$ ? 
 A: 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. 

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

Similarly,
$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).
A: The value that you are looking for is the sum of the factors - 1.  Example 13199 - 12936 = 263, factors are 67 and 197.
Ron

