1
$\begingroup$

$p$ is a prime number.

How to tell if a system of congruences:

\begin{align} x &\equiv a_1 \pmod{p^{i_1}} \\ x&\equiv a_2 \pmod{p^{i_2}} \\ &\dots\\ x &\equiv a_n \pmod{p^{i_n}} \end{align}

Has a solution.

How would you find the solution?

I feel like it has something to do with the chinese remainder theorem but the mod bases are definitely not pairwise relatively prime

$\endgroup$
0
$\begingroup$

If I understand your question correctly, you have \begin{align*} x & \equiv a_1 \pmod{p^{e_1}}\\ x & \equiv a_2 \pmod{p^{e_2}}\\ \vdots & \equiv \vdots\\ x & \equiv a_k \pmod{p^{e_k}} \end{align*}

Without the loss of generality, let us assume $e_1 \leq e_2 \leq \dotsb \leq e_k$. If the last congruence $x \equiv a_k \pmod{p^{e_k}}$ has a solution, then we should have $x \equiv a_k \pmod{p^j}$ for all $j \leq e_k$. In other words, all the congruences with smaller powers should also give the same residue. So you need $a_1 \equiv a_2 \equiv \dotsb$ for the solution to exist.

$\endgroup$
  • $\begingroup$ Thanks for the quick, great response! When you say you need a1 congruent to a2 congruent ak, is that mod(p^(ek))? Sorry I don't know how to format this stuff correctly $\endgroup$ – rando Oct 7 '18 at 19:53
0
$\begingroup$

The general condition for a system of congruences with non-necessarily coprime moduli $$x\equiv a_i\pmod{m_i}\qquad (1\le i\le r)$$ is that $$\forall (i,j), 1\le i,j\le r,\enspace a_i\equiv a_j\mod \gcd(m_i,m_j).$$

$\endgroup$
0
$\begingroup$

In general, $x \equiv a \pmod{p^\alpha}$ and $x \equiv b \pmod{p^\beta}$ if and only if $a \equiv b \pmod{p^\beta}$.

For example, $x \equiv a \pmod{13^5}$ and $x \equiv b \pmod{13^3}$ if and only if $a \equiv b \pmod{13^3}$

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