My steps:
$$4^{44387934 } \mod 10 \\1) \ (4,10) \ne 1 \implies \text{I can't apply the Fermat-Euler theorem} \\ 2) \ \text{I calculate the first powers to see how they behave:} \\4^1\mod 10 \equiv4 \\ 4^2\mod 10 \equiv6 \\ 4^3\mod 10 \equiv4 \\ 4^4\mod 10 \equiv6 \\ … $$
Ok, now I know that the possible results can only be $4$ or $6$ and the loop(4,6) is of length 2, so I'm going to calculate $44387934 \mod 2$ that is $0$, so $4^0 \mod10 \equiv 1…$
The result should be $1$ but actually is 6, but why? I can't apply any theorem, right?
To understand why 6 came up as result, I tried to apply the Euler theorem:
$$\phi(10) = \phi(2)*\phi(5) = 1 \times 4 = 4 \\ 44387934 \mod 4 = \underbrace{44387924}_{ \ \equiv 0 \mod 10} \mod 4 \equiv 2 \\ \text{and } 4^2 \mod 10 \text{ is exactly 6}$$
The problem there is that actually I should not apply the Theorem, so why is 6?
Best Answer
Think about it. If the answer was $1\bmod 10$, that would mean that it is odd, which is clearly absurd. You are correct that the answer loops every $2$, however you don't use $1$ as the start of the loop. Like you said, the loop is $4, 6, 4, 6$, so you actually get $6$ when the exponent is $0\bmod 2$ and $4$ when the exponent is $1\bmod 2$.