Getting the General Solution of Linear Congruence

Question

$4x \equiv 12 \pmod {26}$

I have this equation and I understand that it has two solution via $\text{gcd}(26, 4)$. One of the answers is $x\equiv3$, which I can get by multiplying both sides by inverse of $4$. But the other answer which is $x\equiv16$.

I don't understand how to get this. Is it something to do with getting a general equation? Bezout's identity?

score 1 · Answer 1 · answered Dec 04 '14 at 08:14

1

$4x = 12\pmod {26} \Rightarrow 4x - 12 = 26k \Rightarrow 2x - 6 = 13k \Rightarrow 2(x-3) = 13k \Rightarrow 2\mid 13k \Rightarrow 2\mid k \Rightarrow k = 2n \Rightarrow 2x - 6 = 13(2n) = 26n \Rightarrow x - 3 = 13n \Rightarrow x = 3 + 13n$, $n \in \mathbb{Z}$.

answered Dec 04 '14 at 08:14

DeepSea

77,651

$2\mid 13k \Rightarrow 2\mid k \Rightarrow k = 2n \Rightarrow 2x - 6 = 13(2n) = 26n $ This part I don't understand. Are you saying that k by itself is congruent to 2n? – raz789 Dec 04 '14 at 08:24

score 0 · Accepted Answer · answered Dec 04 '14 at 08:22

0

$$4x\equiv12\pmod{26}\iff2x\equiv6\pmod{13}$$

$$\implies x\equiv3\pmod{\frac{13}{(13,2)}}$$

$$\implies x\equiv3\pmod{13}$$

See Property $\#12$ of Congruence

answered Dec 04 '14 at 08:22

lab bhattacharjee

274,582

Should it not still be (mod 26)? And aren't there two solutions? – raz789 Dec 04 '14 at 08:26
@raz789, $x\equiv3\pmod{13}\implies x\equiv3,3+(2-1)\cdot13\pmod{26}$ – lab bhattacharjee Dec 04 '14 at 08:27
Can you explain this $x\equiv3,3+(2-1)\cdot13\pmod{26}$ side? – raz789 Dec 04 '14 at 08:34
@raz789, $$x\equiv3\pmod{13}\implies x\equiv3+13a\pmod{13m},0\le a\le m-1$$ – lab bhattacharjee Dec 04 '14 at 08:40

Getting the General Solution of Linear Congruence

2 Answers2