0
$\begingroup$

The last digits of powers of a number repeats. For example the last digits of powers of 2 repeat in a cycle of 4, 8, 6, 2, 4, 8, 6, 2 and the last digits of powers of 9 repeat in a cycle of 1, 9, 1, 9. That is for 2, the repeat count is 4 and for 9 it is 2. In fact, the repeat count of all numbers ending with 2 is 4 and 9 is 2 which can be proved with binomial theorem. Hence the repeat count of any decimal number can be easily calculated from the repeat counts of first 9 numbers.

But I am looking for a solution to find repeat count of numbers with larger base/radix than decimal. Hence maintaining a complete lookup table is hard. Also is there a solution to find the repeat count if we consider n last digits instead of 1? In short, given a number, its base and howmany last digits, is it possible to find the repeat count?

So far I found Chinese Remainder Theorem and Euler’s Theorem to find last digits. But I couldn’t find a way through it to find the count. I have only basic knowledge in mathematics. I would be grateful for any help.

$\endgroup$
  • $\begingroup$ Do you already know that you can find the last $k$ digits of the powers of $p$ in the basis $b$ by $p^i\text{ mod } b^n$? $\endgroup$ – M. Winter Oct 17 '17 at 15:02
  • $\begingroup$ @M.Winter Yes. If I understood it correctly, any number mod $base^k$ is the definition of last k digits. But no idea how to find their repeat count. $\endgroup$ – Vadakkumpadath Oct 18 '17 at 7:07
0
$\begingroup$

Lets say you want to find the last $k$ digits of the powers of $p$ in base $b$. At first, define

$$B=\frac{b^n}{\gcd(b^n,p)}.$$

Now $B$ and $p$ are coprime and the "repeating count" of $p^i\pmod {b^n}$ is equal the one of $p^i\pmod{B}$. The term coprime is important here because now we can consider $p$ an element of the multiplicative unit group $\Bbb Z_B^\times$. The period you are looking for is called the order of $p$ in $\Bbb Z_B^\times$.

If I am not mistaken, then some cryptographic procedures are based on the fact that such an order is really hard to find. You might therefore be out of luck. Look for example on this page about Shore's factorization algorithms which works on quantum computers and reduces integer factorization to order-finding which seems to be unfeasible on regular computers.

However, if your modulus $B$ is not too large, you can brute-force your answer. It suffices to use only numbers $\le B^2$ (or even $\le B$) when applying modular exponentiation. For example, compute the order of $p=7$ in base $10$:

\begin{align} 7 &\equiv 7\pmod {10}\\ 7\cdot 7=49 &\equiv 9\pmod {10}\\ 7\cdot 9=63 &\equiv 3\pmod {10}\\ 7\cdot 3=21 &\equiv 1\pmod {10}\\ \end{align}

and then it repeats because we reached $1$ (and it will always reach $1$ because $B$ and $p$ are coprime, and this can be used for "efficient" brute-force strategies because you do not have to remember the other numbers). So the "repeating count" is $4$. In the worst case the period is $B$ and you will have to do all $B$ steps. Then $p$ is said to generate $\Bbb Z_B^\times$. There are some results on generators of such groups which might help you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.