When I was solving Project Euler’s problem 26, I had to find a way to obtain the period of the the decimal expansion of for various integer values of . I first thought of comparing strings of digits along the decimal expansion to see if they repeated; however, this solution was neither clever nor efficient. With this in mind, I set out to find a better method for this problem.
After some research, I came across something I had never heard about in my high school math classes. The smallest integer exponent such that is called the multiplicative order of .
This value has an interesting property. The multiplicative order of is equal to the period of the decimal expansion of . Note that this only works when is relatively prime to 10, i.e. when is not divisible by 2 or 5.
Consider a few examples:
Multiplicative Order of 10 (mod n)
Honestly, I don’t know why this property works, but it allowed me to solve the problem using an algorithm that was much faster (and clever) than my previous. If you want to look deeper into it, check the links below.