$\phi$ nd the Remainder

Relevant wiki: Order of an Element

We tackle the generalization first. So we will prove that, for all positive integers $n,$ we must have $2n|\phi(2^n + 1).$

Let $d = \text{ord}_{2^n + 1}(2).$ By Euler's Theorem, $2^{\phi(2^n + 1)} \equiv 1 \! \pmod{2^n + 1},$ so $d|\phi(2^n + 1).$ We also have $2^n \equiv -1 \! \pmod{2^n + 1},$ and squaring both sides gives $2^{2n} \equiv 1 \! \pmod{2^n + 1}.$ Thus, $d|2n.$

Now, we will show that $d = 2n$ by showing that the other possible values for $d$ do not work. Suppose that $d \neq 2n$ i.e. $d$ is a proper divisor of $2n.$ Then, $1 \leq d \leq n,$ so $1 < 2^d \leq 2^n < 2^n + 1.$ However, this means that $2^d \not \equiv 1 \! \pmod{2^n + 1}$ ; if it were, then $2^d = 1,$ which is impossible.

Therefore, we must have $d = 2n,$ so $2n|\phi(2^n + 1),$ and the claim is proven. $\blacksquare$

The problem is a direct application of this statement. If we let $n = 2018,$ we get $4036|\phi(2^{2018} + 1),$ so the remainder is simply $\boxed{0}.$

Note: There is nothing special about powers of 2; in fact, for any positive integer $a \geq 2,$ we must have $2n|\phi(a^n + 1),$ which can be proven in the same way as we did above.

Please my friends help me to check my solution, is my solution correct?

First, factorize the number $2^{2018}+1=4^{1009}+1=5(4^{1008}-4^{1007}+4^{1006}-...-4+1)$

I consider the number $4^{1008}-4^{1007}+4^{1006}-...-4+1$ as a prime, but I don't know how to prove it.

so $\phi (2^{2018} + 1)=(2^{2018} + 1)(\frac{4}{5})(\frac{4^{1008}-4^{1007}+4^{1006}-...-4}{4^{1008}-4^{1007}+4^{1006}-...-4+1})=16(4^{1007}-4^{1006}+...-1)$

On division by $4036$ , in fact it can be factorize as $2^2 \times 1009$ which $1009$ is a prime, we can do $\phi (2^{2018} + 1)(mod 4036)$ by using Chinese Remainder Theorem. It is easy to show that $\phi (2^{2018} + 1) \equiv 0 (mod 4)$ , then let

$\phi (2^{2018} + 1) \equiv \frac{16}{5}(4^{1008} - 1) \equiv x (mod 1009)$

$5x \equiv 16(4^{1008}-1) \equiv 16(1-1) \equiv 0 (mod 1009)$

$x \equiv 0 (mod 1009)$

this implies that $\phi (2^{2018} + 1) \equiv \boxed 0 (mod 4036)$ , completes the proof

I am trying to come up with a solution that uses elementary box principles because I don't feel the problem needs a number theoretic Perspective; I will edit this as soon as I reach the solution... .

Note that,

2^{n}+1 | 2^{\phi(2^n+1)}-1

But since, ord_{2^n}2=2n.

We have, 2n | \phi(2^n+1).

Relevant wiki's : Order of an Element and Euler's totient function

Using the property that $n | \phi (a^n -1)$ for all positive integers a and n, and noting that :

$\phi(2^{2n} - 1) = \phi(2^n - 1) . \phi(2^n + 1)$ (gcd of both arguments of the totient function in the RH side is clearly 1) we get that

(1) $\phi(2^n - 1)$ is divisible by n (using the mentioned property)

(2) $\phi(2^n + 1)$ is divisible by 2 (an established result if n > 2, which you can very easily verify by looking into the formula for computing $\phi(n)$ ).

This means that $2n | \phi(2^{2n} - 1)$ . The specific case follows easily by setting n = 2018.

I assumed it to be a Mersenne prime and then 2^ 2018 is Φ(2^2018 + 1). Then 2^2018 is definitely divisible by 4036. I'm not sure tho.