Loading

A

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