0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$ Jun 20 '20 at 23:16
  • $\begingroup$ @Brian Moehring, yes. $\endgroup$
    – UmbQbify
    Jun 21 '20 at 0:18
3
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ How to find it then? $\endgroup$
    – UmbQbify
    Jun 21 '20 at 0:48
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 21 '20 at 1:14
  • $\begingroup$ Okay.. I was hoping there maybe some shortcut $\endgroup$
    – UmbQbify
    Jun 21 '20 at 1:15

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.