Loading
Russian
Polish
Mikołaj Hajduk's Homepage

Exemplary application of the Euler's theorem

A
ssume that someone asks us to calculate \[3^{3333333} \mod 100\] i.e. we have to find the remainder from division $3^{3333333}$ by $100$. In other words, we are expected to find the two last digits of the decimal representation of the number $3^{3333333}$. At first sight, the problem doesn't seem easy to solve as one may expect a lot of troublesome and not especially enlightening arithmetic calculations. However, as it will be presented in the following parts of this article, mathematical problems of that sort may be solved with use of some useful "shortcuts" that quickly lead us to the desired result.

If the base $a$ of the power, in our case $a = 3$, is coprime to the modulus $m$ (here $m = 100$), then there exists a natural number $k > 0$ that satisfies the following congruence: \[a^{k} \equiv 1 \; (\mkern-18mu \mod m) \; \; (*)\] Indeed, the Euler's theorem states that the aforementioned congruence will be satisfied for $k = \phi(m)$ where $\phi(n)$ is the Euler's totient function and its value is defined for any natural $n$ as a number of positive integers less than or equal to $n$ that are relatively prime to $n$. Interestingly, $\phi(m)$ is not necessarily the smallest natural number that satisfies the congruence (*). Indeed, the problem considered in this article is an example of such case where the congruence (*) is satisfied also for the exponent much smaller than $\phi(m)$.

Why the existence of such a natural number $k > 0$ that for coprime $a$ and $m$ we get \[a^{k} \equiv 1 \; (\mkern-18mu \mod m)\] is so important? Because in that case for calculation \[a^{n} \mkern-18mu \mod m\] it's enough to consider \[a^{n \mkern-8mu \mod k} \mkern-18mu \mod m\] because if $n = sk + r$ for natural $s > 0$ and $0 \leq r < k$ we have \[(a^{k})^{s} \equiv 1 \; (\mkern-18mu \mod m)\] i.e. \[a^{sk} \equiv 1 \; (\mkern-18mu \mod m)\] Let's multiply both sides of the congruence by $a^{r}$ to obtain \[a^{sk}*a^{r} \equiv a^{r} \; (\mkern-18mu \mod m)\] that is \[a^{sk+r} \equiv a^{r} \; (\mkern-18mu \mod m)\] Taking into account the fact that $n = sk + r$ we can transform the formula this way \[a^{n} \equiv a^{n \mkern-8mu \mod k} \; (\mkern-18mu \mod m)\] The relation presented above shows us how to reduce exponents to values that allow to perform exponentiation even on a mere pocket calculator.

Relying on the definition of the Euler's totient function we can determine value of $\phi(100)$: \[\phi(100) = 100\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 100\frac{1}{2}\frac{4}{5} = 40\] Hence \[3^{3333333} \equiv 3^{3333333 \mod 40}\; (\mkern-18mu \mod 100)\] that is \[3^{3333333} \equiv 3^{13} = 1594323 \; (\mkern-18mu \mod 100)\] and finally \[3^{3333333} \equiv 23 \; (\mkern-18mu \mod 100)\]

Take notice that if we wanted to find empirically the smallest exponent $k > 0$ for which \[3^{k} \equiv 1 \; (\mkern-18mu \mod 100) \; \; (**)\] then it would be enough to consider only the first $20$ powers of the number $3$. Indeed \[3^{20} = 3486784401 \equiv 1 \; (\mkern-18mu \mod 100)\] This is exactly an example of the situation when the Euler's totient function doesn't provide the smallest natural number satisfying the equation (**).

With use of the table presented below, containing all the first $20$ powers of $3$ along with corresponding remainders on division by $100$, a curious reader can confirm that the aforementioned statement is true:

$k$$3^{k}$$3^{k} \mod 100$
$1$$3$$3$
$2$$9$$9$
$3$$27$$27$
$4$$81$$81$
$5$$243$$43$
$6$$729$$29$
$7$$2187$$87$
$8$$6561$$61$
$9$$19683$$83$
$10$$59049$$49$
$11$$177147$$47$
$12$$531441$$41$
$13$$1594323$$23$
$14$$4782969$$69$
$15$$14348907$$7$
$16$$43046721$$21$
$17$$129140163$$63$
$18$$387420489$$89$
$19$$1162261467$$67$
$20$$3486784401$$1$
© 2007-2014, Mikołaj Hajduk