# Constant case CRT: $\,x\equiv a\pmod{\! 2},\ x\equiv a\pmod{\! 5}\iff x\equiv a\pmod{\!10}$

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.$

• I've never heard the phrase "since gcd =1 we can multiply the moduli." Rather, since $3^{100} \equiv 1 \pmod{2}$ and $3^{100} \equiv 1 \pmod{5}$, by CRT, $3^{100} \equiv 1 \pmod{10}.$ – B. Goddard Nov 8 '16 at 19:12
• @B.Goddard.It is valid that if $\gcd (x,y)=1$ with $xy\ne 0 ,$ and $a\equiv b \pmod x$ and $a\equiv b \pmod y,$ then $a\equiv b\pmod {xy}.$ Because if $x$ and $y$ both divide $a-b,$ with $\gcd (x,y)=1$, then $xy$ divides $a-b.$ But I've not seen it phrased that way either. – DanielWainfleet Nov 9 '16 at 21:40

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

If $m$ and $n$ divide $a$, then $lcm(m,n)$ divides $a$.

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

• My argument is based on the following fact: If $a\equiv b \pmod {n_1}$ and $a\equiv b \pmod {n_2}$ with $\gcd(n_1,n_2)=1$ then $a\equiv b \pmod {n_1n_2}$ – nls Nov 8 '16 at 20:19
• @ShreyAryan, this follows from what I've written. Good job. – lhf Nov 8 '16 at 20:20
• So I were to write this in an exam, then how should I go about it? – nls Nov 8 '16 at 20:24
• @ShreyAryan As what B. Goddard pointed out, your phrasing that $\gcd(a,b)=1$, hence I can multiply the congruences is odd (can be judged incorrect as well, even though the ultimate conclusion you are drawing is correct). You should go with what lhf has suggested. – Anurag A Nov 8 '16 at 20:42
• @Shrey Yoru argument is indeed a special constant case of CRT - see my answer. – Gone Nov 9 '16 at 18:24

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.$$

$$\rm(4)\ \,$$ The list of prime factors of $$\rm\,p\,$$ occurs in one factorization of $$\,\rm x-a\,$$, and the disjoint list of prime factors of $$\rm\,q\,$$ occurs in another. By $$\color{#C00}{uniqueness}$$, the prime factorizations are the same up to order, so the concatenation of these disjoint lists of primes occurs in $$\rm\,x-a,\,$$ hence $$\rm\,pq\mid x-a$$.

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.

• Thanks for your beautiful answer! – Postal Model Oct 19 '18 at 19:29

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$$.

• thank you for your answer. I knew this solution but wanted to know whether the reasoning of my argument is sound or not. If possible please, try to address that issue in your answer. – nls Nov 8 '16 at 20:02
• @Shrey Aryan: your reasoning seems to be correct if I interpret your not very clear phrasing about $\gcd(2,5)$. – Bernard Nov 8 '16 at 20:14
• Thank you for replying (again)! I read the following in David Burton, Chapter 4: If $a\equiv b \pmod {n_1}$ and $a\equiv b \pmod {n_2}$ with $\gcd(n_1,n_2)=1$ then $a\equiv b \pmod {n_1n_2}$, but was very unsure about whether I've been applying it correctly or not. – nls Nov 8 '16 at 20:17
• It's OK, only the phrasing is not clear. The abstract version is ‘ the canonical map $\mathbf Z/n_1n_2\mathbf Z\to\mathbf Z/n_1\mathbf Z\times\mathbf Z/n_2\mathbf Z$ is an isomorphism.’ – Bernard Nov 8 '16 at 20:22