Why $4^{44387934 } \mod 10$ is congruent to $6 \mod 10$? 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?
 A: 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$.
A: Hint: $\bmod 10\!:$ scaling an $\rm\color{#0a0}{even}$ integer by $\,\color{#c00}4\,$ is the same as $\rm\color{#c00}{negating}$ it, i.e.
$\quad\ \underbrace{\bmod 10\!:\ \color{#c00}4(\color{#0a0}2n) \,\equiv\, (\color{#c00}{-1})(\color{#0a0}2n)}_{\textstyle\ \ \ \ \ \ \ \ \ \ \color{#0a0}2n \times  
  \{\color{#c00}4\equiv \color{#c00}{-1}\pmod{\!10/\color{#0a0}2}\}\!\!} \!\!\Rightarrow\ \ \bbox[6px,border:1px solid #c00]{\color{#c00}4^{\large\color{#c00} k}\cdot \color{#0a0}4 \equiv \color{#c00}{(-1)}^{\large \color{#c00}k}\color{#0a0} 4}\ \,$ cf. mod Distributive Law
A: You are correct that Euler's theorem does not apply because $\gcd(4,10)≠1$,
but $4^0≡1$, and you could prove by induction that $4^{2n−1}≡4$ and $4^{2n}≡6\bmod10$ for $n>0$.
