4
$\begingroup$

I want to find the solutions of the congruences system: $p \equiv 11\pmod{24}$ and $ p\equiv 3 \pmod 4$.

I probably have some mistake in my solution, can you tell me where I'm wrong?

$ 4 $ and $24$ are non co-primes so I can't use Chinese theorem. So I used this: enter image description here

and becuase $24=2^3 * 3 $ I found the solution for the equivlanet system: $p \equiv 2(\mod3 )$ and $ p\equiv 3 (\mod 4) $ and now I used the Chinese theorem and found that $ p\equiv 11 (\mod 12) $.

But when trying to check my answer, I noticed that for exmaple $ 23\equiv 11 (\mod 12) $ but it's not true that $ 23\equiv 11 (\mod 24) $ which is the original congruence, So what did I do wrong? and could anyone explain me the method to solve congruences like this where the modulos are not co-primes? thank you.

$\endgroup$
2
$\begingroup$

If $p\equiv11\pmod{24}$ then $p\equiv3\pmod{4}$, because if $p=11+24k$ for some $k\in\Bbb{Z}$ then $$p=3+4(2+6k),$$ with $2+6k\in\Bbb{Z}$. So you only need to solve $p\equiv11\pmod{24}$.

The equivalent system, using the Chinese Remainder theorem, should be $$p\equiv2\pmod{3}\qquad\text{ and }\qquad p\equiv3\pmod{8},$$ the latter congruence should be modulo $8$. Breaking down congruences this way is a good approach to solving systems of modular equations, also when the moduli are not coprime.

$\endgroup$
  • 1
    $\begingroup$ thank you, but what is wrong with the way that I broke down the congruences? I used the theorem that I wrote in the post $\endgroup$ – CnR Jun 5 '16 at 11:21
  • $\begingroup$ Because $24=2^3\times3$, the Chinese remainder theorem allows you to check the congruence for the maximal prime powers dividing $24$, which are $2^3$ and $3^1$, i.e. $8$ and $3$. Not $4$ and $3$. $\endgroup$ – Servaes Jun 5 '16 at 11:24
  • $\begingroup$ How do I decide to break down? I mean why couldn't it be p congruent to 2 mod 8 and p congruent to 3 mod 3? $\endgroup$ – CnR Jun 5 '16 at 12:17
  • $\begingroup$ Because $p\equiv11\pmod{24}$ implies that $p\equiv11\pmod{3}$ and $p\equiv11\pmod{8}$, by an argument similar to the one in my answer. $\endgroup$ – Servaes Jun 5 '16 at 13:46
2
$\begingroup$

$$p\equiv11\pmod{24}\implies p\equiv11\pmod4\equiv3$$

So, it is sufficient to have $$p\equiv11\pmod{24}$$

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