Computing Linear Congruence -Uncertainty Of Answer

52 Views Asked by At

given: $$17x\equiv 3\pmod{2\cdot3\cdot5\cdot7}$$

after extended euclidean algorithm of $(17,210)$ I got:

$$1=3\cdot210+17\cdot(-37)$$ now multplying both RHS and LHS by $3$ I get :

$$210\cdot9+17\cdot(-111)=3$$

then, doing (mod $210$) for both sides I get:

$$17\cdot(-111)\equiv 3\pmod{210}$$

so the answer supposed to be $-111$ but the answer is $99$ for $X.$

My question: is it valid to add $210$ just to $-111$ without the all exp. which is $17(-111)$?

2

There are 2 best solutions below

1
On

Since $111+99=210,$ you have $99\equiv -111 \bmod 210,$ so $-111$ is the same as $99.$ If an assigned exercise requires a number in the set $\{0,1,2,3,\ldots,209\},$ then $-111$ would be wrong, but it's not incorrect to say that $-111$ belongs to the congruence class that you're looking for.

You shouldn't be calling the same thing both $x$ and $X;$ you can use one or the other.

0
On

For some modulus $m>0$, the residue class of $a$ modulo $m$ is the set of integers $x$ such that $$x\equiv a\pmod{m}$$ You may see this set denoted $\widehat{a}$, $[a]$, or $\bar{a}$ in various texts. Hence $\widehat{a}=a+mq$, where $q=0,\pm1,\pm2,\dotsc$. Note the numbers $0,1,2,\dotsc,m-1$ are incongruent modulo $m$ and so the $m$ residue classes $\widehat{0},\widehat{1},\widehat{2},\dotsc,\widehat{m-1}$ are disjoint with their union being the whole of $\mathbb{Z}$.

Any set of $m$ integers incongruent modulo $m$ is termed a complete residue system, and as such each representative comes from a distinct residue class $\widehat{0},\widehat{1},\widehat{2},\dotsc,\widehat{m-1}$. We see $\{0,1,2,3,\ldots,209\}$ is a complete residue system mod $210$, as is $\{1,2,3,\ldots,210\}$.

Now since $99\equiv -111\pmod{210}$, $-111$ and $99$ belong in the same residue class and we can say $\widehat{99}=\widehat{-111}$. Note $\widehat{99}=99+210\cdot q$ where $q=0,\pm1,\pm2,\dotsc$, and so we can extend this (infinitely) to generate the whole residue class $\widehat{99}$: $$\widehat{99}=\widehat{-111}=\widehat{309}=\widehat{-321},\dotsc$$ Note we could now go on to do this for all the other $209$ residue classes, and this would give us $210$ infinite sets of numbers whose union is $\mathbb{Z}$. Note if the modulus is a prime $p$, the residue classes modulo $p$ form a field. As such every element $a$ in a complete residue system, disregarding $0$, has a multiplicative inverse $a^{-1}$. In such a case

Note that if $\gcd(a,m)=1$, then the linear congruence $$a\cdot x \equiv b \pmod{m}$$ has a unique solution $b$.

Hence due to $\gcd(17,210)=1$ your solution will be unique. This also means you can divide through by $17$ in the congruence to give $$x\equiv \frac{3}{17}\equiv3\cdot17^{-1}\equiv3\cdot173\equiv99\pmod{210}$$ Here $17^{-1}\equiv173\pmod{210}$, or multiplying through by $17$ we get $$17\cdot173\equiv1\pmod{210}$$ We call $17$ and $173$ modular inverses of each other as their product is $1$ modulo $210$. (This is how division works in congruences, you have to think in terms of inverses.)

One way of finding these modular inverses is the extended Euclidean algorithm: \begin{align*} 210&=12\cdot17+6\\ 17&=2\cdot6+5\\ 6&=1\cdot5+1 \end{align*} so, working backwards \begin{align*} 1&=6-1\cdot5=6-1\cdot(17-2\cdot6)=3\cdot6-1\cdot17\\ &=3\cdot(210-12\cdot17)-1\cdot17\\ &=3\cdot210-37\cdot17 \end{align*} So looking mod $210$ we get $$3\cdot210-37\cdot17\equiv0-37\cdot17\equiv173\cdot 17\equiv1\pmod{210}$$ because modulo $210$, $\widehat{-37}=\widehat{173}$.