IMPORTANT: This applies to the wrong version of the problem, where it was "402" instead of "420".

i can't manage to solve this problem. can you help me?

This is a very nasty problem. I wonder if there is a nice solution (my solution is a dirty brute-force which took me something like 3 hours )

Could you write a sketch of the solution? I mean main results and such.

Farenhajt wrote: If $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ where $p_i$ is prime, then $\phi(n)=p_1^{\alpha_1-1}(p_1-1)p_2^{\alpha_2-1}(p_2-1)\dots p_k^{\alpha_k-1}(p_k-1).$ Hence $p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}-p_1^{\alpha_1-1}(p_1-1)p_2^{\alpha_2-1}(p_2-1)\dots p_k^{\alpha_k-1}(p_k-1)=2\cdot 3\cdot 67.$ It's now obvious that $\alpha_i\ngtr 2$, since otherwise LHS wouldn't be squarefree. Denote $\{u_i\}_{i=1}^{r}=\{p_i|\alpha_i=1\}$ and $\{v_i\}_{i=1}^{s}=\{p_i|\alpha_i=2\}.$ \begin{eqnarray*}u_1u_2\dots u_rv_1^2v_2^2\dots v_s^2-(u_1-1)(u_2-1)...(u_r-1)v_1(v_1-1)v_2(v_2-1)\dots v_s(v_s-1)=2\cdot 3\cdot 67.\end{eqnarray*} Since LHS is divisible by $v_i$, it follows that $s=3$ and $v_1=2, v_2=3, v_3=67.$ Hence \begin{eqnarray*}u_1u_2\dots u_r2^23^267^2-(u_1-1)(u_2-1)...(u_r-1)\cdot 2\cdot 1\cdot 3\cdot 2\cdot 67\cdot 66=2\cdot 3\cdot 67\end{eqnarray*}, or \begin{eqnarray*}402u_1u_2\dots u_r-132(u_1-1)(u_2-1)...(u_r-1)=1.\end{eqnarray*} But in that case LHS is even, hence $n$ is squarefree. Therefore, $p_1p_2\dots p_k-(p_1-1)(p_2-1)\dots (p_k-1)=402$ If all $p_i$ are odd, then LHS is odd, hence $p_1=2$: $2p_2\dots p_k-(p_2-1)\dots(p_k-1)=402$ $(p_2-1)\dots(p_k-1)$ is divisible by $2^{k-1}$, hence $2^{k-2}|p_2p_3\dots p_k-201$, and I'm stuck I think Farenhajt's solution is good.Let me try to complete it.While $2p_2\dots p_k-(p_2-1)\dots(p_k-1)=402$ then we can know $p_2\dots p_k<402$,so$k<5$for$3*5*7*11>402$ then the problem turn an easy equation. we only need to make out three equation. 2a-(a-1)=402,ab-(a-1)(b-1)=402,abc-(a-1)(b-1)(c-1)=402(a,b,c are all prime) the first and the second is quite easy,so I only do someting about the third. we could know $abc<402$,so $min{a,b,c}<8$.we could try a=3,5,7,then the third can turn the second,so we solve the problem.finally we know n=802,546.

Farenhajt wrote: \begin{eqnarray*}u_1u_2\dots u_rv_1^2v_2^2\dots v_s^2-(u_1-1)(u_2-1)...(u_r-1)v_1(v_1-1)v_2(v_2-1)\dots v_s(v_s-1)=2\cdot 3\cdot 67.\end{eqnarray*} Since LHS is divisible by $v_i$, it follows that $s=3$ and $v_1=2, v_2=3, v_3=67.$ I do not see why it follows. I think it follows that $s\leq 3$ and $v_i\in\{2,3,67\}$ for $i=1..s$, nothing more.

It is very esay question.. I have solved that

Ditdo: Please post your solution.

ok!

You can see my solution by one click!

Ditdo wrote: so $n=2m$ and $\varphi(2m) = \varphi(m)$ Only if $m$ is odd that may not be the case.

Maxal,$m$ is odd,because if $m$ is even then $n\vdots4$ Let us return to the equation $n=\phi(n)+402$ Because $n\vdots4$, and $\phi(n)\vdots4$ it follows that $402\vdots4$.Contradiction!!!!! Also $n\not=2^{k}$.If so then we find that $2^k=2^{k}-2^{k-1} +402$,more clearly $2^k=2^{k-1}+402$,clearly $k\le2$,because 402 is not divisible by $2^k$ for any $k\ge2$.By checking we get no answer.

spider_boy wrote: Maxal,$m$ is odd,because if $m$ is even then $n\vdots4$ Let us return to the equation $n=\phi(n)+402$ Because $n\vdots4$, and $\phi(n)\vdots4$ Why $\phi(n)\vdots4$ ?

maxal wrote: spider_boy wrote: Maxal,$m$ is odd,because if $m$ is even then $n\vdots4$ Let us return to the equation $n=\phi(n)+402$ Because $n\vdots4$, and $\phi(n)\vdots4$ Why $\phi(n)\vdots4$ ? Look, maxal ,let $n=p_1^{q_1}p_2^{q_2}\ldots{p_k^{q_k}}$,then $\phi(n)=p_1^{q_1-1}\ldots{p_k^{q_k-1}}(p_1-1)(p_2-1)\ldots{(p_k-1)}$ Now,if $n\not=2^{k}$ then n has another prime divisor other than $2$. now,if m is even,then $LHS$ of the equation is divisible by $4$.And as we said $\phi(n)=p_1^{q_1-1}\ldots{p_k^{q_k-1}}(p_1-1)(p_2-1)\ldots{(p_k-1)}$ Here $p_1^{q_1-1}$ is divisible by $2$.and one of $(p_2-1),\ldots,{(p_k-1)}$ is divisible by at least $2$,because all of $p_2,p_3,.....,p_k$ are odd.There is at least one such expression,beacuse n has another prime divisor that$2$..But $402$ is not divisible by $4$.Contradiction.

As with any problem, its usually easier to work with a smaller case before the general case. In this problem. Lets first assume that $n$ is a semiprime. Let $n=pq$ For primes $p,q$. Then $\phi(n)=\phi(pq)=(p-1)(q-1)=pq-(p+q)+1$. $n=\phi(n)+402$ $pq=pq-(p+q)+1+402$ $p+q=403$ The only solution for $(p,q)$ is: (401,2), so $n=802$ Just writing this off the cuff. Maybe this will help?? There's a nice little theorem in Number Theory by George E. Andrews. It says that: $\displaystyle\frac{\pi(x)}{x}\leq\displaystyle\frac{\phi(k)}{k}+\displaystyle\frac{2k}{x}$ Rearrange the terms: $\displaystyle\frac{\phi(k)}{k}\geq\displaystyle\frac{\pi(x)}{x}-\displaystyle\frac{2k}{x}$ But since $\phi(k)=k-402$, $\displaystyle\frac{k-402}{k}\geq\displaystyle\frac{\pi(x)}{x}-\displaystyle\frac{2k}{x}$ $1-\displaystyle\frac{402}{k}\geq\displaystyle\frac{\pi(x)}{x}-\displaystyle\frac{2k}{x}$ $\displaystyle\frac{402}{k}\leq1-\displaystyle\frac{\pi(x)}{x}+\displaystyle\frac{2k}{x}$ $402x\leq k(x+2-\pi(x))$ Plugging in the formula given (but setting $x=k$), we get... $402x\leq k(x-\phi(x))$ Apparently it doesn't help. Oh well.

can anyone tell me what is $\{u_i\}_{i=1}^{r}=\{p_i|\alpha_i=1\}$ and $\{v_i\}_{i=1}^{s}=\{p_i|\alpha_i=2\}.$ and theorem of George E.Andrews?

because $\varphi(n) \leq n - \sqrt(n)$ we find that $n\leq 20$ now one can actually do stuff by hand tghrough elimination that inequality was taken from here http://en.wikipedia.org/wiki/Euler's_phi_function this is for n composite as in the link above is mentioned. for n prime we have $n=n-1+402$ wich is very unlikly for any n.

spx2 wrote: because $\varphi(n) \leq n - \sqrt(n)$ we find that $n\leq 20$ . You are wrong here .From $\varphi(n) \leq n - \sqrt{n}$ we take that $n\leq 1604$ which means nothing .

1).$\varphi(n) \leq n- \sqrt{n}$ 2).$\varphi(n)=n-402$ 1,2 => $n-402\leq n- \sqrt{n}$ <=> $\sqrt{n}\leq 402$ so $n \leq 402^2$ so $n\leq 161604$. yes i am wrong

i thought again about the problem,hopefully this time i'm right. $n-\varphi(n)=402$ $\prod p_i ^{\alpha_i-1} (\prod p_i - \prod (p_i -1) ) = 402$ now 402=2*3*67 now one can easily take combinations of these as beeing the numbers from $\prod p_i ^{\alpha_i-1}$ is this right ?

this isn't good because there may exist any prime at power 1 in n wich will not appear in that product altough it appears in the paranthesis

One more answer $n=802$ Davron

$n=\sum_{d|n} \varphi(d)$ so if $n=\prod_{i=1}^{k} p_i^{\alpha_i}$ * $n-\varphi(n)=\sum_{i=1}^{k} \sum_{d|\frac{n}{p_i}}\varphi(d)$ but $\sum_{d|\frac{n}{p_i}}\varphi(d) = \frac{n}{p_i}$ so $n-\varphi(n)=\sum_{i=1}^{k} \frac{n}{p_i}$ but if we consider n in the form * we have $\sum_{i=1}^{k} \frac{n}{p_i}=\prod_{i=1}^{k} p_i^{\alpha_i -1} (\sum_{i=1}^{k} p_i )$ is it simpler now ? davron are you sure what you wrote is a solution because $802=2 \cdot 401$ both $2,401$ are prime both appear at power 1 in 802. this means that $\prod_{i=1}^{k} p_i^{\alpha_i -1} (\sum_{i=1}^{k} p_i )=403$ wich is a little weird ... could someone please help ?

please anyone does this help in any way? how can we solve this problem ?

spx2, please stop posting wrong solutions in every topic! Post only full and complete solutions. It's

Substitute $ n$ by $ P_{1}^{\alpha_{1}} \cdot P_{2}^{\alpha_{2}} \cdots P_{x}^{\alpha_{x}}$. As we know, $ \varphi(n) = P_{1}^{\alpha_{1} - 1}\cdot P_{2}^{\alpha_{2} - 1}\cdots P_{x}^{\alpha_{x} - 1}$. So the givven equation rewrites as the following: ${ P_{1}^{\alpha_{1} - 1}\cdot P_{2}^{\alpha_{2} - 1}\cdots P_{x}^{\alpha_{x} - 1}(P_{1}P_{2}\cdots P_{x} - (P_{1} - 1)(P_{2} - 1)\cdots(P_{x} - 1}) = 402$. $ (1)$. If none of the numbers $ P_{1},P_{2},...,P_{x}$ is $ 2$, than in $ (1)$ equality $ LHS$ is odd, while $ 402$ is even-contradiction. So, wlog $ P_{1} = 2$. If $ \alpha_{1} > 1$, than in $ (1)$ equality $ LHS$ is divisible by $ 4$, while $ 402$ isn't divisible by $ 4$. So, $ \alpha_{1} = 1$. Assume there exists the number $ \alpha_{i}$ such that $ \alpha_{i} > 1$. As $ P_{1}^{\alpha_{1} - 1}\cdot P_{2}^{\alpha_{2} - 1}\cdots P_{x}^{\alpha_{x} - 1}|402 = 2\cdot 3\cdot 67$, $ P_{i}$ is either $ P_{i} = 3$ or $ P_{i} = 67$. $ n$ is even. So, $ \varphi(n) < = \frac {n}{2}$, giving $ 402 < = n < = 804$. If wlog $ P_{2} = 67$, than the last inequality gives: $ 3 < = P_{3}\cdots P_{x} < = 6$ which follows $ P_{3 } = P_{x} = 5$. So,$ n = P_{1}P_{2}P_{3} = 2\cdot 67\cdot 5 = 670$. $ \varphi(n) = 132$, but $ 670$ isn't equal to $ 132 + 402$-contradiction. If $ P_{2} = 3$,than the same argument leads us to that: $ 67 < = P_{3} \cdot P_{x} < = 134$. By checking all possible numbers instead of $ P_{3},P_{4},...,P_{x}$, using the fact that if $ i$ doesn't equal to $ j$,where $ 2 < = i,j < = x$, than $ P_{i}$ doesn't equal to $ P_{j}$, we make sure there aren't the solutions to the given equation. Now it remains to take a look to the case $ \alpha_{1} = \alpha_{2} = ... = \alpha{x} = 1$. Our equation rewrites so: $ 2P_{2}P_{3}\cdots P_{x} = (P - {1} - 1)(P_{2} - 1)\cdots(P_{x} - 1) + 402$. $ (2)$. Now we see the two possible cases: $ (a)$ $ x$ is odd; $ (b)$ $ x$ is even; $ (a)$ $ x = 2m + 1$. ($ m$ is positive integer, $ m > = 2$(If $ m = 1$,we have no solutions. If $ m = 0$, we have no solutions). Wlog assume $ P_{1} < P_{2} < ... < P_{x}$. If $ P_{m + 1} > = 19$, than $ 804 > = n > = 2P_{m + 1}P_{m + 2} > = 2\cdot 19\cdot 23 > 804$-contradiction. So, $ P_{m + 1} < = 17$. If $ P_{m + 1} = 17$, than $ 804 > = n > = 2\cdot 3 \cdot 17 \cdot 19 > 804$-contradiction. If $ P_{m + 1} = 13$, than $ 804 > = 2 \cdot 13 \cdot 17 > 804$-contradiction. If $ P_{m + 1} = 11$, than $ 804 > = n > = 2 \cdot 3 \cdot 11 \cdot 13 > 804$-contradiction. If $ P_{m + 1} = 7$, $ 804 > = n > = P_{m - 1}P_{m}P_{m + 1}P_{2m + 1} > = 2 \cdot 3 \cdot 7 \cdot 23 > 804$-contradiction, if $ P_{2m + 1} > = 23$. If not, checking all the cases we get the solution $ n = 546$. If $ p_{m + 1} = 5$, than $ P_{m} = 3$ and $ P_{m - 1} = 2 = P_{1}$.So, $ m = 2$. $ 804 > = P_{1}P_{2}P_{3}P_{4}P_{5} > = 2 \cdot 3 \cdot 5 \cdot7 \cdot 11 > 804$-contradiction. If $ P_{m + 1} = 3$, $ P_{m} = P_{1}$ giving $ m = 1$, which we already checked. (b) $ x = 2m$. If $ m = 1$, $ n = 802$ is the solution. Assume $ m > = 2$. By the same argument as in case $ (a)$ we get there is no more solution. Finally, we have two possible solutions:$ 802$ and $ 546$.

Ditdo wrote: You can see my solution by one click!

$ \phi(2m)=\phi(m)$ only for odd values of m, otherwise it doesn't hold (since function multiplicity doesn't apply)

Obviosly $ n=2m$ and m is odd. Therefore $ 2m-\phi (m)=402$. It give $ 201<m<402$. Obviosly $ m=rad(m)$ or $ m=3rad (m)$ (because $ 402=2*3*67$ and $ 67^2>402$). 1. If $ 3\not |m$, then $ m\not =p_1p_2p_3$, because else $ 3\not p_i-1$ and $ 5*11*17>402$. If $ m=p_1p_2$, then $ 2m-\phi(m)+1=(p_1+1)(p_2+1)=404=4*101$ give contradition. It prove, that $ m=3k$ and $ k$ is not prime. If $ k=3l$ we get $ 3l-\phi(l)=67, 23\le l\le 41$ - not solution. Therefore $ m=3p_1p_2,3<p_1<p_2$. It give $ 2p_1p_2+p_1+p_2=202$ and $ 67<p_1p_2<134$. Or $ (2p_1+1)(2p_2+1)=405=3^4*5=15*27$, or $ p_1=7,p_2=13$. Only solution $ n=2*3*7*13$.