4
$\begingroup$

The Question:


Evaluate $3^{123}\mod 100$


My Attempt


So initially I attempted to list the powers of 3 and find a pattern of the last two digits - which, despite much painful inspection did not yield an obvious useful pattern.

So I then attempted to simplify this and use Euler's Generalisation of Fermat's Theorem to solve this:

The theorem states: $a^{\phi(n)} \equiv 1 \pmod{n}$

So:

$3^{123}\mod 100$

= $3^{41^3}\mod 100$

= $(3^{40} \times 3^1)^3\mod 100$

I think I'm ok up to that point. Now, $\phi(100) = 40$

So am I right in the following?

$(3^{40} \times 3^1)^3\mod 100$ $\cong$ $(1 \times 3^1)^3\mod 100$

= $3^3\mod 100$

= 27.

Am I correct?


Thanks!


$\endgroup$
5
  • $\begingroup$ Does this answer your question? How do I compute $a^b\,\bmod c$ by hand? $\endgroup$ Aug 23, 2020 at 4:44
  • $\begingroup$ No, I am looking how at whether my application of Euler's generalisation of Fermat's Theorem is correct. Checking my solution is the objective of the question, not computing $a^b \mod c$ by hand @JyrkiLahtonen $\endgroup$
    – global05
    Aug 23, 2020 at 4:50
  • 1
    $\begingroup$ That thread has dozens if not hundreds of threads with titles like what are the two last digits of this huge power linked to it. When no new content is produced to the site, I vote to close as a duplicate. $\endgroup$ Aug 23, 2020 at 4:54
  • $\begingroup$ You gave up on looking for patterns, but that can be done. Are you interested in the details? $\endgroup$ Aug 24, 2020 at 14:36
  • $\begingroup$ Why not @CopyPasteIt? $\endgroup$
    – global05
    Aug 24, 2020 at 22:35

4 Answers 4

2
$\begingroup$

You are indeed correct. There is, however, one minor improvement. Using the Carmichael function, you can argue that a smaller power of $3$, namely $3^{\lambda(100)}=3^{20}\equiv 1\bmod 100$. The Carmichael function of divides half the Euler totient function when the argument is even and the Euler totient is a multiple of $4$, which is true for $\lambda(100)$; thus $3^{20}$ can replace $3^{40}$ in the argument.

At a more elementary level, you can render $3^4=80+1$ and raise both sides to the fifth power, thus $3^{20}\equiv1\bmod 100$ as the Binomial Theorem for $(80+1)^5$ gives multiples of $100$ plus $1$.

$\endgroup$
1
$\begingroup$

Correct, an alternative solution:

$$ \begin{align} 3^{123}&=\left(3^{2}\right)^{61}\cdot 3\\ &=\left(10-1\right)^{61}\cdot 3\\ &\equiv\left(\binom{61}{1}10^{1}\left(-1\right)^{60}-1\right)\cdot 3 &\mod{100}\\ &\equiv 27 &\mod100 \end{align} $$

$\endgroup$
1
$\begingroup$

The OP began by looking for a pattern but stated that

...despite much painful inspection did not yield an obvious useful pattern.

You can use some light theory to actually predict the form and structure of the pattern.

Observe that if $a \in \{0,2,4,6,8\}$ and $b \in \{1,3,7,9\}$ and

$\quad 3 \times (10 a + b) \equiv 10 \,a' + b' \pmod{100} \text{ with } a',b' \in \{0,1,2,3,4,5,6,7,8,9\}$

then in fact $a' \in \{0,2,4,6,8\}$ and $b' \in \{1,3,7,9\}$.

This is our main (theoretical) pattern and

$\quad 3^1 \equiv 03 \pmod{100}$
$\quad 3^2 \equiv 09 \pmod{100}$
$\quad 3^3 \equiv 27 \pmod{100}$
$\quad 3^4 \equiv 81 \pmod{100}$
$\quad\text{-------------------------}$
$\quad 3^5 \equiv 43 \pmod{100}$

It easy to verify that the units digit will move

$\quad 3 \mapsto 9 \mapsto 7 \mapsto 1$

inside each of these four cycles.

Considering that $3$ is a unit, we can argue that one of these $4$-cycles will end on

$$\quad 01 \quad \text{the multiplicative identify}$$

and that no repetition is possible until the identify is reached.

Since the tens digit can only cycle over the set $\{0,2,4,6,8\}$, there are at most five of these $4$-cycles that have to be calculated.

Calculating the $2^{nd}$ $4$-cycle:

$\quad 3^5 \equiv 43 \pmod{100}$
$\quad 3^6 \equiv 29 \pmod{100}$
$\quad 3^7 \equiv 87 \pmod{100}$
$\quad 3^8 \equiv 61 \pmod{100}$
$\quad\text{-------------------------}$

Calculating the $3^{rd}$ $4$-cycle:

$\quad 3^9 \equiv 83 \pmod{100}$
$\quad 3^{10} \equiv 49 \pmod{100}$
$\quad 3^{11} \equiv 47 \pmod{100}$
$\quad 3^{12} \equiv 41 \pmod{100}$
$\quad\text{-------------------------}$

Calculating the $4^{th}$ $4$-cycle:

$\quad 3^{13} \equiv 23 \pmod{100}$
$\quad 3^{14} \equiv 69 \pmod{100}$
$\quad 3^{15} \equiv 07 \pmod{100}$
$\quad 3^{16} \equiv 21 \pmod{100}$
$\quad\text{-------------------------}$

At this point we really don't have to calculate the $5^{th}$ $4$-cycle since we know it has to be the last one.

We can now use the fact that

$\tag 1 3^{20} \equiv 1 \pmod{100}$

and work out the remaining details for the OP's question.

$\endgroup$
0
$\begingroup$

Correct! I believe your logic does hold correctly. As far as I can see this is a correct application of Euler's generalisation of Fermat's Theorem. $\phi(100) = 40$ and thus $3^{40} \cong 1 \mod 100$

If you need further convincing, simply input $3^{123}$ into https://www.calculatorsoup.com/calculators/algebra/large-exponent-calculator.php.

Again, not really needed, but if you needed concrete proof, there it is.

$\endgroup$

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.