Cfrgtkky

I know that the solution is with Euler function. I could not understand how to show this. thanks.

Hint: An equivalent problem is

Find the largest $N$ such that $varphi(N) le 4$.

Since $varphi(n) geq sqrt{n/2}$ for all $n$ (see here), we only have to consider $N le 32$.

No need to resort to complicated machinery, whatsoever.

Note that, $forall ninmathbb{Z}^+$, $(n-1,n)=(1,n)=1$. Take a prime $q$ such that, $frac{n}{2}<q<n$ (existence is justified through Bertrand's Postulate). Notice that, $(q,n)=1$ and $(n-q,n)=1$. Hence, we know that, for every $n$, $n-1,q,n-q,1$ are coprime to $n$.

Motivated by this, note that for $n$ sufficiently large (e.g., say $n>32$), look at the intervals, $I=(n/16,n/8),(n/8,n/4),(n/4,n/2),(n/2,n)$, take one prime each, add $1$, we get $phi(n)geq 5$, hence, $n<32$ (notice, this is a very naive bound). A few finite case work establishes $n=12$ is the largest such $n$.

The smallest $N$ where $phi(N) ge 5$ for every $n ge N$ would be $M + 1$ where $M$ is the largest $M$ where $phi(M) le 4$.

Now if $gcd(n,k) = 1$ then $phi(nk) = phi(n)phi(k)$ and for any $p^m$ for a prime $p$, then $phi (p^m) = (p-1)p^{m-1} ge p-1$. So if $phi(M) le 4$ then $p le 5$ so the only possible prime factors of $M$ are $2,3$ or $5$.

So $M = 2^a3^b5^c$ and $phi(M) = phi (2^a)phi(3^b)phi(5^c)$.

Case 1: Now if $c ge 1$ then $phi(5^c) = 4*5^{c-1}$ so $c=1$ and $phi(M) = 4$. And $phi(3^b) = phi(2^a) =1$.

If $bge 1$ then $phi(3^b) = (3-1)3^{b-1} = 2*3^{b-1}$ that's impossible so $b = 0$.

If $a ge 1$ then $phi(2^a) = (2-1)2^{a-1} = 2^{a-1}$. That is possible only if $a =1$ so if $M=10$, $phi(M) =4$ and that's the largest such number that is a multiple of $5$.

Case 2: $c=0$ and If $bge 1$: we can have $phi(3^b) = 2*3^{b-1}$. If this is to be less than or equal to $4$ we must have $b=1$ and $phi(3) = 2$ so $M= 2^a*3$ and $phi(M) = phi (2^a)phi 3 = 2phi(2^a)$.

SO $phi(2^a) le 2$ and as $phi(2^a)= 2^{a-1}$ we may have $a = 2$ and $M = 12$ and $phi(12) = 4$

And that's the largest such number that is a multiple of $3$.

Case 3: $c=0; b=0$ and $M = 2^k$ so $phi(M) = phi(2^{k})=2^{k-1}le 4$. This means $k le 3$ and $M le 8$. If $M = 8$ then $phi 8 = 4$.

And there we have it.

$M =12$ is the largest number so that $phi(M) le 4$ and $N = 13$ is the smallest number so that for all $nge N$, $phi(n) ge 5$.

=======

Worth noting the only time $phi(k)$ is odd is if $k=1,2$ so $phi(k) =5$ is impossible. (If $p$ is an odd factor of $k$ then $p-1|phi(k)$. If $k = 2^k$ then $phi(2^k) = 2^{k-1}$.)

$phi(k) ge 5; k le 12$ occur with $phi(7) = 6; phi(9)=6; phi(11)=10$

$phi(k) = 4$ occur with $phi(5)=phi(8)= phi(10)=phi(12)= 4$

And the rest $phi(3)=phi(4)=phi(6) = 2$.