1

I have a doubt about systems of linear congruences: if I have solved the congruences and I have found as answers (for example) $x \cong8 \ (mod \ 12) $ and $x \cong 6 \ (mod \ 14)$, how can I find ALL the $x \in \Bbb Z$ that satisfy both equations?

I know I have two equations: $ x=8+12k$ and $x=6+14l$ , $k,l \in \Bbb Z$, but I want to list all the integers that satisfy the equations.

Thank you very much.

user149448
  • 25

2 Answers2

1

$$x \equiv8\pmod{12}\implies x\equiv0\pmod4,x\equiv2\pmod3$$

$$x\equiv6\pmod{14}\implies x\equiv0\pmod2,x\equiv6\pmod7$$

So, apply CRT on $$ x\equiv0\pmod4,x\equiv2\pmod3,x\equiv6\pmod7$$ as $4,3,7$ are pairwise co-prime

Alternatively, $$x\equiv2\pmod3\equiv-1,x\equiv6\pmod7\equiv-1$$

So, $x+1$ is divisible by $3,7$ hence by their LCM $=21$

So, $x+1=21a$ where $a$ is any integer

Now, $x=21a-1$ needs to be divisible by $4$

Setting $a=4b,4b+1,4b+2,4b+3$ one by one where $b$ is any integer

$x=21(4b+1)-1=84b+20$

lab bhattacharjee
  • 274,582
0

I like this question....but let's use the low-key method to solve this and have some fun....along the way...

From where you left off...

Goal: Solve for $k$.

Then $8 + 12k - 6 = 14l \to 12k = 14l - 2 = 12l + (2l - 2) \to k = l + \dfrac{2l - 2}{12} = l + \dfrac{l - 1}{6}$

In order for $k$ to be an integer, $6|(l - 1)$. So: $l - 1 = 6m \to l = 6m + 1 \to k = 6m + 1 + m = 7m + 1$.

So: $x = 8 + 12k = 8 + 12(7m + 1) = 84m + 20$, $m \in \mathbb{Z}$

DeepSea
  • 77,651