How can I solve a system of 2 congruences?

Question

I have this system of congruences $ p \equiv 3 \pmod 4$ and $ p \equiv 2 \pmod 3$ and the solution written in the book is $ p \equiv 11 \pmod {12 }$ but I do not know how? Could anyone explain this for me please?

I feel like I can not apply Chinese remainder theorem as it requires at least 3 congruences ..... am I correct?

Answer 1

You could apply the Chinese remainder theorem. For this particular system, the solution is simple:

$p\equiv-1\pmod4$ and $p\equiv-1\pmod3$ means $4|p+1$ and $3|p+1$, so $12|p+1$;

i.e., $p\equiv-1\pmod{12}$.

[Note: $-1\equiv11\pmod{12}$.]

Answer 2

I like to use Bezout coefficients, like such: $-1\cdot3+1\cdot4=1$.

Then we write $x=3\cdot(-3)+2\cdot 4=-1\cong {11}\pmod{12}$.

Answer 3

You can write $$p=3+4m,p=2+3n$$ so $$1=3n-4m$$ solving this Diophantine equation we get $$m=2+3C,n=4+4C$$ so $$p=11+12C$$

Answer 4

For a problem like this, simple trial and error suffices.

For a general method: Start with $p\equiv 3\pmod 4$. That tells us that $p=3+4k$. Now we move to the second congruence, contingent on the first. $$p\equiv 2\pmod 3\iff 3+4k\equiv 2\pmod 3\iff k\equiv 2 \pmod 3$$ $$\iff k=2+3l\iff p = 11+12l\iff p\equiv 11 \pmod {12}$$

as desired.

Answer 5

One starts from Bézout's identity: $\;4u+3v=1\quad(u,v\in\mathbf Z)$, say $4-3=1$. By the Chinese remainder theorem, $$\begin{cases} p\equiv \color{red}{\alpha\mod 4}\\ p\equiv\color{blue}{\beta\mod 3} \end{cases}\iff p\equiv \color{blue}{\beta}\,\color{red}{4}u+\color{red}{\alpha}\,\color{blue}{3}v\mod 3\cdot4 $$