Evaluate the least significant decimal digit $ 109873^{7951}$ I am trying to understand the below, I can t seem to see or understand, how and why and where the answers where arrived at.
Evaluate the least significant decimal digit of $ 109873^{7951}$
Solution:
We need to calculate $ 109873^{7951}$ (mod 10)
φ(10) = 4  // Firstly how is 4 the answer

$ 109873^{7951}(\mod 10) = 3^{(7951 \mod φ(10))} (\mod 10) = 3^{(7951 \mod 4)} (\mod 10) = 3^3
(\mod 10) = 7$
I am wondering if someone could explain to me also how the other answer is 7..? I would grateful if someone could step me though this.
 A: $\varphi(10)$ is $4$ because $4$ of the numbers between 0 and 10 are coprime to 10, namely $\{1,3,7,9\}$.
We can also compute this by the rules that $\varphi(ab)=\varphi(a)\varphi(b)$ when $a$ and $b$ are coprime, and $\varphi(p)=p-1$ when $p$ is prime, so
$$ \varphi(10)=\varphi(2)\varphi(5)=(2-1)(5-1)=1\cdot 4 = 4$$
Since $10$ is square-free, a generalization of Euler's theorem states that $a^k\equiv a^m\pmod{10}$ when $k\equiv m\pmod{\varphi(10)}$.
So since $7951\equiv 3\pmod 4$ we have
$$ 109873^{7951} \equiv 109873^3 \pmod{10} $$
And it is easy to compute the last digit of this: just ignore everything to the left of the ones column when multiplying, so the last digit of $109873^3$ is the same as the last digit of $3^3$.
A: To me, it is $7$.
See:
$$109873^{7951} \equiv {(10987 \cdot 10 + 3)}^{7951} \equiv 3^{7951} \pmod{10}$$
Now we use modular exponentiation.
First of all, we express the exponent in binary: $$7951_{10)} = 1111100001111_{2)}$$
So $3^{7951}$ is congruent to $\prod_{i \in A} b_i$, where $A = \{0, 1, 2, 3, 8, 9, 10, 11, 12\}$.
That is, $3^{7951}$ is congruent to the product of all terms $b_j$ where $j$ are all the positions of the vector $1111100001111$ which are $1$.
So: $$b_0 = 3$$
$$b_1 = b_0^2 \equiv 9$$
$$b_2 = b_1^2 \equiv 1$$
Now we stop, because we notice that $\forall (j \geq 2)\; b_j \equiv 1$, so:
$$109873^{7951} \equiv 3^{7951} \equiv b_0 \cdot b_1 \equiv 3 \cdot 9 \equiv 27 \equiv 7\pmod{10}$$
