Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)}$ ?

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

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
    
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 , –  Fayez Abdlrazaq Deab Jan 22 '13 at 23:34
    
@FayezAbdlrazaqDeab I have already covered $2^n$. You are right about $2p$ - thanks, will reflect. The conclusion still holds. –  Jan Dvorak Jan 22 '13 at 23:41
    
@FayezAbdlrazaqDeab Covered $2p$ - thanks for noting. –  Jan Dvorak Jan 22 '13 at 23:47
1  
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. –  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.

share|improve this answer
    
A scatter plot might be more readable than a line plot –  Jan Dvorak Jan 22 '13 at 21:50
    
@JanDvorak I agree. Let me make the new one. –  Sam DeHority Jan 22 '13 at 21:55
    
oeis.org/… (thanks @JavaMan for the sequence number) shows some very dense lines with regular density, which might be worthwhile to explain. –  Jan Dvorak Jan 22 '13 at 21:59
    
The new picture has been added. –  Sam DeHority Jan 22 '13 at 22:10
1  
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. –  Sam DeHority 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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