# CR-like-Theorem for powers of same prime

CRT asks the numbers in denominator to be coprime, is there are theorem/property when taking modulo by powers of a prime? It's easy if the power is small but it gets tougher as the number and/or powers grows.

Or is there a way to quickly find modulo , with the help of some related property? For example, $$675453 \equiv 3 \pmod 5$$ and $$675453 \equiv 3 \pmod {25}$$ but $$675453 \equiv 78 \pmod {125}$$

Is there some relationship between modulo of powers of prime?

• Do you have an example to clarify your question? Are you just asking for $$x \equiv a_i \pmod{p^i}$$ for some finite set of $i$? (i.e. different powers of a fixed prime) Jun 20 '20 at 23:16
• @Brian Moehring, yes. Jun 21 '20 at 0:18

The answer is no. An easy counterexample try to find some $$x$$ such that $$x \equiv 1 \mod 2$$ and $$x \equiv 2 \mod 4$$.

The deeper reason for this is that we may state the CRT as

Let $$q_1, ..., q_n$$ be coprime, then $$\begin{equation*} \mathbb{Z}/ \left(\prod_{i=1}^n q_i \right) \cong \prod_{i=1}^n\mathbb{Z}/(q_i) \end{equation*}$$

However the same is not true when the $$q_i$$ are not coprime since $$\mathbb{Z}/(p^n)$$ is cyclic while $$\prod_{i=1}^n\mathbb{Z}/(p)$$ is not.

Fortunately it is not difficult to find $$a \mod p^n$$.

• How to find it then? Jun 21 '20 at 0:48
• @AshWhole in the same way you would compute $a \mod n$ for any $n$ - by dividing and finding the remainder. One might use long division by hand. If you want to know how computers do it fast, see en.wikipedia.org/wiki/Division_algorithm. Jun 21 '20 at 1:14
• Okay.. I was hoping there maybe some shortcut Jun 21 '20 at 1:15