# $3^{123} mod 100$

Mathematics Asked by global05 on September 13, 2020

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)^3mod 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)^3mod 100$$ $$cong$$ $$(1 times 3^1)^3mod 100$$

= $$3^3mod 100$$

= 27.

Am I correct?

Thanks!

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.

Correct answer by global05 on September 13, 2020

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}$$
$$quadtext{-------------------------}$$
$$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}$$
$$quadtext{-------------------------}$$

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}$$
$$quadtext{-------------------------}$$

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}$$
$$quadtext{-------------------------}$$

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.

Answered by CopyPasteIt on September 13, 2020

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 1bmod 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}equiv1bmod 100$$ as the Binomial Theorem for $$(80+1)^5$$ gives multiples of $$100$$ plus $$1$$.

Answered by Oscar Lanzi on September 13, 2020

Correct, an alternative solution:

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

## Related Questions

### How to prove $Pleft(cup_{i=1}^{infty}A_iright)=1$ implies that $P({A_i i.o.})=1$

1  Asked on January 7, 2021 by xiangdong-meng

### Finding the order of a pole of a complex function

1  Asked on January 7, 2021 by prasiortle

### Can someone find a (two-sided) inverse function to the characteristic function χ? given…

2  Asked on January 7, 2021 by thecreator

### How To Prove This Is Continuous Or Discontinuous

1  Asked on January 7, 2021 by mat-rhine

### Given ?1 and ?2, how do you calculate ?3 and ?4 after shortening the line segment by equal distance on each point?

1  Asked on January 7, 2021 by jordan-farris

### Aprroximating the area of a surface of revolution using simpsons rule

1  Asked on January 7, 2021 by firefenix777

### The transportation problem with uncertain (and, in general, linearly interdependent) supply- and demand values

0  Asked on January 7, 2021 by rasus

### Finding maximum of this function in complex analysis

0  Asked on January 7, 2021 by avenger

### Is my solution to this first order ODE correct? (Integrating factor method)

1  Asked on January 7, 2021 by ryan-seah

### How to know convexity of the following equation/Problem?

1  Asked on January 7, 2021 by user814045

### Is it true that $prod_{i=1}^nleft(3 + frac{1}{3i}right) < left(3 + frac{1}{n}right)^n$?

2  Asked on January 7, 2021 by larry-freeman

### Quotient rule for limits of functions

1  Asked on January 6, 2021 by ashish

### Create Transfer Function with Known Input Delay and Specified Attributes

3  Asked on January 6, 2021 by lawliet

### How to verify this given homeomorphism in Munkres on stereographic projection

1  Asked on January 6, 2021 by bud-light-d-va

### Find the roots of all cubics $f(x)$ given $f(2)=1$ and all roots are integral

1  Asked on January 6, 2021 by jc5535

### A integral involving hyperbolic and trigonometric functions

1  Asked on January 6, 2021 by math-bob

### Are there any sets of axioms that have an efficient algorithm for all provable statements?

1  Asked on January 6, 2021 by phylliida

### Finding $int_S z,dS$ where $S=left{ big(x,y,zbig):x^2+y^2+z^2=a^2,zge 0, a>0right}$

2  Asked on January 6, 2021 by john-mars