Exemplary application of the Euler's theorem

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: