7
$\begingroup$

Number Theory :

Prove for all $m \in \mathbb{N}$ exists $n \in \mathbb{N}$ such that :

$\varphi(n)-\varphi(n+1)>m$ and $\varphi(n)-\varphi(n-1)>m$

Attempt:

For $m\in \mathbb{N}$ let $q_m$ be prime number form of $4k+3$ for some $k\in \mathbb{N}$ such that $2m+3<q_m$

$\endgroup$
2
  • $\begingroup$ Get some ideas from WA. $\endgroup$
    – Neat Math
    Dec 17, 2020 at 22:40
  • $\begingroup$ @NeatMath Thanks , I will check it out . maybe it will give me a ways to solve $\endgroup$
    – ATB
    Dec 17, 2020 at 22:43

1 Answer 1

Reset to default
2
$\begingroup$

Hint: Suppose $n$ is an odd prime. Then $\varphi(n) = n-1$. Also, $n-1$ and $n+1$ are both even, and thus, $\varphi(n-1) \le \dfrac{n-1}{2}$ and $\varphi(n+1) \le \dfrac{n+1}{2}$. Do you see why this is true?

Using these results, how large does $n$ need to be to guarantee that $\varphi(n)-\varphi(n-1) > m$ and $\varphi(n)-\varphi(n+1) > m$?

$\endgroup$
4
  • $\begingroup$ First of all Thanks you for that Hint, I am understand the hint and I can see that always true because every even number in $\varphi$ great or equal then even number divide by two. For the second line I think that n need to be large as more then m divide by two. I don't sure about that . $\endgroup$
    – ATB
    Dec 20, 2020 at 22:10
  • $\begingroup$ Using $\varphi(n) = n-1$ and $\varphi(n+1) \le \tfrac{n+1}{2}$, can you find a lower bound for $\varphi(n)-\varphi(n+1)$? Then, set that lower bound $> m$ and solve for $n$. $\endgroup$
    – JimmyK4542
    Dec 20, 2020 at 22:13
  • $\begingroup$ Hey, I've been stuck for a long time with this proof. Can I have your help please ? $\endgroup$
    – ATB
    Dec 30, 2020 at 20:36
  • $\begingroup$ We want to pick an odd prime $n$ such that both $\varphi(n)-\varphi(n+1) \ge (n-1)-\tfrac{n+1}{2} = \tfrac{n-3}{2} > m$ and $\varphi(n)-\varphi(n-1) \ge (n-1)-\tfrac{n-1}{2} = \tfrac{n-1}{2} > m$ hold. Can you use these inequalities to figure out how big $n$ needs to be? Then the proof goes something like "For any $m \in \mathbb{N}$, pick an odd prime $n > ?$. Then $\varphi(n)-\varphi(n+1) \ge \ldots > m$ and $\varphi(n)-\varphi(n-1) \ge \ldots > m$." $\endgroup$
    – JimmyK4542
    Dec 30, 2020 at 21:31

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.