CCRT = Constant case CRT: $ $ if $\,p,q\,$ are coprime then$\,x\equiv a\pmod{\! p},\ x\equiv a\pmod{\! q}\iff x\equiv a\pmod{\!pq}$

Question

Problem: Find the units digit of $3^{100}$ using Fermat's Little Theorem (FLT).

My Attempt: By FLT we have $$3^1\equiv 1\pmod2\Rightarrow 3^4\equiv1\pmod 2$$ and $$3^4\equiv 1\pmod 5.$$ Since $\gcd(2,5)=1$ we can multiply the moduli and thus, $3^4\equiv 1\pmod {10}\Rightarrow3^{4*25}\equiv 1\pmod{10}.$ So the units digit is $1.$

Answer 1

Yours is a valid, clean argument. It is based on this:

If $m$ and $n$ divide $a$, then $\text{lcm}(m,n)$ divides $a$.

In your case, you have that $2$ and $5$ divide $3^4-1$, and so $10=\text{lcm}(2,5)$ divides $3^4-1$.

Answer 2

The phrase ‘Since gcd(2,5)=1 we can multiply the moduli’ is not clear at all. I would rather say something like ‘since $3^4\equiv 1\mod 2$ and $\bmod5$, we have $3^4\equiv 1\mod \operatorname{lcm}(2,5)=10$’ by the Chinese remainder theorem.

That said, why make things more complicated than they are?

$3^2\equiv -1\mod 10$, hence $3^4\equiv (-1)^2=1\mod 10$, and finally $3^{10}=(3^4)^{25}\equiv 1\mod10$.

Answer 3

Your proof is correct. It invokes a simple special case of CRT = Chinese Remainder Theorem when the values $\,a_1 = a_2\,$ are constant, say $\,a,\,$ which is equivalent to the following basic result

UL = Universal property of LCM: $\ \rm \,\ j,k\mid n\!\!\color{#0a0}{\overset{\rm UL\!\!}\iff} {\rm lcm}(j,k)\mid n$

CCRT = Constant case CRT $\ $ If $\rm \,a,p,q\,$ are integers and $\rm \,\gcd(p,q) = 1\,$ then

$$\begin{align}\rm x\equiv a\!\!\pmod{p}\\ \rm x\equiv a\!\!\pmod{q}\end{align}\iff\,\rm x\equiv a\!\!\pmod{pq}\qquad$$

Proof $\ $ Below I sketch the key ideas in four proofs.

$\rm(1)\ \ \ x \equiv a\pmod {pq}\:$ is clearly a solution, and the solution is $\color{#C00}{\textit{unique}}$ $\!\!\pmod{\rm\!pq}\,$ by CRT.

$\rm(2)\ \ \ p,q\:|\:x\!-\!a\!\!\color{#0a0}{\overset{\rm UL\!\!}\iff} lcm(p,q)\:|\:x\!-\!a.\:$ Further $\rm\:\gcd(p,q)=1\!\iff\!lcm(p,q) = pq.$

$(3)\ \, $ By Euclid's Lemma: $\rm\:(p,q)=1,\,\ p\mid nq\! =\!x\!-\!a\:\Rightarrow\:p\:|\:n\:\Rightarrow\:pq\:|\:nq = x\!-\!a.$

See here for more proofs, elaboration, and generalizations.

Remark $\ $ This constant-case optimization of CRT arises frequently in practice so is well-worth memorizing, e.g. see some prior posts for many examples.

Quite frequently, $\color{#C00}{\textit{uniqueness}}\ \textit{theorems}\,$ provide powerful tools for proving equalities.