4
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ 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}.$ $\endgroup$ – B. Goddard Nov 8 '16 at 19:12
  • $\begingroup$ @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. $\endgroup$ – DanielWainfleet Nov 9 '16 at 21:40
2
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ 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}$ $\endgroup$ – nls Nov 8 '16 at 20:19
  • $\begingroup$ @ShreyAryan, this follows from what I've written. Good job. $\endgroup$ – lhf Nov 8 '16 at 20:20
  • $\begingroup$ So I were to write this in an exam, then how should I go about it? $\endgroup$ – nls Nov 8 '16 at 20:24
  • $\begingroup$ @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. $\endgroup$ – Anurag A Nov 8 '16 at 20:42
  • $\begingroup$ @Shrey Yoru argument is indeed a special constant case of CRT - see my answer. $\endgroup$ – Gone Nov 9 '16 at 18:24
2
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks for your beautiful answer! $\endgroup$ – Postal Model Oct 19 '18 at 19:29
1
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – nls Nov 8 '16 at 20:02
  • $\begingroup$ @Shrey Aryan: your reasoning seems to be correct if I interpret your not very clear phrasing about $\gcd(2,5)$. $\endgroup$ – Bernard Nov 8 '16 at 20:14
  • $\begingroup$ 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. $\endgroup$ – nls Nov 8 '16 at 20:17
  • $\begingroup$ 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.’ $\endgroup$ – Bernard Nov 8 '16 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.